Wilson's Theorem/Necessary Condition

From ProofWiki
Jump to navigation Jump to search


Let $p$ be a prime number.


$\paren {p - 1}! \equiv -1 \pmod p$

Proof 1

If $p = 2$ the result is obvious.

Therefore we assume that $p$ is an odd prime.

Let $p$ be prime.

Consider $n \in \Z, 1 \le n < p$.

As $p$ is prime, $n \perp p$.

From Law of Inverses (Modulo Arithmetic), we have:

$\exists n' \in \Z, 1 \le n' < p: n n' \equiv 1 \pmod p$

By Solution of Linear Congruence, for each $n$ there is exactly one such $n'$, and $\paren {n'}' = n$.

So, provided $n \ne n'$, we can pair any given $n$ from $1$ to $p$ with another $n'$ from $1$ to $p$.

We are then left with the numbers such that $n = n'$.

Then we have $n^2 \equiv 1 \pmod p$.

Consider $n^2 - 1 = \paren {n + 1} \paren {n - 1}$ from Difference of Two Squares.

So either $n + 1 \divides p$ or $n - 1 \divides p$.

Observe that these cases do not occur simultaneously, as their difference is $2$, and $p$ is an odd prime.

From Negative Number is Congruent to Modulus minus Number‎:

$p - 1 \equiv -1 \pmod p$

Hence $n = 1$ or $n = p - 1$.

So, we have that $\paren {p - 1}!$ consists of numbers multiplied together as follows:

in pairs whose product is congruent to $1 \pmod p$
the numbers $1$ and $p - 1$.

The product of all these numbers is therefore congruent to $1 \times 1 \times \cdots \times 1 \times p - 1 \pmod p$ by modulo multiplication.

From Negative Number is Congruent to Modulus minus Number:

$\paren {p - 1}! \equiv -1 \pmod p$


Proof 2

If $p = 2$ the result is obvious.

Therefore we assume that $p$ is an odd prime.

Consider $p$ points on the circumference of a circle $C$ dividing it into $p$ equal arcs.

By joining these points in a cycle, we can create polygons, some of them stellated.

From Number of Different n-gons that can be Inscribed in Circle, the number of different such polygons is $\dfrac {\paren {p - 1}!} 2$.

When you rotate these polygons through an angle of $\dfrac {2 \pi} p$, exactly $\dfrac {p - 1} 2$ are unaltered.

These are the regular $p$-gons and regular stellated $p$-gons.

That there are $\dfrac {p - 1} 2$ of them follows from Number of Regular Stellated Odd n-gons.

The remaining $\dfrac {\paren {p - 1}!} 2 - \dfrac {p - 1} 2$ polygons can be partitioned into sets of $p$ elements: those which can be obtained from each other by rotation through multiples of $\dfrac {2 \pi} p$.

The total number of such sets is then:

$\dfrac {\paren {p - 1}! - \paren {p - 1} } {2 p}$

Thus we have that:

$2 p \divides \paren {\paren {p - 1}! - \paren {p - 1} }$

That is:

$p \divides \paren {\paren {p - 1}! + 1}$


Proof 3

Let $p$ be prime.

Consider $\struct {\Z_p, +, \times}$, the ring of integers modulo $m$.

From Ring of Integers Modulo Prime is Field, $\struct {\Z_p, +, \times}$ is a field.

Hence, apart from $\eqclass 0 p$, all elements of $\struct {\Z_p, +, \times}$ are units

As $\struct {\Z_p, +, \times}$ is a field, it is also by definition an integral domain, we can apply:

From Product of Units of Integral Domain with Finite Number of Units, the product of all elements of $\struct {\Z_p, +, \times}$ is $-1$.

But the product of all elements of $\struct {\Z_p, +, \times}$ is $\paren {p - 1}!$

The result follows.


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