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 \) \(\displaystyle \left({p-1}\right)^2\) \(\displaystyle \pmod p\) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle 2^2\) \(\equiv\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \left({p-2}\right)^2\) \(\displaystyle \pmod p\) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\ldots\) \(\displaystyle \) \(\) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \)                    
\(\displaystyle \) \(\displaystyle \) \(\displaystyle \) \(\displaystyle \left({\frac {p-1} 2}\right)^2\) \(\equiv\) \(\displaystyle \) \(\) \(\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$