Wilson's Theorem

From ProofWiki
(Redirected from Wilson-Lagrange Theorem)
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Wilson%27s_Theorem&oldid=477532"