Wilson's theorem


In 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, the factorial satisfies
exactly when n is a prime number. In other words, any number n is a prime number if, and only if, ! + 1 is divisible by n.

History

This theorem was stated by Ibn al-Haytham, and, in the 18th century, by 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

For each of the values of n from 2 to 30, the following table shows the number ! and the remainder when ! is divided by n.
The background color is blue for prime values of n, gold for composite values.


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

Both of the proofs below use 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. If were congruent to then it would also be congruent to −1. But ! ≡ 0 .
In fact, more is true. With the sole exception of 4, where 3! = 6 ≡ 2 , if n is composite then ! is congruent to 0. The proof is divided into two cases: First, if n can be factored as the product of two unequal numbers,, where 2 ≤ a < b ≤ n − 2, then both a and b will appear in the product and ! 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 !, and again n divides !.

Prime modulus

; Elementary proof
The result is trivial when, so assume p is an odd prime,. Since the residue classes 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 are . Therefore, with the exception of ±1, the factors of can be arranged in unequal pairs, where the product of each pair is. This proves Wilson's theorem.
For example, if,
; Proof using Fermat's little theorem
Again, the result is trivial for p = 2, so suppose p is an odd prime,. Consider the polynomial
g has degree, leading term, and constant term. Its roots are 1, 2,...,.
Now consider
h also has degree and leading term. Modulo p, Fermat's little theorem says it also has the same roots, 1, 2,...,.
Finally, consider
f has degree at most p − 2, and modulo p also has the roots 1, 2,...,. But Lagrange's theorem says it cannot have more than p − 2 roots. Therefore, f must be identically zero, so its constant term is. 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 has exactly elements of order p, namely the p-cycles. On the other hand, each Sylow p-subgroup in is a copy of. Hence it follows that the number of Sylow p-subgroups is. The third Sylow theorem implies
Multiplying both sides by gives
that is, the result.

Applications

Primality tests

In practice, Wilson's theorem is useless as a primality test because computing ! modulo n for large n is computationally complex, and much faster primality tests are known.

Quadratic residues

Using Wilson's Theorem, for any odd prime, we can rearrange the left hand side of
to obtain the equality
This becomes
or
We can use this fact to prove part of a famous result: for any prime p such that p ≡ 1 , the number is a square mod p. For suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that 2 is congruent to.

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

proved that
where p represents an odd prime and 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. In the latter case, the product of all elements equals a.