Proving Fermat’s Little Theorem

In working with the notion of congruence modulo m where m is a positive integer, one important calculation is finding the powers of a number a, i.e, the calculation a^n \equiv \ \text{mod} \ m. In one particular situation the calculation of interest is to identify the power n such that a^n \equiv 1 \ \text{mod} \ m. One elementary tool that can shed some light on this situation is the Fermat’s little theorem. This post is a self contained proof of this theorem.

After proving the theorem, we examine variations in the statements of the Fermat’s little theorem. There are some subtle differences among the variations. In one version of the Fermat’s little theorem (Theorem 4a below), the converse is not true as witnessed by the Carmichael numbers. In another version (theorem 4b below), the converse is true and gives a slightly better primality test (see Theorem 5 below) than the typical statement of the Fermat’s little theorem.

___________________________________________________________________________________________________________________

Example

Before discussing Fermat’s theorem and its proof, let’s look at an example. Let m=11, which is a prime number. Calculate the powers of a modulo m=11 for all a where 1 \le a \le m-1. Our goal is to look for a^n \equiv 1 \ \text{mod} \ 11.

First of all, if the goal is a^n \equiv 1 \ \text{mod} \ 11, then a cannot be 11 or a multiple of 11. Note that if a is a multiple of 11, then a^n \equiv 0 \ (\text{mod} \ 11) for any positive integer n. So we only need to be concerned with numbers a that are not multiples of m=11, i.e., numbers a that are not divisible by m=11.

Any number greater than 11 and is not divisible by 11 is congruent modulo eleven to one integer r in the range 1 \le r \le 10. So we only need to calculate a^n modulo 11 for 1 \le a \le 10. The following table displays the results of a^n modulo m=11.

    \displaystyle \begin{bmatrix} a^1&a^2&a^3&a^4&a^5&a^6&a^7&a^8&a^9&a^{10}  \\\text{ }&\text{ }&\text{ }   \\ 1&1&1&1&1&1&1&1&1&1 \\ 2&4&8&5&10&9&7&3&6&1 \\ 3&9&5&4&1&3&9&5&4&1 \\ 4&5&9&3&1&4&5&9&3&1 \\ 5&3&4&9&1&5&3&4&9&1 \\ 6&3&7&9&10&5&8&4&2&1 \\ 7&5&2&3&10&4&6&9&8&1 \\ 8&9&6&4&10&3&2&5&7&1 \\ 9&4&3&5&1&9&4&3&5&1 \\ 10&1&10&1&10&1&10&1&10&1 \end{bmatrix}

The above table indicates that to get a^n \equiv 1, the power can stop at 10, one less than the modulus. According to Fermat’s theorem, this is always the case as long as the modulus is a prime number and as long as the base a is a number that is not divisible by the modulus.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

The following is a statement of the theorem.

Theorem 1 (Fermat’s Little Theorem)
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a with \text{GCD}(a,m)=1.

Note that \text{GCD}(a,b) refers to the greatest common divisor of the integers a and b. When \text{GCD}(a,b)=1, the integers a and b are said to be relatively prime. We also use the notation a \ \lvert \ b to mean that the integer a divides b without leaving a remainder.

In the discussion at the end of the above example, the base a is a number that is required to be not divisible by the modulus m. If the modulus m is a prime number, a is a number that is not divisible by the modulus m is equivalent to the condition \text{GCD}(a,m)=1. See the section called Variations below.

We will present below a formal proof of the theorem. The following example will make the idea of the proof clear. Let m=11. Let a=3. Calculate the following 10 numbers:

    a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a

For each of the above numbers, find the least residue modulo m=11. The following shows the results.

    \displaystyle \begin{aligned} \text{ }&1 \cdot 3 \equiv 3 \ \ (\text{mod} \ 11) \\&2 \cdot 3 \equiv 6 \ \ (\text{mod} \ 11) \\&3 \cdot 3 \equiv 9 \ \ (\text{mod} \ 11) \\&4 \cdot 3 \equiv 1 \ \ (\text{mod} \ 11) \\&5 \cdot 3 \equiv 4 \ \ (\text{mod} \ 11) \\&6 \cdot 3 \equiv 7 \ \ (\text{mod} \ 11) \\&7 \cdot 3 \equiv 10 \ \ (\text{mod} \ 11) \\&8 \cdot 3 \equiv 2 \ \  (\text{mod} \ 11) \\&9 \cdot 3 \equiv 5 \ \ (\text{mod} \ 11) \\&10 \cdot 3 \equiv 8 \ \  (\text{mod} \ 11) \end{aligned}

