Theorem 1 In a reduced residue system modulo , there are exactly quadratic residues modulo , and quadratic non-residues modulo . Moreover, if is a quadratic residue modulo , then the number of solutions to the congruence equation (5) is 2.
Solution
To prove the evident, we only need to consider the absolute minimal reduced residue system modulo :
is a quadratic residue modulo if and only if
Since , is a quadratic residue modulo if and only if
When ,
Therefore, equation (7) gives all the quadratic residues modulo , totaling . Since the reduced residue system modulo has numbers, the other must be quadratic non-residues modulo , which proves the first half of the conclusion. When is a quadratic residue modulo , by equations (7) and (8), there must be a unique , such that is a solution to (5). Consequently, in the reduced residue system (6), there are exactly as solutions to (5), meaning the number of solutions to (5) is 2. Proof completed.
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.