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.
 A: 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.
A: $\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: 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.
