Sum of quadratic residues.

Question

Let $p$ be an odd prime. Show that $$\sum_{j=0}^{p-1} \left(\frac{j}{p}\right) = 0 $$ The case when $$p\equiv 1\pmod4 $$ is easy. What if $$p\equiv 3\pmod4$$

Answer 1

Hint:

This is equivalent to saying there are as many quadratic residues as non-quadratic residues between $1$ and $p-1$.

By lil' Fermat each of these numbers satisfies the equation mod. $p\mkern1.5mu$: $$x^{p-1}-1=0 \equiv \Bigl(x^{\tfrac{p-1}2}-1\Bigr)\Bigl(x^{\tfrac{p-1}2}+1\Bigr)=0.$$ So each of these $p-1$ numbers is a root of one of these two factors, and $\mathbf Z/p \mathbf Z$ is a field. Can you find out why each factor has as many roots as the other?

Answer 2

It does not really matter if $p\equiv 1$ or $p\equiv 3\pmod{4}$. Let $Q$ be the set of quadratic residues in $\mathbb{Z}/(p\mathbb{Z})^*$ and $\eta$ be a quadratic non-residue: since the Legendre symbol is multiplicative $$ \mathbb{Z}/(p\mathbb{Z})^* = Q \cup \eta Q $$ where $Q$ and $\eta Q$ are disjoint. It follows that $|Q|-|\eta Q|$ (which is your sum) equals zero.