Let be an odd prime such that . Evaluate with reasons, , where , being the greatest integer not exceeding .
Solution
The answer is .
Note that are pairwise incongruent modulo since
As there are exactly nonzero quadratic residues, are all the nonzero quadratic residues modulo .
Since , is a quadratic residue modulo . Therefore, is a quadratic residue modulo if and only if is a quadratic residue modulo . This shows the nonzero quadratic residues come in pairs such that the numbers in each pair are negative of each other modulo . Thus, for can be partitioned into pairs, such that the sum of each pair is . Thus, the sum is equal 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.