Wilson's theorem
Wilson's theorem is a fundamental result in number theory that characterizes prime numbers through modular arithmetic involving factorials: an integer n > 1 is prime if and only if (n-1)! \equiv -1 \pmod{n}, or equivalently, n divides (n-1)! + 1.[1][2] Named after the English mathematician John Wilson, the theorem was first stated by the 11th-century Persian mathematician Ibn al-Haytham (Alhazen), later known to Gottfried Wilhelm Leibniz, proposed by Wilson in a 1770 letter, and published by Edward Waring in Meditationes Algebraicae; Joseph-Louis Lagrange provided the first published proof in 1773.[1][3] The theorem holds trivially for the prime p = 2 since $1! = 1 \equiv -1 \pmod{2}, and for odd primes, it follows from the structure of the multiplicative group modulo p.[4] The theorem's converse—that if (n-1)! \equiv -1 \pmod{n} for n > 1, then n is prime—relies on the fact that for composite n > 4, (n-1)! is divisible by n (hence congruent to 0 modulo n), due to the presence of distinct factors in the factorial.[1] Proofs of the theorem vary; one common approach pairs each integer a from 1 to p-2 with its modular inverse modulo p, showing that the product (p-1)! \equiv (p-1) \pmod{p} \equiv -1 \pmod{p}.[4] Another utilizes Fermat's Little Theorem and polynomial interpolation, while a third employs primitive roots modulo p to express the factorial as a power product.[4] Wilson's theorem has significant applications in number theory, including as a primality test (though computationally inefficient for large numbers due to factorial computation) and in deriving corollaries such as that −1 is a quadratic residue modulo primes of the form $4k+1, where [(2k)!]^2 \equiv -1 \pmod{p}.[1] It also aids in proving Fermat's Little Theorem by facilitating reductions of powers and factorials modulo primes, and it generalizes to concepts like the Wilson quotient \frac{(p-1)! + 1}{p}, which is an integer for primes p and relates to properties of prime powers.[5][1]History and Context
Origins and Discovery
Wilson's theorem, which states a key congruence involving factorials and prime numbers, has roots predating its association with John Wilson, though it bears his name. The result was first stated by the Persian mathematician Ibn al-Haytham (Alhazen) around 1000 AD and was known to Gottfried Wilhelm Leibniz in the 17th century. It was conjectured in the 18th century by English mathematician John Wilson (1741–1793). Wilson, a distinguished scholar at the University of Cambridge, was elected a Fellow of Peterhouse in 1764 after achieving the position of Senior Wrangler—the top mathematics student—in the 1761 tripos examinations.[6] As a skilled instructor in mathematics, Wilson explored various number-theoretic ideas, including the observation that would later bear his name, though he did not publish it himself.[6] The theorem was first publicly announced by Wilson's mentor, Edward Waring (1734–1798), in his influential treatise Meditationes Algebraicae, published in Cambridge in 1770. Waring, the Lucasian Professor of Mathematics at Cambridge, explicitly credited the result to his former student Wilson, presenting it without a proof as a conjecture about the behavior of (p-1)! modulo a prime p.[7] This publication marked the theorem's entry into the mathematical literature, building on Wilson's unpublished manuscript explorations conducted around that time. The 1770 edition of Waring's work thus served as the primary vehicle for disseminating Wilson's insight to the broader community of European mathematicians.[8] The discovery connected to earlier investigations into factorial congruences by prominent figures such as Leonhard Euler (1707–1783) and Joseph-Louis Lagrange (1736–1813). Euler had examined related properties of factorials and modular arithmetic in his studies of Fermat's Little Theorem during the 1760s, laying groundwork for such results through his work on binomial expansions and prime divisibility. Lagrange, in turn, provided the first rigorous proof of the theorem in 1773, demonstrating its equivalence to certain aspects of Euler's earlier findings on multiplicative inverses modulo primes, thereby solidifying its place in number theory.[1] This linkage highlighted how Wilson's observation synthesized and extended prior continental European efforts on arithmetic progressions and congruences.Naming and Early Recognition
Although the result was first published without proof by Edward Waring in his Meditationes algebraicae in 1770, the theorem is attributed to John Wilson, Waring's friend and former student, who had conjectured it around that time.[7] Waring gave it the name "Wilson's theorem" upon publication.[7] Carl Friedrich Gauss prominently recognized the theorem as a fundamental result in prime number theory in his Disquisitiones Arithmeticae (1801), explicitly referring to it as "the theorem of Wilson" in Article 75 and integrating it into his systematic treatment of congruences and primitive roots.[7][9] The theorem's significance was underscored by early proofs and commentaries that demonstrated its utility prior to formal naming, including Joseph-Louis Lagrange's rigorous proof in 1773 and Augustin's subsequent analysis by Cauchy in 1813, which further emphasized its role in analytic number theory.[10] Over time, the terminology evolved from Gauss's phrasing as a specific "theorem of Wilson" to the standardized "Wilson's theorem" in 19th-century literature, reflecting its central place in elementary number theory.[7]Statement
For Prime Moduli
Wilson's theorem, specifically for prime moduli, states that if p is a prime number greater than 1, then the product of all positive integers from 1 to p-1 satisfies the congruence (p-1)! \equiv -[1](/page/1) \pmod{p}. This relation highlights a distinctive property of primes in the context of modular arithmetic, where the factorial (p-1)! represents the multiplication of the nonzero residue classes modulo p.[1][11] The congruence assumes familiarity with modular arithmetic, in which a \equiv b \pmod{p} means that p divides a - b, and with the definition of a prime as an integer greater than 1 having no positive divisors other than 1 and itself. Since p is prime, each integer from 1 to p-1 is coprime to p, allowing the factorial to be computed as a product within the multiplicative group of integers modulo p.[12][5] Equivalently, the theorem implies that the Wilson's quotient W_p = \frac{(p-1)! + 1}{p} is an integer whenever p is prime. This integer-valued expression provides an alternative way to express the theorem's condition.[13] In contrast to the prime case, the congruence fails for most composite moduli.[1]For Composite Moduli
Wilson's theorem fails to hold for composite moduli n > 1, as (n-1)! \not\equiv -1 \pmod{n}. In fact, the congruence (n-1)! \equiv -1 \pmod{n} is true if and only if n is prime.[12] For composite n > 4, the factorial (n-1)! is divisible by n, so (n-1)! \equiv 0 \pmod{n}. This occurs because n has prime factors whose multiples appear sufficiently often in the product $1 \times 2 \times \cdots \times (n-1) to account for the full prime power factorization of n. Specifically, if n = ab with distinct primes $1 < a < b < n, then both a and b divide (n-1)!, hence so does n. For n = p^k with prime p and k \geq 2, multiples of p up to n-1 ensure at least k factors of p in (n-1)!, so n divides it.[14][1] The case n = 4 is an exception among composites, where $3! = 6 \equiv 2 \pmod{4}, neither $0 nor -1 \equiv 3 \pmod{4}. Consequently, for composite n > 4, (n-1)! + 1 \equiv 1 \pmod{n}, failing the prime condition. While the basic congruence holds for all primes, rare primes known as Wilson primes (5, 13, 563) satisfy the stronger condition (p-1)! + 1 \equiv 0 \pmod{p^2}.[1][15]Examples and Illustrations
Basic Numerical Example
Wilson's theorem states that for a prime number p, the factorial (p-1)! is congruent to -1 modulo p.[1] A basic example is the prime p = 5. Compute $4! = 1 \times 2 \times 3 \times 4 = 24. To find $24 \mod 5, note that $5 \times 4 = 20 and $24 - 20 = 4, so $24 \equiv 4 \pmod{5}. Since $4 + 1 = 5, which is divisible by 5, it follows that $4 \equiv -1 \pmod{5}. Thus, $4! \equiv -1 \pmod{5}.[1] For the prime p = 7, first compute $6! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720. To verify the congruence, observe that $720 + 1 = 721 and $721 = [7](/page/+7) \times 103, since [7](/page/+7) \times 100 = 700 and [7](/page/+7) \times 3 = 21, so 721 is divisible by 7. Therefore, $720 \equiv -1 \pmod{[7](/page/+7)}.[1] The pattern holds for smaller and larger small primes as well. The following table shows (p-1)! \mod p for the primes p = 2, 3, 5, [7](/page/+7), 11, confirming the result equals -1 \mod p in each case:| Prime p | (p-1)! | (p-1)! \mod p | -1 \mod p |
|---|---|---|---|
| 2 | 1! = 1 | 1 | 1 |
| 3 | 2! = 2 | 2 | 2 |
| 5 | 4! = 24 | 4 | 4 |
| 7 | 6! = 720 | 6 | 6 |
| 11 | 10! = 3,628,800 | 10 | 10 |