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 quadraticnon-residue. We can proceed in two ways:

  Proof (a)

  Partition the set $\{\mathrm{\hspace{0.25em}1},\mathrm{\dots },p-1\}$ intopairs $\{c,d\}$ such that$cd\equiv a$. Then $c$ and $d$ mustalways be distinct since $a$ is a non-residue. Hence, the product ofthe 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.