Wilson's theorem

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

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

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

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 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

$${\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}}.}$$

Gauss’ generalization of Wilson’s Theorem states that if ${\displaystyle n}$ is four, an odd prime power, or twice an odd prime power, then the product of relatively prime integers less than itself add one is divisible by ${\displaystyle n}$. It goes further to say that otherwise, the same product subtract one is divisible by ${\displaystyle n}$.

To state Gauss' Generalization of Wilson's Theorem, we use the Euler's totient function, denoted ${\displaystyle \varphi (n)}$, which is defined as the number of positive integers less than or equal to ${\displaystyle n}$ which are also relatively prime with ${\displaystyle n}$. Let's call such numbers ${\displaystyle a_{i}}$, where ${\displaystyle \gcd(a_{i},n)=1}$.

Gauss proved given an odd prime ${\displaystyle p}$ and some integer ${\displaystyle \alpha >0}$, then

${\displaystyle \prod _{k=1}^{\varphi (n)}\!\!a_{k}\ ={\begin{cases}-1{\pmod {n}}&{\text{if }}n=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {n}}&{\text{otherwise}}\end{cases}}}$.

First, let's note this is the proof for cases ${\displaystyle n>2}$, since the results are trivial for ${\displaystyle n=\{1,2\}}$.

For all ${\displaystyle a_{i}}$, we know there exist some ${\displaystyle a_{j}}$, where ${\displaystyle i\neq j}$ and ${\displaystyle \gcd(a_{j},n)=1}$, such that ${\displaystyle a_{i}a_{j}=1}$. This allows us to pair each of the elements together with its inverse. We are left now with ${\displaystyle a_{i}}$ being its own inverse. So in other words ${\displaystyle a_{i}}$ is a root of ${\displaystyle f(x)=x^{2}-1}$ in ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$, and ${\displaystyle f(x)=(x-1)(x+1)}$, in the polynomial ring ${\displaystyle \mathbb {Z} /n\mathbb {Z} [X]}$. If ${\displaystyle a_{i}}$ is a root, it follows that ${\displaystyle n-a_{i}}$ is also a root. Our objective is to show that the number of roots is divisible by four, unless ${\displaystyle n=4,n=p^{\alpha }}$, or ${\displaystyle n=2p^{\alpha }}$.

Let's consider ${\displaystyle n=2}$. Then we notice we have one root since ${\displaystyle 1\equiv -1{\pmod {2}}}$.

Consider ${\displaystyle n=4}$. Then, it is clear there are two roots, specifically, ${\displaystyle x\equiv 1{\pmod {4}}}$ and ${\displaystyle x\equiv -1{\pmod {4}}}$.

Say ${\displaystyle n=p^{\alpha }}$. It is again clear there are two solutions.

We now consider ${\displaystyle n=2^{\beta },\beta >2}$. If one of the factors of ${\displaystyle f(x)}$ is divisible by 2, so is the other. Take the factor ${\displaystyle (x+1)}$ to be divisible by ${\displaystyle 2^{1}}$. Then, it follows that there are 4 distinct roots of ${\displaystyle f(x)}$, namely ${\displaystyle x\equiv 1{\pmod {n}}}$, ${\displaystyle x\equiv 1+2^{\beta -1}{\pmod {n}}}$, ${\displaystyle x\equiv -1{\pmod {n}}}$, and ${\displaystyle x\equiv -1-2^{\beta -1}{\pmod {n}}}$, when ${\displaystyle n=2^{\beta },\beta >2}$.

Finally, let's look at the general case where ${\displaystyle n=2^{\beta }p_{1}{^{\gamma _{1}}}p_{2}{^{\gamma _{2}}}\dots p_{k}{^{\gamma _{k}}}}$. We find 2 roots of ${\displaystyle f(x)}$ over each ${\displaystyle \mathbb {Z} /2^{\beta }\mathbb {Z} }$ and ${\displaystyle \mathbb {Z} /p_{r}^{\gamma _{r}}\mathbb {Z} }$, except when ${\displaystyle \beta >2}$. Using the Chinese remainder theorem, we find that when ${\displaystyle n}$ is not divisible by 2, we have a total of ${\displaystyle 2^{k}}$ solutions of ${\displaystyle f(x)}$. Assuming ${\displaystyle \beta =1}$, in ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$, we have one root, so we still have a total of ${\displaystyle 2^{k}}$ solutions. When ${\displaystyle \beta =2}$, we have 2 roots in ${\displaystyle \mathbb {Z} /4\mathbb {Z} }$, so there are a total of ${\displaystyle 2^{k+1}}$ roots of ${\displaystyle f(x)}$. For all cases where ${\displaystyle \beta >2}$, there are 4 roots in ${\displaystyle \mathbb {Z} /2^{\beta }\mathbb {Z} }$ with a total of ${\displaystyle 2^{k+2}}$ solutions. This shows that the number of roots are divisible by 4, unless ${\displaystyle n=4,n=p^{\alpha }}$, or ${\displaystyle n=2p^{\alpha }}$.

Say ${\displaystyle a_{i}}$ is a root of ${\displaystyle f(x)}$ in ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$. Then ${\displaystyle a_{i}(n-a_{i})=-a_{i}^{2}=-1}$. So, if the number of roots of ${\displaystyle f(x)}$ is divisible by 4, then we can say the product of the roots if 1. Otherwise, we can say the product is -1. So we can conclude that

${\displaystyle \prod _{k=1}^{\varphi (n)}\!\!a_{k}\ ={\begin{cases}-1{\pmod {n}}&{\text{if }}n=4,\;p^{\alpha },\;2p^{\alpha }\\\;\;\,1{\pmod {n}}&{\text{otherwise}}\end{cases}}}$.

• Wilson prime
• Table of congruences

• "Wilson theorem", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Wilson's Theorem". MathWorld.
• Mizar system proof: http://mizar.org/version/current/html/nat_5.html#T22
• Ohana, Andrew. "A Generalization of Wilson's Theorem" (PDF).