Help with quadratic residues problem.

Question

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 ?

Answer 1

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.

Answer 2

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