The above calculation shows that the least residues of a, 2a, 3a, 4a, 5a, 6a, 7a, 8a, 9a, 10a are just an rearrangement of 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. So we have:

    a \cdot 2a \cdot 3a \cdot 4a \cdot 5a \cdot 6a \cdot 7a \cdot 8a \cdot 9a \cdot 10a \equiv 1 \cdot 2 \cdot  3 \cdot  4 \cdot  5 \cdot  6 \cdot  7 \cdot  8 \cdot  9 \cdot  10 \ \ (\text{mod} \ 11)

    a^{10} \ 1 \cdot 2 \cdot  3 \cdot  4 \cdot  5 \cdot  6 \cdot  7 \cdot  8 \cdot  9 \cdot  10 \equiv 1 \cdot 2 \cdot  3 \cdot  4 \cdot  5 \cdot  6 \cdot  7 \cdot  8 \cdot  9 \cdot  10 \ \ (\text{mod} \ 11)

Because 10! (10 factorial) is relatively prime with 11, we can cancel it out on both side of the congruence equation. Thus we have a^{10} \equiv 1 \ (\text{mod} \ 11) for a=3.

The above example has all the elements of the proof that we will present below. The basic idea is that whenever a and the modulus m are relatively prime, taking the least residues of a, 2a, 3a, \cdots, (m-1)a modulo m produces the numbers 1,2,3,\cdots,m-1 (possibly in a different order).

We have the following lemma.

Lemma 2
Let m be a prime number. Let a be a positive integer that is relatively prime with m, i.e., \text{GCD}(a,m)=1. Then calculating the least residues of the number a, 2a, 3a, \cdots, (m-1)a modulo m gives the numbers 1,2,3,\cdots,m-1.

Proof of Lemma 2

Let b_1,b_2,b_3,\cdots,b_{m-1} be the least residues of a, 2a, 3a, \cdots, (m-1)a modulo m. That is, for each j, b_j is the number with 0 \le b_j \le m-1 such that b_j \equiv j \cdot a \ (\text{mod} \ m). Our goal is to show that b_1,b_2,b_3,\cdots,b_{m-1} are the numbers 1,2,3,\cdots,m-1. To this end, we need to show that each b_j satisfies 1 \le b_j \le m-1 and that the numbers b_j are distinct.

First of all, b_j \ne 0. Suppose b_j=0. Then 0 \equiv j \cdot a \ (\text{mod} \ m) and m \lvert j \cdot a. By Euclid’s lemma, either m \ \lvert \ j or m \ \lvert \ a. Since \text{GCD}(a,m)=1, m \not \lvert \ a. So m \ \lvert \ j. But j is a positive integer less than m. So we have a contradiction. Thus each b_j satisfies 1 \le b_j \le m-1.

Now we show the numbers b_1,b_2,b_3,\cdots,b_{m-1} are distinct (the list has exactly m-1 numbers). To this end, we need to show that b_i \ne b_j when i \ne j. Suppose we have b_i=b_j and i \ne j. . Then i \cdot a \equiv j \cdot a \ (\text{mod} \ m). Since a and m are relatively prime, there is a cancelation law that allows us to cancel out a on both sides. Then we have i \equiv j \ (\text{mod} \ m). This means that m \ \lvert \ (i-j). Since i and j are positive integers less than the modulus m, for m \ \lvert \ (i-j) to happen, i must equals j, contradicting i \ne j. It follows that b_1,b_2,b_3,\cdots,b_{m-1} are distinct.

Taking stock of what we have so far, we have shown that \left\{b_1,b_2,b_3,\cdots,b_{m-1} \right\} \subset \left\{1,2,3,\cdots,m-1 \right\}. Both sides of the set inclusion have m-1 distinct numbers. So both sides of the set inclusion must equal. \blacksquare

We now prove Fermat’s little theorem.

Proof of Theorem 1

Let m be a prime number. Let a be a positive integer such that \text{GCD}(a,m)=1. By Lemma 2, the least resides of a, 2a, 3a, \cdots, (m-1)a modulo m are the numbers 1,2,3,\cdots,m-1. Thus we have the following congruence equations:

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

    a^{m-1} \ 1 \cdot 2 \cdot  3 \cdots \cdot  (m-1) \equiv 1 \cdot 2 \cdot  3 \cdots   \cdot  (m-1) \ \ (\text{mod} \ m)

Just as in the earlier example, we can cancel out (m-1)! on both sides of the last congruence equation. Thus we have a^{m-1} \equiv 1 \ (\text{mod} \ m). \blacksquare

___________________________________________________________________________________________________________________

Variations

There are several ways to state the Fermat’s little theorem.

Theorem 3
If m is a prime number, then a^{m} \equiv a \ (\text{mod} \ m) for any integer a.

Theorem 3 is a version of the Fermat’s theorem that is sometimes stated instead of Theorem 1. It has the advantage of being valid for all integers a without having the need to consider whether a and the modulus m are relatively prime. It is easy to see that Theorem 3 implies Theorem 1. On the other hand, Theorem 3 is a corollary of Theorem 1.

