Proof of Euler's Criterion for Quadratic Residues
Let
\[p\]
be an odd prime and let \[a \neq 0 \; (mod \; p)\]
be an integer. Then \[a\]
is a quadratic residue of \[p\]
if and only if \[a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p)\]
, and is a quadratic non residue of \[p\]
if and only if \[a^{\frac{p-1}{2}} \equiv -1 \; (mod \; p)\]
.Proof
Let
\[a\]
be a quadratic non residue of \[p\]
and let \[1 \le b \le p-1\]
be an integer. The linear congruence \[bx \equiv a \; (mod \; p)\]
has a unique solution \[1 \le b' \le p-1\]
. \[b \neq b'\]
otherwise \[b^2 \equiv 1 \; (mod \; p)\]
and \[a\]
would be a quadratic residue of \[p\]
. It follows that the set \[\{ 1, \' 2,..., \; p-1 \}\]
falls into \[\frac{p-1}{2}\]
disjoint pairs \[(b, \; b')\]
with the property that \[bb' \equiv a \; (mod \; p)\]
. Multiplying these pairs together gives\[(p-1)! \equiv a^{\frac{p-1}{2}} \; (mod \; p)\]
.From Wilson's Theorem,
\[(p-1)! \equiv 1 \; (mod \; p)\]
so \[a^{\frac{p-1}{2}} \equiv -1 \; (mod \; p)\]
for any quadratic non residue \[a\]
.Let
\[a\]
be a quadratic residue of \[p\]
so that \[x^2 \equiv a \; (mod \; p)\]
has a solution. In fact it will have two solutions. Lagrange's Theorem guarantees at most two solutions, and if \[1 n\le c \le p-1\]
is a solution then so is \[1 n\le p-c \le p-1\]
, since \[(p-c)^2=p^2-2pc+c^2 \equiv c^2 \; (mod \; p)\]
.If we remove
\[c, \; p-c\]
from the set \[\{ 1, \; 2,..., \; p-1 \}\]
then as before the remaining \[p-3\]
integers fall into \[\frac{p-3}{2}\]
disjoint pairs \[(b, \; b')\]
with the property that \[bb' \equiv a \; (mod \; p)\]
. Then\[\begin{equation} \begin{aligned} (p-1)! &= 1 \times 2 \times 3 \times ... c \times ... \times (p-c) \times ... \times (p-1) \\ & \equiv a^{\frac{p-3}{2}} c(p-c) \; (mod \; p) \\ & \equiv a^{\frac{p-3}{2}} (-c^2) \; (mod \; p) \\ & \equiv a^{\frac{p-3}{2}} (-a) \; (mod \; p) \\ & \equiv -a^{\frac{p-1}{2}} \; (mod \; p) \end{aligned} \end{equation}\]
Using Wilson's Theorem as before,
\[-1 \equiv -a^{\frac{p-1}{2}} \; (mod \; p) \rightarrow 1 \equiv a^{\frac{p-1}{2}} \; (mod \; p)\]
for any quadratic residue
\[a\]
.Suppose now that
\[a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p) \; 1 \le a \le (p-1)\]
. \[a\]
is either a quadratic residue or a quadratic non residue of \[p\]
. If it is a quadratic non residue then \[a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p)\]
and this would imply \[1 \equiv -1 \; (mod \; p)\]
which is a contradiction, so if \[a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p) \]
then \[a\]
is a quadratic residue. 
