# Help with quadratic residues problem.

Problem:

Show that for any odd prime $p>3$, $p$ divides the sum of its quadratic residues.

My attempt: Denote the quadratic residues with $$r_1,r_2,\dots, r_j$$

Case 1: $\quad p\equiv 1\pmod{4}$. Observe that, for any quadratic residue $r$, $$\left(\frac{p-r}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{r}{p}\right) = \left(\frac{r}{p}\right) = 1.$$ Thus, $$\sum_{k=1}^{j}r_k \equiv jp-\sum_{k=1}^{j}r_k\pmod{p}$$ $$\sum_{k=1}^{j}r_k \equiv 0 \pmod{p}$$

Case 2: $\quad p\equiv 3\pmod{4}$ and $p\equiv \pm 1\pmod{8}$. Observe that, for any quadratic residue $r$, $$\left(\frac{p+2r}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{r}{p}\right) = \left(\frac{r}{p}\right) = 1.$$ Thus, $$\sum_{k=1}^{j}r_k \equiv jp+2\sum_{k=1}^{j}r_k\pmod{p}$$ $$\sum_{k=1}^{j}r_k \equiv 0 \pmod{p}$$

Case 3: $\quad p\equiv 3\pmod{4}$ and $p\equiv \pm 3\pmod{8}$. Observe that, for any quadratic residue $r$, $$\left(\frac{p-2r}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)\left(\frac{r}{p}\right) = (-1)(-1)\left(\frac{r}{p}\right) = 1.$$ Thus, $$\sum_{k=1}^{j}r_k \equiv jp-2\sum_{k=1}^{j}r_k\pmod{p}$$ $$\sum_{k=1}^{j}r_k \equiv 0 \pmod{p}$$

Is my solution correct and is there a better way of solving this problem ?

• The quadratic residues of $p$ modulo what? – Bernard Jun 3 '18 at 21:40
• @Bernard By quadratic residue I was referring to any least residue $a$ modulo $p$ such that $x^2\equiv a\pmod{p}$ has a solution, or simply $(a/p)=1$. – Adam Jun 3 '18 at 21:42
• Hint: what is $\sum_{i=1}^p i^2$? – lulu Jun 3 '18 at 21:46
• @Adam, what notation is (2/p) (r/p) = (r/p) ? – meticoeus Jun 4 '18 at 1:40
• @meticoeus I suppose it is the Legendre symbol. – feynhat Jun 4 '18 at 1:42

We note that $$\sum_{i=1}^pi^2=\frac {p(p+1)(2p+1)}6$$

Note that for $p>3$ this fraction makes sense $\mod p$ and is plainly divisible by $p$.

If we work $\pmod p$ the left hand sum is exactly twice the sum of the quadratic residues $\pmod p$ (since every non-zero quadratic residue has exactly two square roots $\pmod p$, and the quadratic residue $0$, which has only one square root, doe not effect the sum $\pmod p$) so the sum of the quadratic residues is $$\frac {p(p+1)(2p+1)}{12}$$

Since $p>3$ we see that this is $0\pmod p$ so we are done.

• @RoryDaulton Right, thanks. I'll edit to note that. – lulu Jun 4 '18 at 10:09

Much simpler. Let $\{a_1,\ldots, a_r\}$ be the complete set of $p$'s $r$ nonzero quadratic residues (whatever $r$ is). Then these form a group under multiplication.

Fact 1: So for any $a_j$, the following holds: $$a_j \sum_{i=1}^r a_i = \sum_{k=1}^r a_k.$$

(Indeed, the set $\{a_ja_1, \ldots, a_ja_r\}$ is just $\{a_1,\ldots, a_r\}$ permuted. Make sure you see why.)

Fact 1 implies that $\sum_{i=1}^1 a_i$ has to be 0 mod $p$ (or there is only at most one nonzero quadratic residue $a_1 = 1$ possible only for $p=2,3$). Adding 0 (which is also a quadratic residue) doesn't change this

• I haven't learned any group theory yet. – Adam Jun 3 '18 at 21:49
• Is my solution correct though ? – Adam Jun 3 '18 at 21:52
• Well, but you do know that if $a_i$ and $a_j$ are quadratic residues, then so is $a_ia_j$, and that if $a_j$ and $a_{j'}$ are distinct elements mod $p$ and $a_i$ is nonzero (e.g., a nonzero quadratic residue) then $a_ia_j$ and $a_ia_{j'}$ are also distinct. This implies Fact 1 just just the same – Mike Jun 3 '18 at 21:53
• @Adam I don't know. I wasn't able to follow after the Thus in e.g., Case 1. – Mike Jun 3 '18 at 21:57
• I am not the person to ask as I don't know the finer points of quadratic residue theory (I'm sorry). But I do know what I gave above works though.... – Mike Jun 3 '18 at 22:10