# Wilson's theorem

In number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if

$(n-1)!\ \equiv \ -1{\pmod {n}}$ .

That is, it asserts that the factorial $(n-1)!=1\times 2\times 3\times \cdots \times (n-1)$ is one less than a multiple of n exactly when n is a prime number.

## History

This theorem was stated by Ibn al-Haytham (c. 1000 AD), and John Wilson. Edward Waring announced the theorem in 1770, although neither he nor his student Wilson could prove it. Lagrange gave the first proof in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.

## Example

The following table shows the values of n from 2 to 30, (n − 1)!, and the remainder when (n − 1)! is divided by n. (In the notation of modular arithmetic, the remainder when m is divided by n is written m mod n.) The background color is blue for prime values of n, gold for composite values.

Table of remainder modulo n
$n$ $(n-1)!$ $(n-1)!\ {\bmod {\ }}n$ 2 1 1
3 2 2
4 6 2
5 24 4
6 120 0
7 720 6
8 5040 0
9 40320 0
10 362880 0
11 3628800 10
12 39916800 0
13 479001600 12
14 6227020800 0
15 87178291200 0
16 1307674368000 0
17 20922789888000 16
18 355687428096000 0
19 6402373705728000 18
20 121645100408832000 0
21 2432902008176640000 0
22 51090942171709440000 0
23 1124000727777607680000 22
24 25852016738884976640000 0
25 620448401733239439360000 0
26 15511210043330985984000000 0
27 403291461126605635584000000 0
28 10888869450418352160768000000 0
29 304888344611713860501504000000 28
30 8841761993739701954543616000000 0

## Proofs

Both of the proofs (for prime moduli) below make use of the fact that the residue classes modulo a prime number are a field—see the article prime field for more details. Lagrange's theorem, which states that in any field a polynomial of degree n has at most n roots, is needed for both proofs.

### Composite modulus

If n is composite it is divisible by some prime number q, where 2 ≤ qn − 2. If (n − 1)! were congruent to −1 (mod n) then it would also be congruent to −1 (mod q). But (n − 1)! ≡ 0 (mod q).

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 < q2 = n, both q and 2q will be factors of (n − 1)!, and again n divides (n − 1)!.

### Prime modulus

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−1. Lagrange's theorem implies that the only values of a for which aa−1 (mod p) are a ≡ ±1 (mod p) (because the congruence a2 ≡ 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, where the product of each pair is ≡ 1 (mod p). This proves Wilson's theorem.

For example, if p = 11,

$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

$g(x)=(x-1)(x-2)\cdots (x-(p-1)).\,$ g has degree p − 1, leading term xp − 1, and constant term (p − 1)!. Its p − 1 roots are 1, 2, ..., p − 1.

Now consider

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

Finally, consider

$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 (p − 1)! + 1 ≡ 0 (mod p). This is Wilson's theorem.

Proof using Sylow theorem

It is possible to deduce Wilson theorem from a particular application of Sylow theorem. Let p be a prime and consider the symmetric group $S_{p}$ . It is immediate to deduce that there are exactly $(p-1)!$ elements of order p, namely the p-cycles. On the other hand each p-Sylow subgroup in $S_{p}$ is a copy of $C_{p}$ , hence it follows that the number of p-Sylow is $n_{p}=(p-2)!$ . The Sylow theorem implies

$(p-2)!\equiv 1\mod p,$ and multiplying both sides by p-1 gives

$(p-1)!\equiv p-1\equiv -1\mod p,$ that is the result.

## Applications

Wilson's theorem is useless as a primality test in practice, since computing (n − 1)! modulo n for large n is hard, and far easier 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

$1\cdot 2\cdots (p-1)\ \equiv \ -1\ {\pmod {p}}$ to obtain the equality

$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

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

$(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!)2 is congruent to (−1).

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

## Gauss's generalization

Gauss proved that if m > 2

$\prod _{k=1 \atop \gcd(k,m)=1}^{m}\!\!k\ \equiv {\begin{cases}-1{\pmod {m}}&{\text{if }}m=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {m}}&{\text{otherwise}}\end{cases}}$ where p is an odd prime, and $\alpha$ is a positive integer. The values of m for which the product is −1 are precisely the ones where there is a primitive root modulo m.

This further generalizes to the fact that in any finite abelian group, either the product of all elements is the identity, or there is precisely one element a of order 2 (but not both). In the latter case, the product of all elements equals a.