Warning: mysql_numrows(): supplied argument is not a valid MySQL result resource in /home/kidsnetau/encyclopedia_content.txt on line 11

Encyclopedia > Wilson's theorem

  Article Content

Wilson's theorem

Wilson's Theorem in number theory 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 1771. There is evidence that Leibniz was aware of the result a century earlier, but he never published it.

Wilson's Theorem states that a number n > 1 is prime if and only if:

<math>(n-1)!\ \equiv\ -1\ (\mbox{mod}\ n)</math>

This is proved using the fact that if p is an odd prime, then the numbers {1, 2, ... p-1} form a group under multiplication modulo p. Therefore each number i in 2 ≤ ip-2 has a unique "partner" (inverse) j such that 2 ≤ jp-2 and ij is 1 mod p (1 is its own inverse, and so is p-1, but no other element has this property, because p is prime.) As 1(p-1) 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 (n-1)! But by the congruence, d also divides (n-1)! + 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

<math>g(x)=(x-1)(x-2) \cdots (x-(p-1))</math>

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

<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 p-2. Reducing mod p, we see that f(x) has at most p-2 roots mod p. But by Fermat's 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.

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:

<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>\prod_{j=1}^{2k}\ j^2\ =(\prod_{j=1}^{2k}\ j)^{2}\equiv(-1)^{2k+1}\ =-1(\mbox{mod}\ p)</math>

There is also a generalization of Wilson's theorem, due to Gauss.

<math>\prod_{1\leq a<m, \ (a,m)=1}a \equiv \{\begin{matrix} -1 (\mbox{mod }m) & \mbox{if } m=4,p^\alpha,2p^\alpha \\ 1(\mbox{mod }m) & \mbox{otherwise}\end{matrix} </math>

where p is an odd prime.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Jambres

... are names given to the magicians who contended with Moses and Aaron and were discomfited by the Hebrew leaders in the Hebrew Bible book of Exodus. These names were not ...