Two Proofs of Wilson’s Theorem

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 p be a positive integer. Then p is a prime number if and only if (p-1)! \equiv -1 \ (\text{mod} \ p).

An alternative way of stating Wilson’s theorem is that p is a prime number if and only if (p-1)! +1 is divisible by p.

___________________________________________________________________________________________________________________

One Proof

We use \text{GCD}(a,b) to denote the greatest common divisor of the positive integers a and b. We use the following lemma.

    Lemma 2

      Let m be a prime number. Then the congruence equation x^2 \equiv 1 \ (\text{mod} \ m) has exactly two solutions. They are x=1,m-1.

Proof of Lemma 2

It is straightforward to see that 1^2 \equiv 1 \ (\text{mod} \ m) and (m-1)^2 \equiv 1 \ (\text{mod} \ m). It remains to show that x=1,m-1 are the only two solutions. To that end, we show that any solution of x^2 \equiv 1 \ (\text{mod} \ m) must be one of these.

Let t be a solution of the above congruence equation. This means that t^2 \equiv 1 \ (\text{mod} \ m) and 0 \le t \le m-1. So m \ \lvert \ (t^2-1)=(t+1)(t-1). By Euclid’s lemma, either m \ \lvert (t+1) or m \ \lvert (t-1). The first case gives t \equiv -1 \ (\text{mod} \ m) and the second case gives t \equiv 1 \ (\text{mod} \ m). Since 0 \le t \le m-1, the first congruence means that t=p-1 and the second congruence means that t=1. \blacksquare

    Lemma 3

      Let a be a positive integer with 0 \le a \le m-1. Then the following conditions are equivalent.

      1. The number a and the modulus m are relatively prime, i.e., \text{GCD}(a,m)=1.
      2. There exists a unique integer b with 0 \le b \le m-1 such that ab \equiv 1 \ (\text{mod} \ m). In other words, the number a has a multiplicative inverse modulo m.

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)

\Longleftarrow
Suppose p is a positive integer that is not prime. Then p has a factor among the integers 2,3,\cdots,p-1. Thus d=\text{GCD}((p-1)!,p)>1 (i.e. (p-1)! and p are not relatively prime).

We claim that (p-1)! \not \equiv -1 \ (\text{mod} \ p). Suppose that (p-1)! \equiv -1 \ (\text{mod} \ p). Then we have (p-1)! \cdot x+ p \cdot y=-1 for some integers x and y. Since d divides the left-hand side of the equation, d \ \lvert \ -1. But d=\text{GCD}((p-1)!,p)>1. So (p-1)! \not \equiv -1 \ (\text{mod} \ p).

We have proved that if p is not prime, then (p-1)! \not \equiv -1 \ (\text{mod} \ p). Equivalently if (p-1)! \equiv -1 \ (\text{mod} \ p), then p is prime.

\Longrightarrow
Suppose p is prime. For each a \in \left\{1,2,3,\cdots,p-1 \right\}, a and p are relatively prime. By Lemma 3, for each such a, there exists a unique b in \left\{1,2,3,\cdots,p-1 \right\} such that ab \equiv 1 \ (\text{mod} \ p).

By Lemma 2, the congruence equation x^2 \equiv 1 \ (\text{mod} \ p) has exactly two solutions, namely x=1,p-1. Thus a=1,p-1 are the only numbers in \left\{1,2,3,\cdots,p-1 \right\} for which a and its inverse b are the same. For each a \in \left\{2,3,\cdots,p-2 \right\}, a \ne b.

The number p-3 is an even integer. There are p-3 many numbers in the set \left\{2,3,\cdots,p-2 \right\}. Based on the discussion in the preceding paragraph, the set \left\{2,3,\cdots,p-2 \right\} consists of \displaystyle \frac{p-3}{2} many pairs of numbers such that the product of each pair is \equiv 1 \ (\text{mod} \ p). Thus we have

    2 \cdot 3 \cdots (p-2) \equiv 1 \ (\text{mod} \ p)

We can also write (p-2)! \equiv 1 \ (\text{mod} \ p). Multiply p-1 on both sides of the equation, we have (p-1)! \equiv p-1 \ (\text{mod} \ p). Since p-1 \equiv -1 \ (\text{mod} \ p), we have (p-1)! \equiv -1 \ (\text{mod} \ p). \blacksquare

___________________________________________________________________________________________________________________

Another Proof

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 m is a positive integer g with 1 \le g \le m-1 such that the least positive exponent satisfying the equation g^x \equiv 1 \ (\text{mod} \ m) is m-1.

Another property of primitive roots that is used in the following proof is that for a given primitive root g for a given prime modulus m, the powers of g would generate the elements of the set \left\{1,2,3,\cdots,p-1 \right\} (these are the least residues that are relatively prime to the prime modulus m).

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 p is prime, then (p-1)! \equiv -1 \ (\text{mod} \ p).

\Longrightarrow
If p=2, it is clear that (p-1)! \equiv -1 \ (\text{mod} \ p). Suppose p is an odd prime. Then there exists a primitive root modulo p. Let g be one such. Because p is prime, every integer x in the interval 1 \le x \le p-1 is relative prime to p. One property of a primitive root for the prime modulus p is that the powers of g would generate the integers in the interval 1 \le x \le p-1. Specifically we have the following set equality

    \left\{r_1,r_2,r_3,\cdots,r_{p-1} \right\}=\left\{1,2,3,\cdots,p-1 \right\}

where each r_j is a least residue modulo p, i.e., 0 \le r_j \le p-1 and r_j \equiv g^j \ (\text{mod} \ p). As a result of the above set equality, we have the following congruence equality.

    g^1 g^2 g^3 \cdots g^{p-1} \equiv r_1 \cdot r_2 \cdot r_3 \cdots r_{p-1} \equiv (p-1)! \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

The exponents in the left-hand side of the above congruence equality can be summed as follows:

    \displaystyle 1+2+3+\cdots+p-1=\frac{(p-1)p}{2}

The congruence equality (1) can be further simplified as follows:

    \displaystyle g^{\frac{(p-1)p}{2}} \equiv (p-1)! \ (\text{mod} \ p)

It follows from Fermat’s theorem that g^{p-1} \equiv 1 \ (\text{mod} \ p). Thus the number \displaystyle g^{\frac{p-1}{2}} satisfies the congruence equation x^2 \equiv 1 \ (\text{mod} \ p). By Lemma 2, x^2 \equiv 1 \ (\text{mod} \ p) has exactly 2 solutions, namely x=1 or x=p-1. So we have the following are two possibilities for \displaystyle g^{\frac{p-1}{2}}.

    \displaystyle g^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)

    \displaystyle g^{\frac{p-1}{2}} \equiv p-1 \equiv -1 \ (\text{mod} \ p)

But the first one is not possible since g is a primitive root modulo p. So the second congruence is true. It follows that

    \displaystyle (p-1)! \equiv g^{\frac{(p-1)p}{2}}=(-1)^p \equiv -1 \equiv  \ (\text{mod} \ p)

The above derivation concludes the proof of the theorem. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s