Number of Quadratic Residues of a Prime

From ProofWiki
Jump to: navigation, search

Theorem

Let $p$ be an odd prime.

Then $p$ has $\dfrac {p-1} 2$ quadratic residues and $\dfrac {p-1} 2$ quadratic non-residues.

The quadratic residues are congruent modulo $p$ to the integers $1^2, 2^2, \ldots, \left({\dfrac {p-1} 2}\right)$.


Proof

The quadratic residues of $p$ are the integers which result from the evaluation of the squares $1^2, 2^2, \ldots, \left({p-1}\right)^2$ modulo $p$.

But $r^2 = \left({-r}\right)^2$ and so these $p - 1$ integers fall into congruent pairs modulo $p$, namely:

\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle 1^2\) \(\equiv\) \(\displaystyle \) \(\displaystyle \left({p-1}\right)^2\) \(\displaystyle \pmod p\) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle 2^2\) \(\equiv\) \(\displaystyle \) \(\displaystyle \left({p-2}\right)^2\) \(\displaystyle \pmod p\) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\ldots\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \left({\frac {p-1} 2}\right)^2\) \(\equiv\) \(\displaystyle \) \(\displaystyle \left({\frac {p+1} 2}\right)^2\) \(\displaystyle \pmod p\) \(\displaystyle \)          Note: we require $p$ to be odd here.          

Therefore each quadratic residue of $p$ is congruent modulo $p$ to one of the $\dfrac {p-1} 2$ integers $1^2, 2^2, \ldots, \left({\dfrac {p-1} 2}\right)^2$.

Note that as $r^2 \not \equiv 0 \pmod p$ for $1 \le r < p$, the integer $0$ is not among these.


All we need to do now is show that no two of these integers are congruent modulo $p$.

So, suppose that $r^2 \equiv s^2 \pmod p$ for some $1 \le r \le s \le \dfrac {p-1} 2$.

What we are going to do is prove that $r = s$.

Now $r^2 \equiv s^2 \pmod p$ means that $p$ is a divisor of $r^2 - s^2 = \left({r + s}\right) \left({r - s}\right)$.

From Euclid's Lemma we see that either $p \backslash \left({r + s}\right)$ or $p \backslash \left({r - s}\right)$.

$p \backslash \left({r + s}\right)$ is impossible as $2 \le r + s \le p - 1$.

As for $p \backslash \left({r - s}\right)$, as $0 \le r - s < \dfrac {p-1} 2$, that can happen only when $r - s = 0$ or $r = s$.

So there must be exactly $\dfrac {p-1} 2$ quadratic residues, and that means there must also be exactly $\dfrac {p-1} 2$ quadratic non-residues.

$\blacksquare$