Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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$?

share|improve this question

marked as duplicate by user91500, amWhy, naslundx, Daniel Rust, egreg Apr 22 at 14:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
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

1 Answer 1

up vote 3 down vote accepted

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$.

share|improve this answer
    
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
1  
@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

Not the answer you're looking for? Browse other questions tagged or ask your own question.