12
$\begingroup$

I read one theorem in the book, they said there will be exactly $\dfrac{p-1}{2}$ quadratic residues of $p$. So for each $i$, $$x^2 \equiv a_i \pmod{p} \text{ where } 1 \leq i \leq p - 1$$

But if we sum all $a_i$, then what does this sum equal to? $$\sum_{i=1}^{\frac{p-1}{2}}a_i = ?$$

I haven't used the condition that $p \equiv 1 \pmod{4}$, so I think I missed one important point here. Any idea?

Update
The original problem
Let $p$ be a prime such that $p \equiv 1 \pmod{4}$.
Prove that the sum of those numbers $1 \leq r \leq p - 1$ that are quadratic residues modulo $p$ is $\dfrac{p(p-1)}{4}$.

Thanks,

1 Answers 1

21

Because $p\equiv 1\bmod 4$, we have that $-1$ is a quadratic residue modulo $p$. The product of two quadratic residues is a quadratic residue. This means that for any quadratic residue $a$, we have that $-a$ is also a quadratic residue. Thus the sum cancels to $0\bmod p$.


Because there are $\frac{p-1}{2}$ quadratic residues mod $p$, and they all occur in pairs $a$ and $p-a$, there are $\frac{p-1}{4}$ pairs each of whose sum is $p$, hence the sum of them all is $\frac{p(p-1)}{4}$.

  • 0
    Good answer. Chan and I use \pmod {4}, instead of \bmod {4}, which gets you parentheses around it if you want them.2011-04-04
  • 0
    @Zev Chonoles: Thank you. However, the question asked to prove it equals to $\dfrac{p(p-1)}{4}$. I'm confused now.2011-04-04
  • 0
    And, conversely, when can this be true? Since this holds to be true in the case p=7, one may want to ask this question.2011-04-04
  • 0
    And it is easy to compute the sum using the argument of Zev Chonoles, isn't it?2011-04-04
  • 0
    @Chan - my apologies then, I had incorrectly assumed the sum was to be evaluated modulo p. However, the stated answer is not in contradiction with my answer - note that $\frac{p(p-1)}{4}\equiv 0\bmod p$.2011-04-04
  • 0
    @Zev Chonoles: No worries. It was indeed my vague question. I see my problem now. It should be all positives $a_i$.2011-04-04
  • 0
    don't you mean each of whose sum is $\frac{p}{2}$?2014-10-06