In mathematics, Wilson's theorem states that p is a prime number if and only if

$(p-1)!\backslash \; \backslash equiv\backslash \; -1\backslash \; (\backslash mbox\{mod\}\backslash \; p)$

(see factorial and modular arithmetic for the notation).

History

The theorem was first discovered by Ibn al-Haytham (also known as Alhazen), but it is named after John Wilson (a student of the English mathematician Edward Waring) who rediscovered it more than 700 years later. Waring announced the theorem in 1770, although neither he nor Wilson could prove it. Lagrange gave the first proof in 1773. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.

Proofs

First proof

This proof uses the fact that if p is an odd prime, then the set of numbers G = (Z/pZ)^× = {1, 2, ... p − 1} forms a group under multiplication modulo p. This means that for each element a in G, there is a unique inverse element b in G such that ab ≡ 1 (mod p). If a ≡ b (mod p), then a² ≡ 1 (mod p), which forces a² − 1 = (a + 1)(a − 1) ≡ 0 (mod p), and since p is prime, this forces a ≡ 1 or −1 (mod p), i.e. a = 1 or a = p − 1.

In other words, 1 and p − 1 are each their own inverse, but every other element of G has a distinct inverse, and so if we collect the elements of G pairwise in this fashion and multiply them all together, we get the product −1. For example, if p = 11, we have

$10!\; =\; 1(10)(2\; \backslash cdot\; 6)(3\; \backslash cdot\; 4)(5\; \backslash cdot\; 9)(7\; \backslash cdot\; 8)\; \backslash \; \backslash equiv\backslash \; -1\backslash \; (\backslash mbox\{mod\}\backslash \; 11).\backslash ,$

If p = 2, the result is trivial to check.

For a converse (but see below for a more exact converse result), suppose the congruence holds for a composite n, and note that then n has a proper divisor d with 1 < d < n. Clearly, d divides (n − 1)! But by the congruence, d also divides (n − 1)! + 1, so that d divides 1, a contradiction.

Second proof

Here is another proof of the first direction: Suppose p is an odd prime. Consider the polynomial

$g(x)=(x-1)(x-2)\; \backslash cdots\; (x-(p-1)).\backslash ,$

Recall that if f(x) is a nonzero polynomial of degree d over a field F, then f(x) has at most d roots over F. Now, with g(x) as above, consider the polynomial

$f(x)=g(x)-(x^\{p-1\}-1).\backslash ,$

Since the leading coefficients cancel, we see that f(x) is a polynomial of degree at most p − 2. Reducing mod p, we see that f(x) has at most p − 2 roots mod p. But by Fermat's little theorem, each of the elements 1, 2, ..., p − 1 is a root of f(x). This is impossible, unless f(x) is identically zero mod p, i.e. unless each coefficient of f(x) is divisible by p.

But since p is odd, the constant term of f(x) is just (p − 1)! + 1, and the result follows.

Applications

Wilson's theorem is useless as a primality test, since computing (n − 1)! is difficult for large n.

Using Wilson's Theorem, we have for any prime p:

$1\backslash cdot\; 2\backslash cdots\; (p-1)\backslash \; \backslash equiv\backslash \; -1\backslash \; (\backslash mbox\{mod\}\backslash \; p)$

$1\backslash cdot(p-1)\backslash cdot\; 2\backslash cdot\; (p-2)\backslash cdots\; m\backslash cdot\; (p-m)\backslash \; \backslash equiv\backslash \; 1\backslash cdot\; (-1)\backslash cdot\; 2\backslash cdot\; (-2)\backslash cdots\; m\backslash cdot\; (-m)\backslash \; \backslash equiv\backslash \; -1\backslash \; (\backslash mbox\{mod\}\backslash \; p)$

where p = 2m + 1. This becomes

$\backslash prod\_\{j=1\}^m\backslash \; j^2\backslash \; \backslash equiv(-1)^\{m+1\}\backslash \; (\backslash mbox\{mod\}\backslash \; p).$

And so primality is determined by the quadratic residues of p. We can use this fact to prove part of a famous result: −1 is a square (quadratic residue) mod p if p ≡ 1 (mod 4). For suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that

$\backslash left(\; \backslash prod\_\{j=1\}^\{2k\}\backslash \; j\; \backslash right)^\{2\}\; =\; \backslash prod\_\{j=1\}^\{2k\}\backslash \; j^2\backslash \; \backslash equiv\; (-1)^\{2k+1\}\backslash \; =\; -1(\backslash mbox\{mod\}\backslash \; p).$

Generalization

There is also a generalization of Wilson's theorem, due to Carl Friedrich Gauss:

where p is an odd prime.

Converse

The converse to Wilson's theorem states that for a composite number n > 5,

n divides (n − 1)!.

This leaves the case n = 4, for which 3! is congruent to 2 modulo 4.

In fact if q is a prime factor of n, so that n = qa, the numbers

1, 2, ..., n − 1

include a − 1 multiples of q. Therefore the power of q dividing the factorial is at least n/q − 1; and the power dividing n at most

log n/log q.

The required inequality

log n/log q ≤ n/q − 1

does hold in general, except for the case q = 2 and n = 4.

Modular arithmetic Prime numbers | Factorial and binomial topics | Mathematical theorems

Теорема на Уилсън | Wilsonova věta | Satz von Wilson | Teorema de Wilson | Théorème de Wilson | 윌슨의 정리 | Teorema di Wilson | Wilson-tétel | Stelling van Wilson | ウィルソンの定理 | Teorema de Wilson | Wilsons sats | ทฤษฎีบทของวิลสัน | 威尔逊定理