This site is supported by donations to The OEIS Foundation.

Wilson's theorem

Wilson's theorem concerns a relationship between factorials and prime numbers. Gottfried W. Leibniz knew of it before John Wilson and Edward Waring came along.

Theorem W1. (Wilson) The congruence ${\displaystyle (n-1)!\equiv -1\mod n}$ holds true if and only if ${\displaystyle n}$ is prime. Put another way, the number ${\displaystyle (n-1)!+1}$ is a multiple of ${\displaystyle n}$ only when ${\displaystyle n}$ is prime.

Proof. If ${\displaystyle n}$ is composite, then it has at least one prime factor ${\displaystyle 1. For ${\displaystyle n=4}$, we see that ${\displaystyle 3!\equiv 2\mod 4}$. For all higher composite ${\displaystyle n}$, we see that the number ${\displaystyle (n-1)!=\prod _{i=1}^{n-1}i}$ is a product that runs through every prime factor of ${\displaystyle n}$ as well as other composite numbers repeating a lot of those same prime factors, and therefore ${\displaystyle (n-1)!\equiv 0\mod n}$ not –1.[1]

The case of the prime number 2 is disposed of easily enough by examination, leaving us only the odd primes to concern ourselves with. We can also dispose of 3 by examination. The only divisors of an odd prime ${\displaystyle p}$ are 1 and itself, hence ${\displaystyle \gcd(j,p)=1}$ for all ${\displaystyle 1. For each ${\displaystyle j}$, there is precisely one integer ${\displaystyle 1 such that ${\displaystyle jk\equiv 1\mod p}$. This means that each integer from 2 to ${\displaystyle p-2}$ can be paired off such that their product is 1 more than a multiple of ${\displaystyle p}$, and therefore ${\displaystyle \prod _{i=2}^{p-2}i\equiv 1\mod p}$. This falls short of the factorial, as it leaves out the pair consisting of 1 and ${\displaystyle p-1}$, and we see that ${\displaystyle 1\times (p-1)\equiv -1\mod p}$, and therefore ${\displaystyle (p-1)!}$ satisfies the congruence specified by the theorem. □ [2]

So if we take a prime number, such as 7, we will find that the factorial of the number one less than that prime is one less than a multiple of that prime, such as is the case with 6! + 1 = 721, which is 103 times 7 (see A060371 and A007619).

There are of course many ways to prove the theorem. Decades ago, Bolker gave a proof using the algebra of polynomials and invoking Fermat's little theorem.[3]

1. Some textbooks state the theorem in reference to prime numbers only, and thus don't bother to prove the relationship doesn't hold for composite ${\displaystyle n}$.
2. Ivan Niven & Herbert S. Zuckerman, An Introduction to the Theory of Numbers. New York: John Wiley & Sons (1980): p. 34, Theorem 2.10. The proof given concerns itself only with ${\displaystyle p}$ prime.