Number of Quadratic Residues of a Prime

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

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$

\(\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.