Wilson's Theorem History Proofs First Proof Second Proof

The theorem was first discovered by John Wilson , a student of the English mathematician Edward Waring. Waring announced the theorem in 1770, although neither could prove it. Lagrange gave the first proof in 1773. There is evidence that Leibniz was aware of the result a century earlier, but he never published it.

2 Proofs

2.1 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 i in G, there is a unique inverse j in G such that ij ≡ 1 (mod p). If i ≡ j (mod p), then i² ≡ 1 (mod p), which forces i² − 1 = (i + 1)(i − 1) ≡ 0 (mod p), and since p is prime, this forces i ≡ 1 or −1 (mod p), i.e. i = 1 or i = 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

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 (n − 1)! But by the congruence, d also divides (n − 1)! + 1, so that d divides 1, a contradiction.

2.2 Second proof

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 fieldIn abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication, and division (except division by zero) may be performed and the associative, commutative, and distributive rules hold, which are famil 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 p − 2. Reducing mod p, we see that f(x) has at most p − 2 roots mod p. But by Fermat's theoremFermat's little theorem states that if p is a prime number, then for any integer a : This means that if you take some number a multiply it by itself p times and subtract a the result is divisible by p (see modular arithmetic). It is often stated in the fo, 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.

3 Applications

Wilson's theorem is useless as a primality testA primality test is an algorithm for determining whether an input number is prime. Naive methods The simplest primality test is as follows: Given an input number n we see if each integer k from 2 to n-1 divides n''. If n is divisible by any k then n is co, since computing (n − 1)! 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 residueIn mathematics, a number q is called a quadratic residue modulo p if there exists an integer x such that: : Otherwise, q is called a quadratic non-residue . In effect, a quadratic residue modulo p is a number that has a square root in modular arithmetic ws 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

4 Generalization

There is also a generalization of Wilson's theorem, due to Carl Friedrich GaussJohann Carl Friedrich Gauss (Gauss ( April 30, 1777 February 23, 1855) was a legendary German mathematician, astronomer and physicist with a very wide range of contributions; he is considered to be one of the greatest mathematicians of all time. His name:

where p is an odd prime.

<Hide>

Home > Wilson's theorem

1 History