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.


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.

  • $\begingroup$ I don't understand this. What is this fixed square? Don't we have to use $p \equiv 1 (mod 4) $ somewhere? $\endgroup$ – Topolożka Jun 6 '16 at 13:54
  • $\begingroup$ 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. $\endgroup$ – lulu Jun 6 '16 at 14:06
  • $\begingroup$ I just added a second proof, using primitive roots. $\endgroup$ – 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*}

  • 1
    $\begingroup$ A good proof for the case the OP wanted (although as lulu pointed out, the assumption that $p\equiv1\pmod4$ isn't actually necessary). $\endgroup$ – Greg Martin Jun 6 '16 at 18:45
  • $\begingroup$ @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. $\endgroup$ – Martin Sleziak Jun 6 '16 at 19:38
  • $\begingroup$ Ah, for those sums the assumption $p\equiv1\pmod4$ is certainly necessary. $\endgroup$ – Greg Martin Jun 6 '16 at 22:14

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.