3
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ The quadratic residues of $p$ modulo what? $\endgroup$ – Bernard Jun 3 '18 at 21:40
  • $\begingroup$ @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$. $\endgroup$ – Adam Jun 3 '18 at 21:42
  • 2
    $\begingroup$ Hint: what is $\sum_{i=1}^p i^2$? $\endgroup$ – lulu Jun 3 '18 at 21:46
  • $\begingroup$ @Adam, what notation is (2/p) (r/p) = (r/p) ? $\endgroup$ – meticoeus Jun 4 '18 at 1:40
  • $\begingroup$ @meticoeus I suppose it is the Legendre symbol. $\endgroup$ – feynhat Jun 4 '18 at 1:42
7
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ I haven't learned any group theory yet. $\endgroup$ – Adam Jun 3 '18 at 21:49
  • $\begingroup$ Is my solution correct though ? $\endgroup$ – Adam Jun 3 '18 at 21:52
  • 1
    $\begingroup$ 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 $\endgroup$ – Mike Jun 3 '18 at 21:53
  • 1
    $\begingroup$ @Adam I don't know. I wasn't able to follow after the Thus in e.g., Case 1. $\endgroup$ – Mike Jun 3 '18 at 21:57
  • 1
    $\begingroup$ 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.... $\endgroup$ – Mike Jun 3 '18 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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