# Sum of Legendre symbols

I need to prove that if $p$ is a odd prime, then $$\sum_{i=1}^{p-1}\left[\left(p-i\right)\left(\frac{i}{p}\right)\right]\equiv0\pmod p,$$ but I have issues. I have been able to end up with a generic term like $$-i\left(\frac{i}{p}\right),$$ but is of no use. So, I think my proof is no good. Can you help me?

Sorry for my English.

• It seems false for $p=3$, possibly for all $p\equiv3\pmod4$ but I'm not sure. Perhaps there is the extra condition that $p\equiv1\pmod4$? Because then it is true. Or should the equality be in fact a congruency modulo $p$? That seems more likely. – punctured dusk Apr 26 '14 at 9:33
• To prove that the sum is congruent to $0$ modulo $p$ (if that's what you're asking) I suggest rewriting it as a geometric series using a primitive root. Recall that the Legendre symbol is completely multiplicative. – punctured dusk Apr 26 '14 at 9:42
• Did you mean the sum is zero modulo $\;p\;$ ? – DonAntonio Apr 26 '14 at 10:24
• yes - 0 modulo p – user145866 Apr 26 '14 at 14:45

Primitive$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}$ roots allow us to transform the sum into the sum of a geometric sequence.

Note that it is equivalent to prove $$\sum_{i=1}^{p-1}i\leg ip\equiv0,$$ because we can ignore multiples of $p$ and multiply both sides with $-1$.

Here comes the primitive root trick: let $w$ be a primitive root modulo $p$. Then every congruence class $1,2,\ldots,p-1$ is reached exactly once when we consider $w^0,w^1,w^2,\ldots,w^{p-2}\pmod p$.

Our sum is thus simplified to

$$\sum_{i=1}^{p-1}w^i\leg{w^i}p.$$ (But the order of the terms here is completely different.)

Using $\leg{w^i}p=(-1)^i$, it becomes

$$\sum_{i=1}^{p-1}(-w)^i.$$

If $-w\not\equiv1$ this is $$\frac{(-w)^{p-1}-1}{-w-1}\equiv0\pmod p,$$ by Fermat's Little Theorem.

It remains to check the case where $-w=1$, i.e, when $-1$ is a primitive root. This is, of course, only possible if $p=3$, in which case it is not much work to check that the congruence does not hold: $\sum_{i=1}^{2}(-(-1))^i=2\not\equiv0$. Or if you wish, $\sum_{i=1}^{2}(3-i)\leg i3=2-1\not\equiv0$.