= 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\equiv1$, so $p\mid(a-1)(a+1)$; the <Euclid lemma> gives $a\equiv1$ or $-1$. For odd $p$, these are distinct. Every other pair contributes one to the product of all nonzero residues, leaving
$$
(p-1)!\equiv1\cdot(-1)\equiv-1\pmod p.
$$
For $p=2$, $1!\equiv-1\pmod2$ 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:
$$
(p-1)!=q!\prod_{r=1}^q(p-r)\equiv(-1)^q(q!)^2\pmod p.
$$
If $p\equiv1\pmod4$, then $q$ is even. Therefore
$$
\boxed{\left[\left(\frac{p-1}{2}\right)!\right]^2\equiv-1\pmod p}.
$$
This constructs a <square root of minus one modulo a prime> explicitly.
Back to article page
