NTIC Wilson's Theorem and Fermat's Theorem

Section 7.5 Wilson's Theorem and Fermat's Theorem

Polynomials aren't the only types of formulas we will see. Here, we introduce two famous theorems about other types of congruences modulo

$p$ (a prime) that will come in very handy in the future.

🔗

Subsection 7.5.1 Wilson's Theorem

🔗

Theorem 7.5.1. Wilson's Theorem.

If $p$ is a prime, then

$\begin{equation*} (p-1)!\equiv -1\text{ (mod }p)\text{,} \end{equation*}$

where the exclamation point here indicates the factorial.

🔗

Proof.

If $p=2$ this is very, very easy to check. So assume $p\neq 2\text{,}$ hence $p-1$ is even. Now we will think of all the numbers from $1$ to $p-1\text{,}$ which will be multiplied to make the factorial. (We will put the example $p=11$ in bullets to help follow.)

For each $n$ such that $1 \lt n \lt p-1\text{,}$ we know that $n$ has a unique inverse modulo $p\text{.}$ Pair up all the numbers between (not including) 1 and $p-1$ in this manner.

If $p=11\text{,}$ we pair up $(2,6)\text{,}$ $(3,4)\text{,}$ $(5,9)\text{,}$ and $(7,8)\text{.}$

Then multiplying out $(p-1)$ factorial, we can reorder the terms using the pairs, and notice much cancellation:

\begin{equation*} (p-1)!\equiv1\cdot 2\cdot 3\cdots (p-2)\cdot (p-1) \equiv 1 \cdot a\cdot a^{-1}\cdot b\cdot b^{-1}\cdots (p-1) \end{equation*}

\begin{equation*} \equiv 1\cdot 1\cdot 1\cdots 1\cdot (p-1)\equiv (p-1)\equiv -1\text{ (mod }p) \end{equation*}

For instance, if $p=11\text{,}$ we pair up

\begin{equation*} 10!\equiv 1\cdot 2\cdots 9\cdot 10\equiv 1\cdot (2\cdot 6)\cdot (3\cdot 4)\cdot (5 \cdot 9)\cdot (7 \cdot 8)\cdot 10 \end{equation*}

which simplifies to

\begin{equation*} 10!\equiv 1\cdot 1\cdot 1\cdot 1\cdot -1\text{ (mod }p) \end{equation*}

Beautiful!

The only loose end is that perhaps some number pairs up with itself, which would mess up that all the numbers pair off nicely. However, in that case, $a^2\equiv 1$ (mod $p$), so by definition $p\mid (a-1)(a+1)\text{;}$ since $p$ is a prime greater than two, it must divide one (and only one) of these factors (recall Lemma 6.3.6). In these cases $a\equiv 1$ or $a\equiv p-1\text{.}$ But we were not pairing off $1$ or $p-1\text{,}$ so this can't happen.

🔗

Exercise 7.7.7 is to show that the conclusion of Wilson's theorem fails for

$p=10\text{.}$ That is, that

$(10-1)!\not\equiv -1$ (mod

$10$ ). So does it work or not for other moduli?

xxxxxxxxxx
 
@interact
def _(n=range_slider(2,100,1,(3,9))):
    for modulus in [n[0]..n[1]]:
        pretty_print(html(r"$(%s-1)!\equiv %s$ (mod $%s$)"%(modulus, mod(factorial(modulus-1),modulus), modulus)))

🔗

Remark 7.5.2.

See Exercise 7.7.11 once you have explored this for a while. For a nice combinatorial proof, see [C.7.27]. If you are really curious see Wikipedia or Alexander Walker's blog for a generalization due to Gauss; a somewhat different approach to generalization is taken in [C.7.28].

🔗

Subsection 7.5.2 Fermat's Little Theorem

🔗

If one explores a little with powers of numbers modulo

$p$ a prime, one usually notices some pattern of those powers. This is the best-known, and soon we'll reinterpret it in a powerful way.

🔗

Theorem 7.5.3. Fermat's Little Theorem.

If $\gcd(a,p)=1$ for $p$ a prime, then

$\begin{equation*} a^{p-1}\equiv 1\text{ (mod }p)\text{.} \end{equation*}$

🔗

Proof.

Sketch of proof (to fill in, see Exercise 7.7.10):

If $\gcd(a,p)=1$ and $p$ is prime, show that $\{a,2a,3a,\ldots,(p-1)a,pa\}$ is a complete residue system (mod $p$).
- That is, show that the set $\{[a],[2a],[3a],\ldots,[pa]\}$ is the same as the complete set of residues $\{[0],[1],[2],\ldots,[p-1]\}\text{,}$ though possibly in a different order.
If $p$ is prime and $p$ does not divide $a\text{,}$ show that

\begin{equation*} a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1)\text{ (mod }p)\text{.} \end{equation*}
Now use Wilson's Theorem and multiply by $-1\text{.}$

🔗

There are other ways to prove it as well. There is a beautiful approach in terms of counting necklaces or strings of pearls which requires essentially no number theory, but rather basic ideas from combinatorics, the discipline of counting well. We'll see a more abstract approach after we introduce the concept of groups in Chapter 8; see Exercise 9.6.2.

🔗

So despite the innocuous appearance of this result as a corollary of another theorem, do not be fooled; it is incredibly powerful. As an example, it provides the primary tool in Fermat's proof that

$2^{37}-1$ is not prime⁴For more on this story see [C.5.8, page 57]; for more on this type of number see Definition 12.1.6.; imagine discovering this factorization by hand!

xxxxxxxxxx
 
print(2^37-1)
print(factor(2^37-1))