# Sum of squares of the quadratic nonresidues modulo $p$ is divisible by $p$ [duplicate]

Let $p$ be a prime number with $p > 5$. Prove that the sum of the squares of the quadratic nonresidues modulo $p$ is divisible by $p$.

My idea is to use the fact that any quadratic residue is congruent modulo $p$ to one integer in the set $\{1^2,2^2,\ldots,\left( \frac{p-1}{2} \right)^2 \}$. And none of the quadratic residues are congruent to each other. So the quadratic nonresidues must all be in the set $\{ \left( \frac{p+1}{2} \right)^2 , \left( \frac{p+3}{2}\right)^2 \ldots, (p-1)^2\}$. So the sum of the quadratic nonresidues must be given by $$\sum_{k=1}^{p-1} k^2 - \sum_{k=1}^{\frac{p-1}{2}}k^2 = \frac{(p-1)p(2p-1)}{6} - \frac{\left( \frac{p-1}{2} \right) \left( \frac{p+1}{2} \right) p}{6} = \frac{p}{6} \left( (p-1)(2p-1) - \frac{1}{4}(p-1)(p+1) \right).$$ Is this the correct approach? Prove that the term in parenthesis is an integer divisible by $6$?

-

## marked as duplicate by 91500, amWhy, naslundx, Dan Rust, egregApr 22 '14 at 14:28

The quadratic non-residues are not in the set $\left(\frac{p+1}{2}\right)^2$ and so on. Those are quadratic residues, repeating the first bunch you mentioned. – André Nicolas Oct 30 '13 at 2:49

Using primitive roots finishes the problem quickly: Let $g$ be a primitive root, so that the sum of the squares of the quadratic non-residues is just

$$\sum_{i=1}^{\frac{p-1}{2}}{(g^{2i-1})^2} \equiv g^2\sum_{i=0}^{\frac{p-3}{2}}{g^{4i}} \equiv g^2\frac{1-(g^4)^{\frac{p-1}{2}}}{1-g^4} \equiv \frac{g^2(1-(g^{p-1})^2)}{1-g^4} \equiv 0 \pmod{p}$$

where since $p>5$, $p \nmid 1-g^4$ so the manipulations above are valid.

If you don't want to appeal to primitive roots, then something similar to what you tried can also be done. What we want is to take the sum of the squares of all non-zero elements and subtract the squares of the quadratic residues. So we get

\begin{align} &\sum_{k=1}^{p-1}{k^2}-\sum_{k=1}^{\frac{p-1}{2}}{(k^2)^2} \\ &\equiv \frac{(p-1)p(2p-1)}{6}-\frac{(\frac{p-1}{2})(\frac{p+1}{2})(p)(3(\frac{p-1}{2})^2+3(\frac{p-1}{2})-1)}{30} \pmod{p}\\ & \equiv p[\frac{(p-1)(2p-1)}{6}-\frac{(\frac{p-1}{2})(\frac{p+1}{2})(3(\frac{p-1}{2})^2+3(\frac{p-1}{2})-1)}{30}] \pmod{p}\\ & \equiv 0 \pmod{p} \end{align}

where we may treat $\frac{1}{30}=30^{-1}$ as an element in $\mathbb{Z}_p$ since $p>5$.

-
Nice! Why is the last k^2 squared? And where does all those 3's come from in the final form of the summation of the quadratic residues? :p – Numbersandsoon Oct 30 '13 at 3:07
@BoSchmidt The quadratic residues are $k^2$ for $k=1, 2, \ldots , \frac{p-1}{2}$. We want to subtract the squares of the quadratic residues, so that's $(k^2)^2$. I have used the formula $\sum_{k=1}^{n}{k^4}=\frac{k(k+1)(2k+1)(3k^2+3k-1)}{30}$, which can be proved in various ways. – Ivan Loh Oct 30 '13 at 3:09
Ah, that's right! Can we be sure of the last line in the congruences? Isn't it necessary to show that the sum in the parentheses is an integer? – Numbersandsoon Oct 30 '13 at 3:14
@BoSchmidt Since $\gcd(30, p)=1$, we may treat $\frac{1}{30}$ as the inverse of $30$ in $\mathbb{Z}_p$, i.e. the element $x \in \mathbb{Z}_p$ s.t. $30x \equiv 1 \pmod{p}$. If you are uncomfortable with such, then write instead $30(\sum_{k=1}^{p-1}{k^2}-\sum_{k=1}^{\frac{p-1}{2}}{k^4}) \equiv 0 \pmod{p}$ and say that since $p \nmid 30$, we have $(\sum_{k=1}^{p-1}{k^2}-\sum_{k=1}^{\frac{p-1}{2}}{k^4}) \equiv 0 \pmod{p}$. – Ivan Loh Oct 30 '13 at 3:18
Got it! Thank you very much. – Numbersandsoon Oct 30 '13 at 3:21