Wilson's Theorem/Necessary Condition/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $p$ be a prime number.

Then:

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


Proof

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$

$\blacksquare$


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/Necessary_Condition/Proof_1&oldid=398782"