To see that Theorem 3 follows from Theorem 1, let m be prime and a be any integer. Suppose a and the modulus m are not relatively prime. Then they have a common divisor d>1. Since m is prime, d must be m. So a is an integer multiple of m. Thus m divides both a and any power of a. We have a^{n} \equiv a \ (\text{mod} \ m) for any integer n. In particular, a^{m} \equiv a \ (\text{mod} \ m). The case that a and the modulus m are relatively prime follows from Theorem 1.

We now consider again the versions that deal with a^{m-1} \equiv 1. The following is a side-by-side comparison of Theorem 1 with another statement of the Fermat’s little theorem. Theorem 1 is re-labeled as Theorem 4a.

Theorem 4a (= Theorem 1)
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a with \text{GCD}(a,m)=1.

Theorem 4b
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a that is not divisible by m.

The equivalence of these two versions follows from the fact that for any prime number m, \text{GCD}(a,m)=1 if and only if a is not divisible by m. It is straightforward to see that if \text{GCD}(a,m)=1, then a is not divisible by m. For the converse to be true, m must be a prime number.

Since any integer a is congruent modulo m to some r with 0 \le r \le m-1, the following version is also an equivalent statement of the Fermat’s little theorem.

Theorem 4c
If m is a prime number, then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a such that 1 \le a \le m-1.

___________________________________________________________________________________________________________________

The Converse

It is a natural question to ask whether the converse of the Fermat’s little theorem is true. In many sources, it is stated that the converse is not true. It turns out that the answer depends on the versions. The converse of Theorem 4a is not true, while the converse of Theorem 4b and the converse of Theorem 4c are true. Let’s compare the following statements about the positive integer m:

    a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a with \text{GCD}(a,m)=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

    a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a that is not divisible by m \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Statement (1) is the conclusion of Theorem 4a, while statement (2) is the conclusion of Theorem 4b.

The statement (2) is a stronger statement. Any positive integer m that satisfies (2) would satisfy (1). This is because the set of all integers a for which \text{GCD}(a,m)=1 is a subset of the set of all integers a for which a is not divisible by m.

However, statement (1) does not imply statement (2). Any composite positive integer m that satisfies (1) is said to be a Carmichael number. Thus any Carmichael number would be an example showing that the converse of Theorem 4a is not true. There are infinitely many Carmichael numbers, the smallest of which is 561= 3 \cdot 11 \cdot 17. See the blog post Introducing Carmichael numbers for a more detailed discussion.

Any positive integer m satisfying statement (2) is a prime number. Thus the converse of Theorem 4b is true. We have the following theorem.

Theorem 5
Let m be an integer with m>1. Then m is a prime number if and only if statement (2) holds.

Proof of Theorem 5

The direction \Longrightarrow is Theorem 4b. To show \Longleftarrow, we show the contrapositive, that is, if m is not a prime number, then statement (2) does not hold, i.e., there is some a not divisible by m such that a^{m-1} \not \equiv 1 \ (\text{mod} \ m).

Suppose m is not prime. Then m has a divisor a where 1<a<m. We claim that a^{m-1} \not \equiv 1 \ (\text{mod} \ m). By way of a contradiction, suppose a^{m-1} \equiv 1 \ (\text{mod} \ m). Then m \ \lvert \ (a^{m-1}-1). Since a \ \lvert \ m, we have a \ \lvert \ (a^{m-1}-1). So a^{m-1}-1=a \cdot j for some integer j. Now we have a \cdot (a^{m-2}-j)=1. This implies that a divides 1. This is impossible since 1<a. This establishes the direction \Longleftarrow. \blacksquare

As a Carmichael number, 561 satisfies statement (1). However it would not satisfy statement (2). By the proof of Theorem 5, if a is a prime factor of 561, then a^{560} \not \equiv 1 \ (\text{mod} \ 561). Note that 3^{560} \not \equiv 1 \ (\text{mod} \ 561) since 3 is a divisor of 561. In fact, 3^{560} \equiv  375 \ (\text{mod} \ 561) and 11^{560} \equiv 154 \ (\text{mod} \ 561). We also have 17^{560} \equiv 34 \ (\text{mod} \ 561). Thus statement (1) is a weaker statement.

Any statement for the Fermat’s little theorem can be used as a primality test (Theorems 4a, 4b or 4c). On the face of it, Theorem 5 seems like an improvement over Theorem 4a, 4b or 4c since Theorem 5 can go both directions. However, using it to show that m is prime would require checking a^{m-1} \equiv 1 \ (\text{mod} \ m) for all a with 1 < a \le m-1. If m has hundreds of digits, this would be a monumental undertaking! Thus this primality test has its limitation both in terms of practical considerations and the possibility of producing false positives.

__________________________________________________________________________________________________________________

\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