Today, we will study Wilson's Theorem - a theorem concerning prime numbers. Wilson's theorem says that if $p$ is a prime number then the number $(p-1)! + 1$ will be divisible by $p$.
Here, the notation $n!$ denotes $$n! = 1 \times 2 \times 3 \times \dots \times n.$$
For example,
- $1! + 1 = 2$ is divisible by $2$
- $2! + 1 = 3$ is divisible by $3$
- $4! + 1 = 25$ is divisible by $5$
- $6! + 1 = 721$ is divisible by $7$
There are many ways to prove Wilson's theorem. The proof that we will soon present here is a proof that is based on Fermat's little theorem.
Fermat's "little" Theorem. If $p$ is a prime number and $a$ is not divisible by $p$ then $$a^{p-1} = 1 \pmod{p}.$$
You can read more about Fermat's little theorem in this post.
To prove Wilson's theorem, we will use some facts about polynomials. These facts are quite simple but yet we will soon see that they turn out to be quite useful.
First, let us talk about polynomials. A polynomial is the one that looks like the following $$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0.$$ This polynomial $P(x)$ has a degree equal to $n$ and the numbers $a_0, a_1, \dots, a_n$ are called the coefficients. Particularly, $a_0$ is called the constant coefficient, $a_1$ is called the degree $1$ coefficient, $a_2$ is called the degree $2$ coefficient,..., $a_n$ is called the degree $n$ coefficient. The coefficient $a_0$ is also called the last coefficient and $a_n$ the leading coefficient of the polynomial.
Let us state some facts about polynomials.
Fact 1. For a polynomial $$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$$ its last coefficient can be calculated as: $a_0 = P(0)$.
Clearly, when we substitute $x=0$ then we obtain $P(0) = a_0$. So Fact 1 is trivial.
Fact 2. If the degree of the polynomial $P(x)$ is $n \geq 1$, then $$\Delta P(x) = P(x+1)-P(x)$$ is a polynomial of degree $n-1$.
We prove this property for a special case $x^n$, the general case will then follow.
For the polynomial $x^n$, we have $$\Delta x^n = (x+1)^n - x^n = n x^{n-1} + {n \choose 2} x^{n-2} + {n \choose 3} x^{n-3} + \dots + n x + 1$$ So $\Delta x^n$ is a polynomial of degree $n-1$.
For the general case, $$\Delta P(x) = a_n \Delta x^n + a_{n-1} \Delta x^{n-1} + \dots + a_1 \Delta x$$ Since $\Delta x^n$ is a polynomial of degree $n-1$, $\Delta x^{n-1}$ is a polynomial of degree $n-2$, ..., it follows that $\Delta P(x)$ is a polynomial of degree $n-1$.
Fact 3. The leading coefficient of the polynomial $\Delta P(x)$ is equal to $n a_n$.
As above, we have shown that $\Delta x^n$ is a polynomial of degree $n-1$ and its leading coefficient is $n$, so the leading coefficient of the polynomial $\Delta P(x) = a_n \Delta x^n + \dots$ is then equal to $n a_n$.
Now, let us use these three facts and prove Wilson's theorem.
Wilson's Theorem. For any prime number $p$, it must hold that $$ (p-1)! = -1 \pmod{p} $$
Proof. We use the following polynomial $$f_1(x) = x^{p-1} - 1$$
We have the following observations about this polynomial
- $f_1(x)$ is a polynomial of degree $p-1$
- the leading coefficient of $f_1(x)$ is $1$
- the last coefficient of $f_1(x)$ is $-1$
- by Fermat's little theorem, $f_1(1) = f_1(2) = f_1(3) = \dots = f_1(p-1) = 0 \pmod{p}$.
Let us construct the following polynomial $$f_2(x) = \Delta f_1(x) = f_1(x+1)-f_1(x)$$
- By Fact 2, $f_2(x)$ is a polynomial of degree $p-2$.
- By Fact 3, the leading coefficient of $f_2(x)$ is $p-1$.
- Since $f_2(x) = f_1(x+1) - f_1(x)$, we have $f_2(1) = f_2(2) = \dots = f_2(p-2) = 0 \pmod{p}$.
Similarly, with the polynomial $$f_3(x) = \Delta f_2(x) = f_2(x+1)-f_2(x)$$
we have
- $f_3(x)$ is a polynomial of degree $p-3$
- the leading coefficient of $f_3(x)$ is $(p-1)(p-2)$
- $f_3(1) = f_3(2) = \dots = f_3(p-3) = 0 \pmod{p}$
Finally, with $$f_{p-1}(x) = \Delta f_{p-2}(x) = f_{p-2}(x+1)-f_{p-2}(x)$$ we have
- $f_{p-1}(x)$ is a polynomial of degree $1$
- the leading coefficient of $f_{p-1}(x)$ is $(p-1)(p-2)\dots 2 = (p-1)!$
- $f_{p-1}(1) = 0 \pmod{p}$
Let us now calculate the last coefficients of these polynomials.
- The last coefficient of $f_1(x)$ is $f_1(0) = -1$.
- The last coefficient of $f_2(x)$ is $$f_2(0) = f_1(1) - f_1(0) = - f_1(0) \pmod{p}$$
- The last coefficient of $f_3(x)$ is $$f_3(0) = f_2(1) - f_2(0) = - f_2(0) \pmod{p}$$
- The last coefficient of $f_{p-1}(x)$ is $$f_{p-1}(0) = f_{p-2}(1) - f_{p-2}(0) = - f_{p-2}(0) \pmod{p}$$
It follows that $f_{p-1}(0) = (-1)^{p-2} f_1(0) = 1 \pmod{p}$.
We have shown that $f_{p-1}(x)$ is a polynomial of degree $1$, its leading coefficient is $(p-1)!$, its last coefficient is $f_{p-1}(0) = 1 \pmod{p}$, therefore, $$f_{p-1}(x) = (p-1)! x + c,$$ where, $c = 1 \pmod{p}$.
We have also shown that $f_{p-1}(1) = 0 \pmod{p}$, thus, $$(p-1)! + c = 0 \pmod{p}$$ Combining with the fact that $c = 1 \pmod{p}$, we deduce the Wilson's theorem that $$(p-1)! + 1 = 0 \pmod{p}. \blacksquare$$
So we have proved the Wilson's theorem by using three simple facts about polynomials. Particularly, we made use of the formula $\Delta P(x) = P(x+1) - P(x)$. This formula is very similar to the derivative operation in calculus.
We stop here for now, see you again in the next post.
Homework.
1. Write in details the above proof for the case $p=5$.
2. Prove that if $n > 1$ and $(n-1)! = -1 \pmod{n}$ then $n$ must be a prime number.
3. Instead of using $\Delta P(x) = P(x+1)-P(x)$, we may consider $\Delta P(x) = P(x)-P(x-1)$. State and prove the corresponding Fact 2 and Fact 3 for this case.