Wilson's theorem: Definition from Answers.com

In mathematics, Wilson's theorem states that a natural number n > 1 is a prime number if and only if

$(n-1)!\ \equiv\ -1\ (\mbox{mod}\ n)$

(see factorial and modular arithmetic for the notation).

1 History
2 Proofs
- 2.1 First proof
- 2.2 Second proof
3 Applications
4 Generalizations
- 4.1 A simple generalization
- 4.2 Gauss's generalization
5 See also
6 Notes
7 References
8 External links

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.^[2] 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 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 \cdot 6)(3 \cdot 4)(5 \cdot 9)(7 \cdot 8) \ \equiv\ -1\ (\mbox{mod}\ 11).\,$

The commutative and associative properties are used in above procedure. All elements in the above product will be of the form g g ⁻¹ ≡ 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

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

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

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

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 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, for any odd prime p = 2m + 1 we can rearrange the left hand side of

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

to obtain the equality

$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).$

This becomes

$\prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1}\ (\mbox{mod}\ p).$

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

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

Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.

Generalizations

A simple generalization

Wilson's theorem can be generalized to the following statement:

$\forall n\in\mathbb{N}: (n-1)! ~\bmod~ n = \begin{cases} -1 & \gets n \text{ is prime} \\ 2 & \gets n=4 \\ 0 & \text{otherwise} \end{cases}$

From the above proofs we already know that for prime n we have $(n-1)!\equiv -1 \pmod n$

We can easily verify the cases n=1 and n=4 by hand. Which leaves us with the case where n is a composite number larger than 5. In this case the above statement claims that n divides (n-1)!. We will now prove this.

Note that by definition

$(n-1)! = 1\times 2 \times \cdots \times (n-1)$

We will show that we can always find two of these n-1 terms such that their product is divisible by n.

In most cases, a composite n > 5 has a divisor a such that 2 ≤ a < (n/a). In such case, the two terms are a and (n/a). The only case when no such a exists is if n is a square of a prime p>2. In this case, the two terms are p and 2p.

Gauss's generalization

The following is a stronger generalization of Wilson's theorem, due to Carl Friedrich Gauss:

$\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.$

where p is an odd prime, and $α$ 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.

Notes

^ O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Haytham.html .
^ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers," Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, vol. 2, pages 125-137 (1771). (Note: Lagrange proved Wilson's theorem in 1773. In 1773, when the Berlin Academy finally published its Mémoires for 1771, Lagrange's proof was simply inserted in the Mémoires for 1771. See footnote [2] on page 499 of: Leonard Euler; A. P. Juskevic and R. Taton (ed.s), Correspondence de Leonard Euler avec A. C. Clairaut, J. d'Alembert et J. L. Lagrange (Cambridge, Massachusetts: Birkhäuser, 1980) [in French].)

References

Ore, Oystein (1988). Number Theory and its History. Dover. pp. 259–271. ISBN 0-486-65620-9.

External links

Weisstein, Eric W., "Wilson's Theorem" from MathWorld.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	Comte Joseph Louis Lagrange
	Wilson quotient
	Agoh–Giuga conjecture

	What is the Pythagoran theorem? Read answer...
	What is Dini's Theorem? Read answer...
	The pythagorean theorem? Read answer...

	What is the least positive residue of 8910111213 modulo 7 using the wilson's theorem?
	What is the relationship between Gauss theorem stokes's theorem and green's theorem?
	What is the relationship between the Green's Theorem Divergence Theorem and Stoke's Theorem?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Wilson's theorem". Read more

Wilson's theorem

Contents