proof of Euler’s criterion
(All congruences^{} are modulo $p$ for the proof; omitted for clarity.)
Let
$$x={a}^{(p1)/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}^{(p1)/2}\equiv {b}^{p1}\equiv 1$$ 
•
It remains to show that ${a}^{(p1)/2}\equiv 1$ if $a$ is a quadratic nonresidue. We can proceed in two ways:
 Proof (a)

Partition^{} the set $\{\mathrm{\hspace{0.25em}1},\mathrm{\dots},p1\}$ into pairs $\{c,d\}$ such that$cd\equiv a$. Then $c$ and $d$ must always be distinct since $a$ is a nonresidue. Hence, the product^{} of the union of the partitions is:
$$(p1)!\equiv {a}^{(p1)/2}\equiv 1$$ and the result follows by Wilson’s Theorem.
 Proof (b)

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

Canonical name  ProofOfEulersCriterion 
Date of creation  20130322 12:41:53 
Last modified on  20130322 12:41:53 
Owner  Koro (127) 
Last modified by  Koro (127) 
Numerical id  7 
Author  Koro (127) 
Entry type  Proof 
Classification  msc 11A15 