# Prove the congruence $\sum_{r=1}^{p-1}{(r|p) * r } \equiv 0 \pmod p.$

Prove that if $p$ is prime and $p\equiv 1 \pmod4$, then $$\sum_{r=1}^{p-1}{(r|p) * r } \equiv 0 \pmod p.$$ ( $(r|p)$ is a Legendre Symbol )

I know that $\sum_{1 \le r \le p}{(\frac{r}{p})} = 0$, but I don't know what to do with the multiplication by r.

## 3 Answers

Denote your sum by $S$. Note: you don't need a congruence on $p$, but you do need $p>3$.

Proof I:

Let $s\neq 1$ be a fixed non-zero square $\pmod p$ (this requires that $p>3$.)

As $r$ spans the non-zero residues, so does $sr$. Thus (working $\pmod p$): $$S=\sum_{r=1}^{p-1}\left(\frac {sr}p\right)sr=s\sum_{r=1}^{p-1}\left(\frac {r}p\right)r=s\times S\implies S=0$$

Proof II:

Let $g$ be a primitive root $\pmod p$. Assume $p>3$ so $g\neq -1$. Then $$S=\sum_{i=1}^{p-1} (-1)^ig^i=-g\times \frac {(-g)^{p-1}-1}{(-g)-1}$$ That last sum is $0\pmod p$ by Fermat's little Theorem.

• I don't understand this. What is this fixed square? Don't we have to use $p \equiv 1 (mod 4)$ somewhere? – Topolożka Jun 6 '16 at 13:54
• you don't need the congruence on $p$ (though you do need $p>3$). $s$ is any square you like (other than $1$). I am just using the properties A. multiplication by $s$ simply permutes the non-zero residues. and B. Multiplying by a square leaves the Legendre symbol unchanged. – lulu Jun 6 '16 at 14:06
• I just added a second proof, using primitive roots. – lulu Jun 6 '16 at 14:19

Here is another proof. Note that, for an odd prime $p$, \begin{align*} \sum_{r=1}^{p-1} \bigg(\frac rp\bigg) r &= \sum_{r=1}^{p-1} \bigg( \bigg(\frac rp\bigg) + 1 \bigg) r - \sum_{r=1}^{p-1} r \\ &= \bigg( \sum_{r=1}^{p-1} \#\{ m \text{ (mod }p)\colon m^2\equiv r\text{ (mod }p)\} \cdot r \bigg) - \frac{p(p-1)}2 \\ &\equiv \bigg( \sum_{m=1}^{p-1} m^2 \bigg) - 0 \pmod p \\ &= \frac{(p-1)p(2p-1)}6 . \end{align*} When $p>3$, this last expression is $0$ (mod $p$).

This proof highlights the often-overlooked method of converting a sum involving Legendre symbols into a sum taken directly over the squares (mod $p$). The second equality is easy but is worth remembering; the third step might take some thoughtful reflection, but I think that time is well worth it.

$\newcommand{\jaco}[2]{\left(\frac{#1}{#2}\right)}$Since $-1$ is a quadratic residue modulo $p$ you have $\jaco{-1}p=1$ and $\jaco ap = \jaco{-a}p$. This gives you $$\jaco ap =\jaco{p-a}p$$ and $$a\jaco ap + (p-a)\jaco{p-a}p = p \equiv 0 \pmod p.$$ So you can see that the numbers $1,2,\dots,p-1$ can be divided into $\frac{p-1}2$ pairs, such that the contribution of each pair to the sum is a multiple of $p$.

In fact, in this way we can show that \begin{align*} \sum\limits_{\substack{a=1\\(a|p)=1}}^{p-1} a &= \frac{p(p-1)}4\\ \sum\limits_{\substack{a=1\\(a|p)=-1}}^{p-1} a &= \frac{p(p-1)}4 \end{align*} and \begin{align*} \sum\limits_{a=1}^{p-1} a\jaco ap &= \sum\limits_{\substack{a=1\\(a|p)=1}}^{p-1} a - \sum\limits_{\substack{a=1\\(a|p)=-1}}^{p-1} a \\ &= \frac{p(p-1)}4 - \frac{p(p-1)}4 = 0 \end{align*}

• A good proof for the case the OP wanted (although as lulu pointed out, the assumption that $p\equiv1\pmod4$ isn't actually necessary). – Greg Martin Jun 6 '16 at 18:45
• @GregMartin I have seen this as the first part of Exercise 7 in Chapter 9 in Apostol's Introduction to Analytic Number Theory. (Apostol includes the requirement on $p$.) The part (b) of the same exercise is one of the sums I have added in my post. As far as I can say, in that part the assumption on $p$ cannot be omitted. – Martin Sleziak Jun 6 '16 at 19:38
• Ah, for those sums the assumption $p\equiv1\pmod4$ is certainly necessary. – Greg Martin Jun 6 '16 at 22:14