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.

  • $\begingroup$ 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. $\endgroup$ – punctured dusk Apr 26 '14 at 9:33
  • $\begingroup$ 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. $\endgroup$ – punctured dusk Apr 26 '14 at 9:42
  • $\begingroup$ Did you mean the sum is zero modulo $\;p\;$ ? $\endgroup$ – DonAntonio Apr 26 '14 at 10:24
  • $\begingroup$ yes - 0 modulo p $\endgroup$ – 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


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$.


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.