Wilson's theorem

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is (using the notations of modular arithmetic), the factorial (n−1)!=1×2×3×⋯×(n−1) satisfies

(n−1)! ≡−1(modn)

exactly when n is a prime number. In other words, any integer n > 1 is a prime number if, and only if, (n − 1)! + 1 is divisible by n.

History

The theorem was first stated by Ibn al-Haytham c. 1000 AD. Edward Waring announced the theorem in 1770 without proving it, crediting his student John Wilson for the discovery. Lagrange gave the first proof in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but never published it.

Example

For each of the values of n from 2 to 30, the following table shows the number (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.) As expected, (n−1)! ≡n−1mod n when n is prime. The background color is blue for prime values of n, gold for composite values.

Table of factorial and its remainder modulo n
n(n−1)!
(sequence A000142 in the OEIS)
(n−1)! mod n
(sequence A061006 in the OEIS)
211
322
462
5244
61200
77206
850400
9403200
103628800
11362880010
12399168000
1347900160012
1462270208000
15871782912000
1613076743680000
172092278988800016
183556874280960000
19640237370572800018
201216451004088320000
2124329020081766400000
22510909421717094400000
23112400072777760768000022
24258520167388849766400000
256204484017332394393600000
26155112100433309859840000000
274032914611266056355840000000
28108888694504183521607680000000
2930488834461171386050150400000028
3088417619937397019545436160000000

Proofs

As a biconditional (if and only if) statement, the proof has two halves: to show that equality does not hold when n is composite, and to show that it does hold when n is prime.

Composite modulus

Suppose that n is composite. Therefore, it is divisible by some prime number q where 2≤q<n. Because q divides n, there is an integer k such that n=qk. Suppose for the sake of contradiction that (n−1)! were congruent to −1 modulo n. Then (n−1)! would also be congruent to −1 modulo q: indeed, if (n−1)!≡−1(modn) then (n−1)!=nm−1=(qk)m−1=q(km)−1 for some integer m, and consequently (n−1)! is one less than a multiple of q. On the other hand, since 2≤q≤n−1, one of the factors in the expanded product (n−1)!=(n−1)×(n−2)×⋯×2×1 is q. Therefore (n−1)!≡0(modq). This is a contradiction; therefore it is not possible that (n−1)!≡−1(modn) when n is composite.

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

Prime modulus

The first two proofs below use the fact that the residue classes modulo a prime number form a finite field (specifically, a prime field).

Elementary proof

The result is trivial when p=2, so assume p is an odd prime, p≥3. Since the residue classes modulo p form a field, every non-zero residue a has a unique multiplicative inverse a−1. Euclid's lemma implies that the only values of a for which a≡a−1(modp) are a≡±1(modp). Therefore, with the exception of ±1, the factors in the expanded form of (p−1)! can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo p. This proves Wilson's theorem.

For example, for p=11, one has 10!=[(1⋅10)]⋅[(2⋅6)(3⋅4)(5⋅9)(7⋅8)]≡[−1]⋅[1⋅1⋅1⋅1]≡−1(mod11).

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

Proof using elementary Group Theory

Let p be an odd prime. Let 𝔽p× denote the multiplicative group of integers modulo p, such that (p−1)!≡∏x∈𝔽p×xmodp. Since 𝔽p× is cyclic, there exists a group isomorphism φ:𝔽p×→ℤp−1, where ℤp−1 is the additive group of integers modulo p - 1. Therefore:

φ(∏x∈𝔽p×x)=∑x∈𝔽p×φ(x)=∑n∈ℤp−1n≡p(p−1)2mod(p−1)

Since p was an odd prime, p(p−1)2 has order 2 inside ℤp−1. Since isomorphisms preserve the orders of elements, it follows that φ−1(p(p−1)2)=∏x∈𝔽p×x also has order exactly 2. The only such element in 𝔽p× is p−1.

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 Sp has exactly (p−1)! elements of order p, namely the p-cycles Cp. On the other hand, each Sylow p-subgroup in Sp is a copy of Cp. Hence it follows that the number of Sylow p-subgroups is np=(p−2)!. The third Sylow theorem implies

(p−2)!≡1(modp).

Multiplying both sides by (p − 1) gives

(p−1)!≡p−1≡−1(modp),

that is, the result.

Applications

Primality tests

In practice, Wilson's theorem is useless as a primality test because computing (n − 1)! modulo n for large n is computationally complex.

Quadratic residues

Using Wilson's Theorem, for any odd prime p = 2m + 1, we can rearrange the left hand side of 1⋅2⋯(p−1) ≡ −1 (modp) to obtain the equality 1⋅(p−1)⋅2⋅(p−2)⋯m⋅(p−m) ≡ 1⋅(−1)⋅2⋅(−2)⋯m⋅(−m) ≡ −1(modp). This becomes ∏j=1m j2 ≡(−1)m+1(modp) or (m!)2≡(−1)m+1(modp). 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 this, 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) (mod p).

Formulas for primes

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

p-adic gamma function

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

Gauss's generalization

Gauss proved that ∏k=1gcd⁡(k,m)=1m−1k ≡{−1(modm)if m=4,pα,2pα1(modm)otherwise where p represents an odd prime and α a positive integer. That is, the product of the positive integers less than m and relatively prime to m is one less than a multiple of m when m is equal to 4, or a power of an odd prime, or twice a power of an odd prime; otherwise, the product is one more than a multiple of m. The values of m for which the product is −1 are precisely the ones where there is a primitive root modulo m.

See also