Wilson's theorem
From Wikipedia Mirror
In mathematics, Wilson's theorem states that a natural number n > 1 is a prime number if and only if
- <math>(n-1)!\ \equiv\ -1\ (\mbox{mod}\ n)</math>
(see factorial and modular arithmetic for the notation).
Contents |
History
The theorem was first discovered by Bhaskara I, and later explained by Ibn al-Haytham (known as Alhazen in Medieval Europe) circa 1000 AD, but it is named after John Wilson (a student of the English mathematician Edward Waring) who stated it in the 18th century.[1] Waring announced the theorem in 1770, although neither he nor Wilson could prove it. Lagrange gave the first proof in 1773.[1] 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 a 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 a2 ≡ 1 (mod p), which forces a2 − 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
- <math>10! = 1(10)(2 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11).\,</math>
The commutative and associative properties are used in above procedure. All elements in the above product will be of the form g g −1 ≡ 1 (mod p) except 1 (p − 1) which is left.
If p = 2, the result is trivial to check.
To prove the converse (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 prime. Consider the polynomial
- <math>g(x)=(x-1)(x-2) \cdots (x-(p-1)).\,</math>
From Lagrange's theorem, 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
- <math>f(x)=g(x)-(x^{p-1}-1).\,</math>
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.
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.
Applications
Wilson's theorem is useless as a primality test in practice, since computing (n − 1)! modulo n for large n is hard, and far easier primality tests are known (indeed, even trial division is considerably more efficient).
Using Wilson's Theorem, we have for any prime p:
- <math>1\cdot 2\cdots (p-1)\ \equiv\ -1\ (\mbox{mod}\ p)</math>
- <math>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\ (\mbox{mod}\ p)</math>
where p = 2m + 1. This becomes
- <math>\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1}\ (\mbox{mod}\ p).</math>
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
- <math>\left( \prod_{j=1}^{2k}\ j \right)^{2} = \prod_{j=1}^{2k}\ j^2\ \equiv (-1)^{2k+1}\ = -1(\mbox{mod}\ p).</math>
Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.
Generalization
There is also a generalization of Wilson's theorem, due to Carl Friedrich Gauss:
- <math>\prod_{k = 1 \atop (k,m)=1}^{m} \!\!k \ \equiv \ \left \{ \begin{matrix} \ \ 0 \ (\mbox{mod } m) & \mbox{if } m=1 \\ -1\ (\mbox{mod }m) & \mbox{if } m=4,\;p^\alpha,\;2p^\alpha \\ \ \ 1\ (\mbox{mod }m) & \mbox{otherwise} \end{matrix} \right. </math>
where p is an odd prime, and <math>\alpha</math> is a positive integer. This further generalizes to the fact that in any finite abelian group, either the product of all elements is the identity, or there is precisely one element a of order 2. In the latter case, the product of all elements equals a.
See also
Notes
References
External links
ca:Teorema de Wilson cs:Wilsonova věta da:Wilsons sætning de:Satz von Wilson es:Teorema de Wilson fr:Théorème de Wilson ko:윌슨의 정리 it:Teorema di Wilson he:משפט וילסון lv:Vilsona teorēma hu:Wilson-tétel nl:Stelling van Wilson ja:ウィルソンの定理 pl:Twierdzenie Wilsona pt:Teorema de Wilson ro:Teorema lui Wilson ru:Теорема Вильсона fi:Wilsonin lause sv:Wilsons sats th:ทฤษฎีบทของวิลสัน uk:Теорема Вілсона vi:Định lý Wilson zh:威尔逊定理
