7. If is a natural number, is a prime, prove that must be a quadratic residue modulo .
Solution
7. Proof: Since , -1 must be a quadratic residue modulo , i.e., there exists an integer such that
On the other hand, from we also have
Therefore,
Since , there must be a such that , thus
This is exactly what we need to prove.
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.