Wilson's Theorem states that a number n > 1 is prime if and only if:
This is proved using the fact that if p is an odd prime, then the numbers {1, 2, ... p1} form a group under multiplication modulo p. Therefore each number i in 2 ≤ i ≤ p2 has a unique "partner" (inverse) j such that 2 ≤ j ≤ p2 and ij is 1 mod p (1 is its own inverse, and so is p1, but no other element has this property, because p is prime.) As 1(p1) is 1 mod p, the result follows. If p = 2, the result is trivial to check. For the converse, 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 (n1)! But by the congruence, d also divides (n1)! + 1, so that d divides 1, a contradiction.
Here is another proof of the first direction: Suppose p is an odd prime. Consider the polynomial
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
Since the leading coefficients cancel, we see that f(x) is a polynomial of degree p2. Reducing mod p, we see that f(x) has at most p2 roots mod p. But by Fermat's theorem, each of the elements 1,2,...,p1 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 (p1)! + 1, and the result follows.
Wilson's theorem is useless as a primality test, since computing (n1)! is difficult for large n.
Using Wilson's Theorem, we have for any prime p:
where p = 2m + 1. This becomes:
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
There is also a generalization of Wilson's theorem, due to Gauss.
where p is an odd prime.
Search Encyclopedia

Featured Article

