Wilson's theorem

From HandWiki
Short description: Theorem on prime numbers

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is (using the notations of modular arithmetic), the factorial [math]\displaystyle{ (n - 1)! = 1 \times 2 \times 3 \times \cdots \times (n - 1) }[/math] satisfies

[math]\displaystyle{ (n-1)!\ \equiv\; -1 \pmod n }[/math]

exactly when n is a prime number. In other words, any integer n > 1 is a prime number if, and only if, (n − 1)! + 1 is divisible by n.[1]

History

This theorem was stated by Ibn al-Haytham (c. 1000 AD),[2] and, in the 18th century, by the English mathematician John Wilson.[3] Edward Waring announced the theorem in 1770, although neither he nor his student Wilson could prove it. Lagrange gave the first proof in 1771.[4] There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.[5]

Example

For each of the values of n from 2 to 30, the following table shows the number (n − 1)! and the remainder when (n − 1)! is divided by n. (In the notation of modular arithmetic, the remainder when m is divided by n is written m mod n.) The background color is blue for prime values of n, gold for composite values.

Table of factorial and its remainder modulo n
[math]\displaystyle{ n }[/math] [math]\displaystyle{ (n-1)! }[/math]
(sequence A000142 in the OEIS)
[math]\displaystyle{ (n-1)!\ \bmod\ n }[/math]
(sequence A061006 in the OEIS)
2 1 1
3 2 2
4 6 2
5 24 4
6 120 0
7 720 6
8 5040 0
9 40320 0
10 362880 0
11 3628800 10
12 39916800 0
13 479001600 12
14 6227020800 0
15 87178291200 0
16 1307674368000 0
17 20922789888000 16
18 355687428096000 0
19 6402373705728000 18
20 121645100408832000 0
21 2432902008176640000 0
22 51090942171709440000 0
23 1124000727777607680000 22
24 25852016738884976640000 0
25 620448401733239439360000 0
26 15511210043330985984000000 0
27 403291461126605635584000000 0
28 10888869450418352160768000000 0
29 304888344611713860501504000000 28
30 8841761993739701954543616000000 0

Proofs

The proofs (for prime moduli) below use the fact that the residue classes modulo a prime number are a finite field—see the article Prime field for more details.[6] Lagrange's theorem, which states that in any field a polynomial of degree n has at most n roots, is needed for all the proofs.

Composite modulus

If n is composite it is divisible by some prime number q, where 2 ≤ qn − 2. Because [math]\displaystyle{ q }[/math] divides [math]\displaystyle{ n }[/math], let [math]\displaystyle{ n = qk }[/math] for some integer [math]\displaystyle{ k }[/math]. Suppose for the sake of contradiction that [math]\displaystyle{ (n-1)! }[/math] were congruent to −1 (mod n) where n is composite. Then (n-1)! would also be congruent to −1 (mod q) as [math]\displaystyle{ (n-1)! \equiv -1 \ (\text{mod} \ n) }[/math] implies that [math]\displaystyle{ (n-1)! = nm - 1 = (qk)m - 1 = q(km) - 1 }[/math] for some integer [math]\displaystyle{ m }[/math] which shows (n-1)! being congruent to -1 (mod q). But (n − 1)! ≡ 0 (mod q) by the fact that q is a term in (n-1)! making (n-1)! a multiple of q. A contradiction is now reached.

In fact, more is true. With the sole exception of 4, where 3! = 6 ≡ 2 (mod 4), if n is composite then (n − 1)! is congruent to 0 (mod n). The proof is divided into two cases: First, if n can be factored as the product of two unequal numbers, n = ab, where 2 ≤ a < b ≤ n − 2, then both a and b will appear in the product 1 × 2 × ... × (n − 1) = (n − 1)! and (n − 1)! will be divisible by n. If n has no such factorization, then it must be the square of some prime q, q > 2. But then 2q < q2 = n, both q and 2q will be factors of (n − 1)!, and again n divides (n − 1)!.

Prime modulus

Elementary proof

The result is trivial when p = 2, so assume p is an odd prime, p ≥ 3. Since the residue classes (mod p) are a field, every non-zero a has a unique multiplicative inverse, a−1. Lagrange's theorem implies that the only values of a for which aa−1 (mod p) are a ≡ ±1 (mod p) (because the congruence a2 ≡ 1 can have at most two roots (mod p)). Therefore, with the exception of ±1, the factors of (p − 1)! can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo p. This proves Wilson's theorem.

For example, for p = 11, one has [math]\displaystyle{ 10! = [(1\cdot10)]\cdot[(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8)] \equiv [-1]\cdot[1\cdot1\cdot1\cdot1] \equiv -1 \pmod{11}. }[/math]

Proof using Fermat's little theorem

Again, the result is trivial for p = 2, so suppose p is an odd prime, p ≥ 3. Consider the polynomial

[math]\displaystyle{ g(x)=(x-1)(x-2) \cdots (x-(p-1)). }[/math]

g has degree p − 1, leading term xp − 1, and constant term (p − 1)!. Its p − 1 roots are 1, 2, ..., p − 1.

Now consider

[math]\displaystyle{ h(x)=x^{p-1}-1. }[/math]

