Find all prime numbers such that has exactly solutions in integers modulo . In other words, determine all prime numbers with the following property: there exist exactly ordered pairs of integers such that and .
Solution
Clearly works with solutions and and not or . If then -1 is not a quadratic residue, so for , exactly one of and is a square and gives two solutions (for positive and negative ), so there's exactly two solutions for each such pair . If is such that , there's exactly one solution. If , let be a square root of . The right hand side factors as . For this is zero, there is one choice of , namely zero. Otherwise, the right hand side is nonzero. For any fixed , there are either 0 or 2 choices for . Replacing by negates the right hand side, again producing two choices for since -1 is a quadratic residue. So the total number of solutions is , and thus there cannot be exactly solutions.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.