Wilson's Theorem
Theorem
A (strictly) positive integer $p$ is a prime if and only if:
- $\paren {p - 1}! \equiv -1 \pmod p$
Corollary $1$
Let $p$ be a prime number.
Then $p$ is the smallest prime number which divides $\paren {p - 1}! + 1$.
Corollary $2$
Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Let $p$ be a prime factor of $n!$ with multiplicity $\mu$.
Let $n$ be expressed in a base $p$ representation as:
\(\ds n\) | \(=\) | \(\ds \sum_{j \mathop = 0}^m a_j p^j\) | where $0 \le a_j < p$ | |||||||||||
\(\ds \) | \(=\) | \(\ds a_0 + a_1 p + a_2 p^2 + \cdots + a_m p^m\) | for some $m > 0$ |
Then:
- $\dfrac {n!} {p^\mu} \equiv \paren {-1}^\mu a_0! a_1! \dotsb a_m! \pmod p$
Proof
If $p = 2$ the result is obvious.
Therefore we assume that $p$ is an odd prime.
Necessary Condition
Let $p$ be a prime number.
Then:
- $\paren {p - 1}! \equiv -1 \pmod p$
Sufficient Condition
Let $p$ be a (strictly) positive integer such that:
- $\paren {p - 1}! \equiv -1 \pmod p$
Then $p$ is a prime number.
Examples
$10$ does not divide $\paren {n - 1}! + 1$
For all $n \in \Z_{>0}$, $10$ is not a divisor of $\paren {n - 1}! + 1$.
Also known as
Some sources refer to Wilson's Theorem as the Wilson-Lagrange theorem, after Joseph Louis Lagrange, who proved it.
Source of Name
This entry was named for John Wilson.
Historical Note
The proof of Wilson's Theorem was attributed to John Wilson by Edward Waring in his $1770$ edition of Meditationes Algebraicae.
It was first stated by Ibn al-Haytham ("Alhazen").
It appears also to have been known to Gottfried Leibniz in $1682$ or $1683$ (accounts differ).
It was in fact finally proved by Lagrange in $1793$.
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-1}$ Basic Properties of Congruences: Example $\text {4-2}$
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $24$
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $561$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $24$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $563$
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Wilson's theorem
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Wilson's theorem