proof of Euler’s criterion

(All congruences are modulo $p$ for the proof; omitted for clarity.)

Let

x=a^{(p-1)/2}

Then $x^{2}\equiv 1$ by Fermat’s Little Theorem. Thus:

x\equiv\pm 1

Now consider the two possibilities:

•

If $a$ is a quadratic residue then by definition, $a\equiv b^{2}$ for some $b$ . Hence:

$x\equiv a^{(p-1)/2}\equiv b^{p-1}\equiv 1$
•

It remains to show that $a^{(p-1)/2}\equiv-1$ if $a$ is a quadratic non-residue. We can proceed in two ways:

Proof (a)

Partition the set $\left\{\ 1,\ldots,p-1\ \right\}$ into pairs $\left\{\ c,d\ \right\}$ such that $cd\equiv a$ . Then $c$ and $d$ must always be distinct since $a$ is a non-residue. Hence, the product of the union of the partitions is:

$(p-1)!\equiv a^{(p-1)/2}\equiv-1$

and the result follows by Wilson’s Theorem.

Proof (b)

The equation:

$z^{(p-1)/2}\equiv 1$

has at most $(p-1)/2$ roots. But we already know of $(p-1)/2$ distinct roots of the above equation, these being the quadratic residues modulo $p$ . So $a$ can’t be a root, yet $a^{(p-1)/2}\equiv\pm 1$ . Thus we must have:

$a^{(p-1)/2}\equiv-1$

QED.