Let be a prime number. Prove the following theorem of Euler: the equation has a solution with if and only if or . (You may use the fact that the ring of integers of is a principal ideal domain.)
Solution
The "only if" part is clear. We prove the "if" part. For one can take . Assume . By quadratic reciprocity, . Thus splits in . The ring of integers of is , where . Since is a PID, there exists such that . We claim that at least one of , , and belongs to and thus is of the form with . Taking norms, we then get . To prove the claim, we may assume , where and are odd integers. Then either (which is equivalent to ) or (which is equivalent to ).
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.