Ibn al-Haytham · John Wilson · Joseph-Louis Lagrange
\[(p-1)!\]
\[p\ \text{is prime}\iff (p-1)!+1\equiv 0 \pmod{p}\]
Wilson's theorem is an exact primality criterion : an integer \(p>1\) is prime if and only if \((p-1)!+1\) is a multiple of \(p\). For example \(4!+1=25=5^2\) is a multiple of \(5\), so \(5\) is prime ; but \(5!+1=121\) is not a multiple of \(6\), so \(6\) is composite. Unlike Fermat's little theorem, Wilson's test has no liars : no composite number ever satisfies it, so the Carmichael numbers that fool Fermat are all caught here. The cost is practical, not logical : evaluating \((p-1)!\bmod p\) takes \(p-1\) multiplications, far heavier than the fast modular exponentiation of Fermat, so the theorem is prized for its beauty rather than used for large numbers.
The result carries the name of John Wilson (1741–1793), an English judge, to whom it was attributed by Edward Waring in 1770. Yet Wilson neither was the first to state it nor ever proved it. The congruence had already been given by the Arab mathematician Ibn al-Haytham (Alhazen) around the year 1000, and the first rigorous proof was supplied by Joseph-Louis Lagrange in 1771. It is a classic case of Stigler's law of eponymy : a theorem rarely bears the name of its true discoverer.
A000040 The primes : exactly the \(p>1\) with \((p-1)!\equiv -1 \pmod p\).
A007619 Wilson quotients : \(\big((p-1)!+1\big)/p\) for successive primes \(p\).
# Wilson's theorem : an exact primality test
def wilson(p):
return p > 1 and factorial(p-1) % p == p-1 # (p-1)! = -1 mod p
print [p for p in range(2, 30) if wilson(p)] # 2,3,5,7,11,13,17,19,23,29
print [n for n in range(2, 30) if not wilson(n)] # the composites
# No composite ever passes (unlike Fermat) : Carmichael 561 is caught
print wilson(561) # False
\[(p-1)!\equiv -1 \pmod{p^{2}}\qquad\Rightarrow\qquad p\in\{5,\ 13,\ 563,\ \ldots\}\]
A prime is a Wilson prime when the congruence holds not just modulo \(p\) but modulo \(p^{2}\). Only three are known : \(5,\ 13,\ 563\). Despite searches past \(2\times 10^{13}\), no fourth has appeared, yet it is conjectured there are infinitely many — they are simply extraordinarily rare. This is the deep water behind a shallow-looking test.
A007540 Wilson primes : \((p-1)!\equiv -1 \pmod{p^{2}}\).
# Wilson primes : the congruence holds modulo p^2
def wilson_prime(p):
return is_prime(p) and (factorial(p-1)+1) % (p*p) == 0
print [p for p in primes(1000) if wilson_prime(p)] # 5, 13, 563
# None between 563 and, say, 50000 -- they are extraordinarily rare
print [p for p in primes(563+1, 50000) if wilson_prime(p)] # []