In this post, we give two proofs of Wilson’s theorem. The second proof uses the notion of primitive roots. The following is the statement of the theorem.
Theorem 1 (Wilson’s Theorem)
Let be a positive integer. Then is a prime number if and only if .
An alternative way of stating Wilson’s theorem is that is a prime number if and only if is divisible by .
We use to denote the greatest common divisor of the positive integers and . We use the following lemma.
Let be a prime number. Then the congruence equation has exactly two solutions. They are .
Proof of Lemma 2
It is straightforward to see that and . It remains to show that are the only two solutions. To that end, we show that any solution of must be one of these.
Let be a solution of the above congruence equation. This means that and . So . By Euclid’s lemma, either or . The first case gives and the second case gives . Since , the first congruence means that and the second congruence means that .
Let be a positive integer with . Then the following conditions are equivalent.
- The number and the modulus are relatively prime, i.e., .
- There exists a unique integer with such that . In other words, the number has a multiplicative inverse modulo .
Lemma 3 is proved in a previous post (see Theorem 1 in the post Euler’s phi function, part 1).
Proof of Theorem 1 (first proof)
Suppose is a positive integer that is not prime. Then has a factor among the integers . Thus (i.e. and are not relatively prime).
We claim that . Suppose that . Then we have for some integers and . Since divides the left-hand side of the equation, . But . So .
We have proved that if is not prime, then . Equivalently if , then is prime.
Suppose is prime. For each , and are relatively prime. By Lemma 3, for each such , there exists a unique in such that .
By Lemma 2, the congruence equation has exactly two solutions, namely . Thus are the only numbers in for which and its inverse are the same. For each , .
The number is an even integer. There are many numbers in the set . Based on the discussion in the preceding paragraph, the set consists of many pairs of numbers such that the product of each pair is . Thus we have
We can also write . Multiply on both sides of the equation, we have . Since , we have .
To carry out the following proof, we use the theorem that every prime modulus has a primitive root. A primitive root for a given prime modulus is a positive integer with such that the least positive exponent satisfying the equation is .
Another property of primitive roots that is used in the following proof is that for a given primitive root for a given prime modulus , the powers of would generate the elements of the set (these are the least residues that are relatively prime to the prime modulus ).
Basic properties of primitive roots are discussed in the post called Defining Primitive Root.
Proof of Theorem 1 (second proof)
We prove the direction that if is prime, then .
If , it is clear that . Suppose is an odd prime. Then there exists a primitive root modulo . Let be one such. Because is prime, every integer in the interval is relative prime to . One property of a primitive root for the prime modulus is that the powers of would generate the integers in the interval . Specifically we have the following set equality
where each is a least residue modulo , i.e., and . As a result of the above set equality, we have the following congruence equality.
The exponents in the left-hand side of the above congruence equality can be summed as follows:
The congruence equality (1) can be further simplified as follows:
It follows from Fermat’s theorem that . Thus the number satisfies the congruence equation . By Lemma 2, has exactly 2 solutions, namely or . So we have the following are two possibilities for .
But the first one is not possible since is a primitive root modulo . So the second congruence is true. It follows that
The above derivation concludes the proof of the theorem.