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 observed,

In the multiplication tables for prime p's, 1 always appears in the upper left and lower right corners and nowhere else on the main diagonal.

In algebraic terms this fact is expressed as

Equation n² ≡ 1 (mod p) has, for a prime p, two and only two solutions: n = 1 and n = p -1.

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,

[(p -1)!]_p = [1]_p·[2]_p·[3]_p· ... ·[p-1]_p = [1]_p·[p-1]_p = [p-1]_p

which is most often written as

(p - 1)! ≡ -1 (mod p)

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

If n > 4 is a composite integer then (n - 1)! ≡ 0 (mod n).

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, 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.

(A combinatorial proof of Wilson's theorem can be found elsewhere.)

References

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

71942494