Wilson's Theorem

Wilson's Theorem is another consequence (Fermat's Little Theorem being one) of the Euclid's Proposition VII.30. As we have noticed,

In algebraic terms this fact is expressed as

Indeed, n² = 1 (mod p) implies that p|(n² - 1), or p|(n - 1)(n + 1). By the Proposition VII.30 either p|(n - 1) in which case n = 1 (mod p), or p|(n + 1) and then n = p -1 (mod p).

Now, as we already remarked, multiplication by [a]_p permutes the set {[1]_p, [2]_p, [3]_p, ... [p-1]_p}. This means that for every [a] different from either [1] or [p-1] there exists [b] ≠ [a] such that [a][b] = [1]. The significance of the fact that [b] ≠ [a] lies in that all classes from {[2]_p, [3]_p, ..., [p-2]_p} can be split into pairs whose product is [a][b] = [1]. Therefore,

which is most often written as

Yet another way of writing it is p|(1·2·3·...·(p -1) + 1) which simply says that (p -1)! + 1 is divisible by p and is reminiscent of the Euclid's proof of the infinitude of primes. In fact this is how the theorem (a conjecture at the time) first appeared in the first edition (1770) of Meditationes Algebraicae by Edward Waring. Waring ascribed the result to a student of his John Wilson. Waring gave a proof of the theorem in the third edition of Meditationes Algebraicae in 1782. However the first published proof was given by J. L. Lagrange yet in 1770 [Hilton, p. 41, Ore, p. 259].

For composite moduli, the Wilson's formula fails. Instead we have

Assuming n = PQ, where P ≤Q and each greater than 1, we note that both P and Q appear as multiples in (n - 1)! which is, therefore, is divisible by n. If P = Q, then n = P² and 1 < P < 2P < P² = n provided n>4.

Thus, at least in principle, Wilson's Theorem can be used to establish primality of a given number.

References

1. J. H. Conway and R. K. Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
2. H. Davenport, The Higher Arithmetic, Harper&Brothers, NY
3. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
4. P. Hilton, D. Holton, J. Pederson, Mathematical Reflections, Springer Verlag, 1997
5. R. Honsberger, Mathematical Gems II, MAA, 1976
6. O. Ore, Number Theory and Its History, Dover Publications, 1976

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny