Past exam of the mathematics course of the University of Cambridge / 2003 / ia / Paper 4 / 6C / i / Solution

For a prime number $p$, every nonzero residue class has a unique multiplicative inverse modulo $p$: Bezout identity supplies one because its representative is coprime to $p$, and cancellation modulo a prime gives uniqueness. Pair each residue with its inverse. The only unpaired residues satisfy $a^2\equiv 1$, so $p\mid (a-1)(a+1)$; the Euclid lemma gives $a\equiv 1$ or $-1$. For odd $p$, these are distinct. Every other pair contributes one to the product of all nonzero residues, leavingFor $p=2$, $1!\equiv -1(\mathrm{mod}2)$ as well. This proves Wilson theorem in all cases.

For an odd prime, set $q=(p-1)/2$. Pair the upper half of the factorial with the negatives of the lower half:If $p\equiv 1(\mathrm{mod}4)$, then $q$ is even. ThereforeThis constructs a square root of minus one modulo a prime explicitly.