# 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.

Title proof of Euler’s criterion ProofOfEulersCriterion 2013-03-22 12:41:53 2013-03-22 12:41:53 Koro (127) Koro (127) 7 Koro (127) Proof msc 11A15