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 ${\displaystyle (n-1)!=1\times 2\times 3\times \cdots \times (n-1)}$ satisfies

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

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.^[1]

History

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

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.) The background color is blue for prime values of n, gold for composite values.

Table of factorial and its remainder modulo n

${\displaystyle n}$	${\displaystyle (n-1)!}$ (sequence A000142 in the OEIS)	${\displaystyle (n-1)!\ {\bmod {\ }}n}$ (sequence A061006 in the OEIS)
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

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

Composite modulus

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

In fact, more is true. With the sole exception of the case ${\displaystyle n=4}$, where ${\displaystyle 3!=6\equiv 2{\pmod {4}}}$, if ${\displaystyle n}$ is composite then ${\displaystyle (n-1)!}$ is congruent to 0 modulo ${\displaystyle n}$. The proof can be divided into two cases: First, if ${\displaystyle n}$ can be factored as the product of two unequal numbers, ${\displaystyle n=ab}$, where ${\displaystyle 2\leq a<b<n}$, then both ${\displaystyle a}$ and ${\displaystyle b}$ will appear as factors in the product ${\displaystyle (n-1)!=(n-1)\times (n-2)\times \cdots \times 2\times 1}$ and so ${\displaystyle (n-1)!}$ is divisible by ${\displaystyle ab=n}$. If ${\displaystyle n}$ has no such factorization, then it must be the square of some prime ${\displaystyle q}$ larger than 2. But then ${\displaystyle 2q<q^{2}=n}$, so both ${\displaystyle q}$ and ${\displaystyle 2q}$ will be factors of ${\displaystyle (n-1)!}$, and so ${\displaystyle n}$ divides ${\displaystyle (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).^[6]

Elementary proof

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

For example, for ${\displaystyle p=11}$, one has $${\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.

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, and much faster primality tests are known (indeed, even trial division is considerably more efficient).^{[citation needed]}

Used in the other direction, to determine the primality of the successors of large factorials, it is indeed a very fast and effective method. This is of limited utility, however.^{[citation needed]}

Quadratic residues

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 this, suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that (m!)² 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^{[7][non-primary source needed]} that $${\displaystyle \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 represents an odd prime and ${\displaystyle \alpha }$ 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

• Wilson prime
• Table of congruences
• Agoh–Giuga conjecture