Maths Olympiad Prep

Library / /35 of 94

Number theory Difficulty 5.7 AIME, harder Prove it Hong Kong

Let pp be an odd prime such that p1(mod4)p \equiv 1 \pmod 4. Evaluate with reasons, k=1p12{k2p}\sum_{k=1}^{\frac{p-1}{2}} \left\{ \frac{k^2}{p} \right\}, where {x}=x[x]\{x\} = x - [x], [x][x] being the greatest integer not exceeding xx.

Solution

The answer is p14\frac{p-1}{4}.
Note that 12,22,,(p12)21^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2 are pairwise incongruent modulo pp since
x2y2(modp)x±y(modp). x^2 \equiv y^2 \pmod{p} \Rightarrow x \equiv \pm y \pmod{p}.
As there are exactly p12\frac{p-1}{2} nonzero quadratic residues, 12,22,,(p12)21^2, 2^2, \dots, \left(\frac{p-1}{2}\right)^2 are all the nonzero quadratic residues modulo pp.
Since p1(mod4)p \equiv 1 \pmod 4, 1-1 is a quadratic residue modulo pp. Therefore, rr is a quadratic residue modulo pp if and only if r-r is a quadratic residue modulo pp. This shows the nonzero quadratic residues come in pairs such that the numbers in each pair are negative of each other modulo pp. Thus, {k2p}\left\{ \frac{k^2}{p} \right\} for k=1,2,,p12k = 1, 2, \dots, \frac{p-1}{2} can be partitioned into p14\frac{p-1}{4} pairs, such that the sum of each pair is r+(pr)p=1\frac{r + (p-r)}{p} = 1. Thus, the sum is equal to p14\frac{p-1}{4}.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.