h also has degree p − 1 and leading term xp − 1. Modulo p, Fermat's little theorem says it also has the same p − 1 roots, 1, 2, ..., p − 1.

Finally, consider

[math]\displaystyle{ f(x)=g(x)-h(x). }[/math]

f has degree at most p − 2 (since the leading terms cancel), and modulo p also has the p − 1 roots 1, 2, ..., p − 1. But Lagrange's theorem says it cannot have more than p − 2 roots. Therefore, f must be identically zero (mod p), so its constant term is (p − 1)! + 1 ≡ 0 (mod p). This is Wilson's theorem.

Proof using the Sylow theorems

It is possible to deduce Wilson's theorem from a particular application of the Sylow theorems. Let p be a prime. It is immediate to deduce that the symmetric group [math]\displaystyle{ S_p }[/math] has exactly [math]\displaystyle{ (p-1)! }[/math] elements of order p, namely the p-cycles [math]\displaystyle{ C_p }[/math]. On the other hand, each Sylow p-subgroup in [math]\displaystyle{ S_p }[/math] is a copy of [math]\displaystyle{ C_p }[/math]. Hence it follows that the number of Sylow p-subgroups is [math]\displaystyle{ n_p=(p-2)! }[/math]. The third Sylow theorem implies

[math]\displaystyle{ (p-2)! \equiv 1 \pmod p. }[/math]

Multiplying both sides by (p − 1) gives

[math]\displaystyle{ (p-1)! \equiv p-1 \equiv -1 \pmod p, }[/math]

that is, the result.

Applications

Primality tests

In practice, Wilson's theorem is useless as a primality test because computing (n − 1)! modulo n for large n is computationally complex, and much faster primality tests are known (indeed, even trial division is considerably more efficient).[citation needed]

Used in the other direction, to determine the primality of the successors of large factorials, it is indeed a very fast and effective method. This is of limited utility, however.[citation needed]

Quadratic residues

Using Wilson's Theorem, for any odd prime p = 2m + 1, we can rearrange the left hand side of [math]\displaystyle{ 1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod{p} }[/math] to obtain the equality [math]\displaystyle{ 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 \pmod{p}. }[/math] This becomes [math]\displaystyle{ \prod_{j=1}^m\ j^2\ \equiv(-1)^{m+1} \pmod{p} }[/math] or [math]\displaystyle{ (m!)^2 \equiv(-1)^{m+1} \pmod{p}. }[/math] 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 this, suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that (m!)2 is congruent to (−1) (mod p).

Formulas for primes

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

p-adic gamma function

Wilson's theorem allows one to define the p-adic gamma function.

Gauss' generalization

Gauss proved[7][non-primary source needed] that [math]\displaystyle{ \prod_{k = 1 \atop \gcd(k,m)=1}^m \!\!k \ \equiv \begin{cases} -1 \pmod{m} & \text{if } m=4,\;p^\alpha,\;2p^\alpha \\ \;\;\,1 \pmod{m} & \text{otherwise} \end{cases} }[/math] where p represents an odd prime and [math]\displaystyle{ \alpha }[/math] a positive integer. That is, the product of the positive integers less than m and relatively prime to m is one less than a multiple of m when m is equal to 4, or a power of an odd prime, or twice a power of an odd prime; otherwise, the product is one more than a multiple of m. The values of m for which the product is −1 are precisely the ones where there is a primitive root modulo m.

See also

Notes

  1. The Universal Book of Mathematics. David Darling, p. 350.
  2. O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Haytham.html .
  3. Edward Waring, Meditationes Algebraicae (Cambridge, England: 1770), page 218 (in Latin). In the third (1782) edition of Waring's Meditationes Algebraicae, Wilson's theorem appears as problem 5 on page 380. On that page, Waring states: "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger." (A man most illustrious and most skilled in mathematics, Squire John Wilson, found this most elegant property of prime numbers.)
  4. Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers" (Proof of a new theorem concerning prime numbers), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Berlin), vol. 2, pages 125–137 (1771).
  5. Giovanni Vacca (1899) "Sui manoscritti inediti di Leibniz" (On unpublished manuscripts of Leibniz), Bollettino di bibliografia e storia delle scienze matematiche ... (Bulletin of the bibliography and history of mathematics), vol. 2, pages 113–116; see page 114 (in Italian). Vacca quotes from Leibniz's mathematical manuscripts kept at the Royal Public Library in Hanover (Germany), vol. 3 B, bundle 11, page 10:

    Original : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:

    "Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?) si datus sit primitivus. Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem."

    Egli non giunse pero a dimostrarlo.

    Translation : In addition, he [Leibniz] also glimpsed Wilson's theorem, as shown in the following statement:

    "The product of all integers preceding the given integer, when divided by the given integer, leaves 1 (or the complement of 1?) if the given integer be prime. If the given integer be composite, it leaves a number which has a common factor with the given integer [which is] greater than one."

    However, he didn't succeed in proving it.

    See also: Giuseppe Peano, ed., Formulaire de mathématiques, vol. 2, no. 3, page 85 (1897).
  6. Landau, two proofs of thm. 78[full citation needed]
  7. Gauss, DA, art. 78

References

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

External links