(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 $\setof{1, \ldots, p - 1}$ into pairs $\setof{c, d}$ such that$c d \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.