In the last posts, we have learned about polynomial interpolation through two formulas, the Newton's interpolation formula and the Lagrange's interpolation formula. Both formulas can be used to prove the Wilson's theorem.
In this post, we will present a proof of the Wilson's theorem based on the Newton's interpolation formula. The other proof, that is, proving Wilson's theorem based on the Lagrange's interpolation formula, we leave it as a homework exercise.
Wilson's Theorem is a well known theorem in number theory. It says that if $p$ is prime number then the number $(p−1)!+1$ is a multiple of $p$.
For example,
- with $p=2$, $1!+1=2$ is divisible by $2$
- with $p=3$, $2!+1=3$ is divisible by $3$
- with $p=5$, $4!+1=25$ is divisible by $5$
- with $p=7$, $6!+1=721$ is divisible by $7$
There are many proofs of Wilson's theorem. On this blog, we have previously shown a proof based on the finite difference method $$\Delta P(x) = P(x+1) - P(x)$$
The proof that we are about to show is based on the Newton's interpolation formula for polynomials.
If $P(x)$ is a polynomial of degree $n$ and $x_1$, $x_2$, $\dots$, $x_n$, $x_{n+1}$ are $n+1$ distinct numbers then the Newton's interpolation formula is the following formula $$P(x) = \alpha_1 + \alpha_2(x-x_1) + \alpha_3(x-x_1)(x-x_2) + \dots + \alpha_{n+1} (x-x_1)(x-x_2) \dots (x-x_n)$$
The coefficients $\alpha_i$ in the Newton's interpolation formula can be determined as follows. To determine $\alpha_1$, we substitute $x=x_1$ into the formula. To determine $\alpha_2$, we substitute $x=x_2$. Similarly, the last coefficient $\alpha_{n+1}$ is determined by substituting $x=x_{n+1}$.
Now, to prove Wilson's theorem, which polynomial $P(x)$ are we going to apply the Newton's interpolation formula for?
We will apply the formula for the following polynomial $$P(x) = x^{p-1} -1$$
This special polynomial is motivated from the 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.
What does the Fermat's little theorem tell us? With our choice of the above polynomial $P(x) = x^{p-1} - 1$, the Fermat's little theorem tells us that, all the values $P(1)$, $P(2)$, $P(3)$, $\dots$, $P(p-1)$ are divisible by $p$.
The polynomial $P(x) = x^{p-1} -1$ has degree $p-1$, and so we will choose $x_1=1$, $x_2=2$, $\dots$, $x_p =p$ for the Newton's formula and we have $$P(x) = x^{p-1} -1 = \alpha_1 + \alpha_2(x-1) + \alpha_3(x-1)(x-2) + \dots + \alpha_{p} (x-1)(x-2) \dots (x-(p-1))$$
Now, let us substitute $x=1,2,3, \dots$ one by one to determine the coefficients $\alpha_1, \alpha_2, \alpha_3, \dots$.
- First of all, with $x=1$, we obtain $\alpha_1 = 0$, so $$P(x) = x^{p-1} -1 = \alpha_2(x-1) + \alpha_3(x-1)(x-2) + \dots + \alpha_{p} (x-1)(x-2) \dots (x-(p-1))$$
- With $x=2$, we have $$P(2) = \alpha_2 . $$ Since $P(2)$ is a multiple of $p$ by the Fermat's little theorem, we can write $$\alpha_2 = p ~\beta_2 .$$
- With $x=3$, we have $$P(3) = 2 ~\alpha_2 + 2 ~\alpha_3,$$ so $$2 ~\alpha_3 = P(3) - 2 ~\alpha_2 = p ~z_3 - 2 ~p ~\beta_2 = p ~\beta_3,$$ and thus, $$\alpha_3 = p~ \frac{\beta_3}{\gamma_3},$$ where $(\gamma_3, p) = 1$.
- With $x=4$, we have $$P(4) = 3 ~\alpha_2 + 6 ~\alpha_3 + 3! ~\alpha_4,$$ so $$3! ~\alpha_4 = P(4) - 3 ~\alpha_2 - 6 ~\alpha_3 = p ~z_4 - 3 ~p ~\beta_2 - 6 ~p~ \frac{\beta_3}{\gamma_3} = p~ \frac{\beta_4}{\gamma_3},$$ and thus, $$\alpha_4 = p~ \frac{\beta_4}{\gamma_4},$$ where $(\gamma_4, p) = 1$.
- Similarly, we can show that for any $i = 2, 3, 4, 5, \dots, p-1$, we can write $$\alpha_i = p~ \frac{\beta_i}{\gamma_i},$$ where $(\gamma_i, p) = 1$.
What about the last coefficient $\alpha_p$? If we compare the polynomial coefficients of degree $p-1$ in the Newton's formula $$P(x) = x^{p-1} -1 = \alpha_2(x-1) + \alpha_3(x-1)(x-2) + \dots + \alpha_{p} (x-1)(x-2) \dots (x-(p-1))$$ then we can see that on the left hand side, the coefficient of $x^{p-1}$ is $1$, and on the right hand side, the coefficient of $x^{p-1}$ is $\alpha_{p}$. Therefore, $$\alpha_{p} = 1 .$$
So we have determined all the coefficients $\alpha_i$, and the Newton's interpolation formula becomes $$P(x) = x^{p-1} -1 = p~ \frac{\beta_2}{\gamma_2} (x-1) + p~ \frac{\beta_3}{\gamma_3} (x-1)(x-2) + \dots + (x-1)(x-2) \dots (x-(p-1))$$
By substituting $x=0$, we have $$-1 = p~ \frac{\beta_2}{\gamma_2} ~(-1) + p~ \frac{\beta_3}{\gamma_3} ~(-1)^2 2! + \dots + p~ \frac{\beta_{p-1}}{\gamma_{p-1}} ~(-1)^{p-2} (p-2)! + (-1)^{p-1} (p-1)!$$
Therefore, $$(-1)^{p-1} (p-1)! + 1 = p~ \frac{b}{\gamma_2 ~\gamma_3 \dots ~\gamma_{p-1}}$$
In the above equation, the left hand side is an integer, so on the right hand side, $pb$ must be divisible by $\gamma_2 ~\gamma_3 \dots ~\gamma_{p-1}$. Since all the numbers $\gamma_2$, $\gamma_3$, $\dots$, $\gamma_{p-1}$ are co-prime to $p$, the number $b$ must be divisible by $\gamma_2 ~\gamma_3 \dots ~\gamma_{p-1}$. Thus, $$\frac{b}{\gamma_2 ~\gamma_3 \dots ~\gamma_{p-1}}$$ is an integer.
Therefore, $$(-1)^{p-1} (p-1)! + 1 = 0 \pmod{p}$$
And we obtain the Wilson's theorem $$(p-1)! + 1 = 0 \pmod{p}$$
Today, we have shown another proof of the Wilson's theorem based on Fermat's little theorem and the Newton's interpolation formula. Let us stop here for now and hope to see you again in the next post.
Homework. Prove Wilson's theorem by using the Lagrange's interpolation formula.