Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question

1 Answer 1

up vote 14 down vote accepted

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

share|improve this answer
    
Good answer. Chan and I use \pmod {4}, instead of \bmod {4}, which gets you parentheses around it if you want them. –  Ross Millikan Apr 4 '11 at 2:18
    
@Zev Chonoles: Thank you. However, the question asked to prove it equals to $\dfrac{p(p-1)}{4}$. I'm confused now. –  Chan Apr 4 '11 at 2:23
    
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. –  awllower Apr 4 '11 at 2:23
    
And it is easy to compute the sum using the argument of Zev Chonoles, isn't it? –  awllower Apr 4 '11 at 2:24
    
@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$. –  Zev Chonoles Apr 4 '11 at 2:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.