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

Question

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.

Answer 1

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.

Answer 2

$\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*}

Answer 3

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.