Wilson's theorem

If n is composite it is divisible by some prime number q, where 2 ≤ q ≤ n − 2. Because ${\displaystyle q}$ divides ${\displaystyle n}$, let ${\displaystyle n=qk}$ for some integer ${\displaystyle k}$. Suppose for the sake of contradiction that (n − 1)! were congruent to −1 (mod n) where n is composite. Then (n-1)! would also be congruent to −1 (mod q) as ${\displaystyle (n-1)!\equiv -1\ ({\text{mod}}\ n)}$ implies that ${\displaystyle (n-1)!=nm-1=(qk)m-1=q(km)-1}$ for some integer ${\displaystyle m}$ which shows (n-1)! being congruent to -1 (mod q). But (n − 1)! ≡ 0 (mod q) by the fact that q is a term in (n-1)! making (n-1)! a multiple of q. A contradiction is now reached.

In fact, more is true. With the sole exception of 4, where 3! = 6 ≡ 2 (mod 4), if n is composite then (n − 1)! is congruent to 0 (mod n). The proof is divided into two cases: First, if n can be factored as the product of two unequal numbers, n = ab, where 2 ≤ a < b ≤ n − 2, then both a and b will appear in the product 1 × 2 × ... × (n − 1) = (n − 1)! and (n − 1)! will be divisible by n. If n has no such factorization, then it must be the square of some prime q, q > 2. But then 2q < q² = n, both q and 2q will be factors of (n − 1)!, and again n divides (n − 1)!.

Elementary proof

The result is trivial when p = 2, so assume p is an odd prime, p ≥ 3. Since the residue classes (mod p) are a field, every non-zero a has a unique multiplicative inverse, a⁻¹. Lagrange's theorem implies that the only values of a for which a ≡ a⁻¹ (mod p) are a ≡ ±1 (mod p) (because the congruence a² ≡ 1 can have at most two roots (mod p)). Therefore, with the exception of ±1, the factors of (p − 1)! can be arranged in unequal pairs,[7] where the product of each pair is ≡ 1 (mod p). This proves Wilson's theorem.

For example, if p = 11,

${\displaystyle 10!=[(1\cdot 10)]\cdot [(2\cdot 6)(3\cdot 4)(5\cdot 9)(7\cdot 8)]\equiv [-1]\cdot [1\cdot 1\cdot 1\cdot 1]\equiv -1{\pmod {11}}.}$

Proof using Fermat's little theorem

Again, the result is trivial for p = 2, so suppose p is an odd prime, p ≥ 3. Consider the polynomial

${\displaystyle g(x)=(x-1)(x-2)\cdots (x-(p-1)).}$

g has degree p − 1, leading term x^{p − 1}, and constant term (p − 1)!. Its p − 1 roots are 1, 2, ..., p − 1.

Now consider

${\displaystyle h(x)=x^{p-1}-1.}$

h also has degree p − 1 and leading term x^{p − 1}. Modulo p, Fermat's little theorem says it also has the same p − 1 roots, 1, 2, ..., p − 1.

Finally, consider

${\displaystyle f(x)=g(x)-h(x).}$

f has degree at most p − 2 (since the leading terms cancel), and modulo p also has the p − 1 roots 1, 2, ..., p − 1. But Lagrange's theorem says it cannot have more than p − 2 roots. Therefore, f must be identically zero (mod p), so its constant term is (p − 1)! + 1 ≡ 0 (mod p). This is Wilson's theorem.

Proof using the Sylow theorems

It is possible to deduce Wilson's theorem from a particular application of the Sylow theorems. Let p be a prime. It is immediate to deduce that the symmetric group ${\displaystyle S_{p}}$ has exactly ${\displaystyle (p-1)!}$ elements of order p, namely the p-cycles ${\displaystyle C_{p}}$. On the other hand, each Sylow p-subgroup in ${\displaystyle S_{p}}$ is a copy of ${\displaystyle C_{p}}$. Hence it follows that the number of Sylow p-subgroups is ${\displaystyle n_{p}=(p-2)!}$. The third Sylow theorem implies

${\displaystyle (p-2)!\equiv 1{\pmod {p}}.}$

Multiplying both sides by (p − 1) gives

${\displaystyle (p-1)!\equiv p-1\equiv -1{\pmod {p}},}$

that is, the result.

In practice, Wilson's theorem is useless as a primality test because computing (n − 1)! modulo n for large n is computationally complex, and much faster primality tests are known (indeed, even trial division is considerably more efficient).

Using Wilson's Theorem, for any odd prime p = 2m + 1, we can rearrange the left hand side of

${\displaystyle 1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}}$

to obtain the equality

${\displaystyle 1\cdot (p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv \ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv \ -1{\pmod {p}}.}$

This becomes

${\displaystyle \prod _{j=1}^{m}\ j^{2}\ \equiv (-1)^{m+1}{\pmod {p}}}$

or

${\displaystyle (m!)^{2}\equiv (-1)^{m+1}{\pmod {p}}.}$

We can use this fact to prove part of a famous result: for any prime p such that p ≡ 1 (mod 4), the number (−1) is a square (quadratic residue) mod p. For suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that (m!)² is congruent to (−1).

Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.

Wilson's theorem allows one to define the p-adic gamma function.