In previous posts, we have learned about modulo for rational numbers. To show its application, today, we will use the language of modulo of rationals to give another proof of Wilson's Theorem.
Wilson's theorem is a well known theorem in number theory. It is stated as follows.
Wilson's Theorem. If $p$ is a prime number then $$(p-1)! = -1 \pmod{p}.$$
For example,
- with $p=2$, $$1! = 1= -1 \pmod{2}$$
- with $p=3$, $$2! = 2 = -1 \pmod{3}$$
- with $p=5$, $$4! = 24 = -1 \pmod{5}$$
- with $p=7$, $$6!= 720 = -1 \pmod{7}$$
When we use modulo of rationals to solve a problem concerning integers, it is often based on the following simple theorem.
Theorem. Let $n$, $a$, $b$ be integer numbers. Then the condition that $$a =_{Q} ~b \pmod{n}$$ is equivalent to the condition $$a=b \pmod{n}.$$
Suppose that we need to show that $a=b \pmod{n}$ for two integers $a$ and $b$. Sometimes, if it is only based on modulo of integers, it is quite hard to prove directly that $a=b \pmod{n}$. However, if we use modulo of rationals, our calculation will then no longer be restricted under the integers alone, but can be extended into a larger domain of rational numbers. It may be easier to prove that $$a =_{Q} ~b \pmod{n},$$ and then from here, by using the above theorem, we obtain the needed equality $$a=b \pmod{n}.$$
Let us now use the above technique to prove the Wilson' theorem. We will apply the Newton's interpolation formula for the following polynomial $$P(x) = x^{p-1} -1.$$
By Fermat's "little" theorem, for the above polynomial, we have $$P(1) = P(2) = P(3) = \dots = P(p-1) = 0 \pmod{p}.$$
Proving Wilson's Theorem based on Newton's interpolation formula
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 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 in the formula can be determined as follows. To find $\alpha_1$, we substitute $x=x_1$ into the formula. To find $\alpha_2$, we substitute $x=x_2$. Similarly, the last coefficient $\alpha_{n+1}$ can be determined by substituting $x=x_{n+1}$.
The polynomial that we will use is $P(x)=x^{p−1}−1$. This polynomial is of degree $p−1$. We will use $x_1=1$, $x_2=2$, $\dots$, $x_p=p$. The Newton's formula becomes $$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))$$
Clearly, the coefficients $\alpha_i$ are rational numbers. We will prove the following two points:
- $\alpha_{p} = 1$
- for any $i=1,2, \dots, p-1$, $$\alpha_i =_{Q} ~0 \pmod{p}.$$
Proving $\alpha_{p} = 1$
To show that $\alpha_{p} = 1$, we compare the polynomial coefficient of degree $p−1$ in Newton's formula $$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))$$
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$.
Proving $\alpha_i =_{Q} ~0 \pmod{p}$ for $i=1,2, \dots, p-1$
From the formula $$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))$$
- Substitute $x=1$, we obtain $$\alpha_1 = 0$$
- Substitute $x=2$, we obtain $$P(2) = \alpha_2.$$ By Fermat's little theorem, $P(2) = 0 \pmod{p}$, thus, $$\alpha_2 =_{Q} ~0 \pmod{p}$$
- Substitute $x=3$, we obtain $$P(3) = \alpha_2 (3-1) + \alpha_3 (3-1)(3-2).$$ By Fermat's little theorem, $P(3) = 0 \pmod{p}$; we also have $\alpha_2 =_{Q} ~0 \pmod{p}$, therefore, $$\alpha_3 (3-1)(3-2) =_{Q} ~0 \pmod{p}.$$ It follows that $$\alpha_3 =_{Q} ~0 \pmod{p}$$
- Similarly, substitute $x=i$, we obtain $$P(i) = \alpha_2 (i-1) + \alpha_3 (i-1)(i-2) + \dots + \alpha_i ~(i-1)!$$ By Fermat's little theorem, $P(i) = 0 \pmod{p}$; we have also proved that $$\alpha_2 =_{Q} ~\alpha_3 =_{Q} ~\dots =_{Q} ~\alpha_{i-1} =_{Q} ~0 \pmod{p},$$ so $$\alpha_i ~(i-1)! =_{Q} ~0 \pmod{p},$$ thus, $$\alpha_i =_{Q} ~0 \pmod{p}.$$
In summary, we have proved the following two points
- $\alpha_{p} = 1$
- for any $i=1,2, \dots, p-1$, $$\alpha_i =_{Q} ~0 \pmod{p}.$$
It follows from the Newton's formula $$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))$$ that for any rational number $x$, we have $$P(x)=x^{p−1}−1 =_{Q} ~ (x−1)(x−2) \dots (x−(p-1)) \pmod{p}$$
Substitute $x=0$, we obtain $$-1 =_{Q} ~ (−1)(−2) \dots (−(p-1)) \pmod{p}.$$ That is $$(-1)^{p-1} (p-1)! =_{Q} -1 \pmod{p}.$$
Both sides are integers, therefore, $$(-1)^{p-1} (p-1)! = -1 \pmod{p}.$$
And we obtain Wilson's theorem $$(p-1)! = -1 \pmod{p}.$$
Today we have shown another proof of Wilson's theorem by using Fermat's little theorem and Newton's interpolation formula. This proof is explained in the language of modulo for rational numbers. We can read more about Wilson's theorem by following the following links: Wilson's Theorem I, Wilson's Theorem II.
Let us stop here for now. See you again on the next post.
Let us stop here for now. See you again on the next post.
Homework. Prove Wilson's theorem by using Lagrange's interpolation formula in the following steps.
Suppose that $p$ is a prime number.
1. Let $f(x)$ be a polynomial of rational coefficients and of degree less than or equal to $p-2$. Use Lagrange's interpolation formula to prove that if $$f(1) =_{Q} ~f(2) =_{Q} ~f(3) =_{Q} \dots =_{Q} ~f(p-1) =_{Q} 0 \pmod{p}$$ then all the coefficients of the polynomial $f(x)$ will $=_{Q} ~0 \pmod{p}$.
2. Let $f(x)$ be a polynomial of integer coefficients and of degree less than or equal to $p-2$. Prove that if $$f(1) = f(2) = f(3) = \dots = f(p-1) = 0 \pmod{p}$$ then all the coefficients of the polynomial $f(x)$ will $= 0 \pmod{p}$.
3. Take $$f(x) = (x^{p-1} -1) - (x-1)(x-2) \dots (x-(p-1))$$ Prove that all the coefficients of the polynomial $f(x)$ are $= 0 \pmod{p}$.
The last coefficient of the above polynomial is $$-1 - (-1)^{p-1} (p-1)!$$ From here implies the Wilson's theorem.