An elementary algorithm for finding primitive roots

In the previous post Finding Primitive Roots, we demonstrate one approach for finding all primitive roots of a prime modulus. In this post, we summarize the ideas behind that example.

Throughout this discussion m is a positive integer that is used as the modulus for modular arithmetic, and a is assumed to be a positive integer that is relatively prime to m such that 0 \le a \le m-1.

According to Fermat’s little theorem, if the modulus m is prime, then a^{m-1} \equiv 1 \ (\text{mod} \ m). If the modulus is relaxed to include non-prime integers as well, then we have Euler’s theorem which states that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) where \phi(m) is Euler’s phi function. For any modulus m, \phi(m) is simply the numbers of possible values of a that are relatively prime to m. For example, \phi(m)=10 if m=11 and \phi(m)=4 if m=10.

So it is always the case that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m). Another way to say this is that the number \phi(m) is always a solution to the following congruence equation.

    \displaystyle a^x \equiv 1 \ (\text{mod} \ m) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

With this above discussion in mind, we define the notion of order. The order of a modulo m is the least positive integer solution to the congruence equation (1).

Furthermore, the number a is said to be a primitive root modulo m if the least positive integer solution to (1) is \phi(m).

Note that even though the notions of order and primitive root are defined here for integers a that are relatively prime to m with 0 \le a \le m-1, the definitions are also valid for positive a outside the range 0 \le a \le m-1. Relaxing the definitions can make some proofs go easier (e.g. Theorem 2 below).

___________________________________________________________________________________________________________________

An Approach in Finding Primitive Roots

We now summarize the ideas discussed in the previous post Finding Primitive Roots.

Recall that a is a positive integer less than m that is relatively prime to m. How do we check if a is a primitive root? On the face of it, we need to check that no positive integer less than \phi(m) is a solution to equation (1). It turns out that we only need to check positive integers less than \phi(m) that are divisors of \phi(m). We have the following theorem.

    Theorem 1

      The following conditions are equivalent.

      1. The number a is a primitive root modulo m.
      2. Every positive divisor k of \phi(m) with k < \phi(m) is not a solution of the congruence equation (1).

\text{ }
If we know that there exists a primitive root for a modulus, the followng theorem tells us how to find the other primitive roots.

    Theorem 2

      Suppose the number a is a primitive root modulo m. Then there are exactly \phi(\phi(m)) many primitive roots modulo m. They are obtained by finding the least residues of the numbers a^j where the exponents j are taken from the following set.

        \left\{j: 1 \le j \le \phi(m) \text{ and } j \text{ is relatively prime to } \phi(m) \right\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

Thus the above two theorems taken together form an algorithm for finding primitve roots of a modulus (if one is known to exist to begin with). We can use Theorem 1 to find a primitive root. Once we have found one, we can raise it to exponents that are relatively prime to the number \phi(m) to find the remaining primitive roots. Since there are \phi(\phi(m)) many positive integers that are less than \phi(m) and relatively prime to \phi(m), there are \phi(\phi(m)) many primitive roots modulo m (if one exists).

Before proving the theorems, let’s look at a quick example.

For m=11, \phi(11)=10. The candidates for primitive roots modulo m=11 are in the set \left\{2,3,4,\cdots,10 \right\}. The divisors of \phi(11)=10 are 1,2,5. According to Theorem 1, we only need to raise these numbers to exponents that are divisors of \phi(11)=10.

Note that 2^1 \equiv 2 \ (\text{mod} \ 11), 2^2 \equiv 4 \ (\text{mod} \ 11) and 2^5 \equiv 10 \ (\text{mod} \ 11). Thus a=2 is a primitive root modulo m=11.

The positive integers that are less than \phi(11)=10 and that are relatively prime to \phi(11)=10 are 1, 3, 7, 9. So there are four primitive roots modulo m=11. They are:

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

___________________________________________________________________________________________________________________

Proof of Theorems

Proof of Theorem 1

The direction 1 \Longrightarrow 2 is clear. If a is a primitive root modulo m, then by definition, no positive integer less than \phi(m) can be a solution to the congruence equation (1).

2 \Longrightarrow 1
Let h be the order of a modulo m. The key to the proof is that h must be a divisor of \phi(m) (see Theorem 4 and Corollary 5 in the post Defining Primitive Root). For the sake of completeness, we provide the proof here.

Since h is the least positive solution of the congruence equation (1), h \le \phi(m). Using the division algorithm, we have \phi(m)=q \cdot h+r for some integers q and r where 0 \le r <h. We have the following calculation.

    1 \equiv a^{\phi(m)}=(a^h)^q \cdot a^r \equiv (1)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

So we have a^r \equiv 1 \ (\text{mod} \ m) and 0 \le r <h. Since h is the least positive solution of (1), the only possibility is that r=0. Hence \phi(m)=q \cdot h and h is a divisor of \phi(m).

Now back to the proof for 2 \Longrightarrow 1. We claim that h=\phi(m), implying that a is a primitive root modulo m. If h<\phi(m), then h is a positive divisor of \phi(m) with h<\phi(m) such that h is a solution of the congruence equation (1) (i.e. the condition 2 does not hold). Thus if condition 2 holds, condition 1 must hold. \blacksquare

Proof of Theorem 2
Theorem 2 is the combined result of Theorem 6 and Corollary 7 in the post Defining Primitive Root. To make this post as self contained as possible, we repeat the proof, showing just the essential parts.

We do need one theorem from the previous post Defining Primitive Root. Let w be a positive integer that is relatively prime to the modulus m. Let k be the order of w modulo m. Theorem 4 in this post states that for any , w^n \equiv 1 \ (\text{mod} \ m) if and only if k \ \lvert \ n.

There are exactly \phi(\phi(m)) many elements in the above set indicated by (2). So there are these many powers of a. The first thing to show is that the powers a^j are all distinct congruent modulo m. Hence their least residues are also distinct.

To see this, suppose a^j \equiv a^i \ (\text{mod} \ m) where i, j \le \phi(m) with i \le j. We want to show i=j. Suppose that i<j. Since a^i is relatively prime to m, we can cancel out a^i on both sides and obtain a^{j-i} \equiv 1 \ (\text{mod} \ m). Since j-i<\phi(m) and a is a primitive root modulo m, a^{j-i} \not \equiv 1 \ (\text{mod} \ m). So i=j. Thus if i \ne j, then a^j \not \equiv a^i \ (\text{mod} \ m).

The next thing to show is that a^j is a primitive root modulo m for any j in the above set (2). Suppose j is one such element of the set (2). Then j and \phi(m) are relatively prime.

Let h be the order of a^j modulo m. We have a^{j \cdot h}=(a^h)^j \equiv 1 \ (\text{mod} \ m). Since a is a primitive root modulo m, it follows that \phi(m) \ \lvert \ j \cdot h (according Theorem 4 in Defining Primitive Root). Since \phi(m) and j are relatively prime, \phi(m) \ \lvert \ h.

On the other hand, (a^j)^{\phi(m)}=(a^{\phi(m)})^j \equiv 1 \ (\text{mod} \ m). Since h is the order of a^j, it follows that h \ \lvert \ \phi(m) (also using Theorem 4 in Defining Primitive Root).

With \phi(m) \ \lvert \ h and h \ \lvert \ \phi(m), we have h=\phi(m). Thus a^j is a primitive root modulo m and so is its least residue. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

Defining Primitive Root

In this post, we define the notion of primitive root and prove some elementary results. Instead of jumping right into the definition, we take a leisurely approach by first looking at some of the related basic notions.

___________________________________________________________________________________________________________________

Setting Up the Scene

Two positive integers a and b are relatively prime if they do not share any prime factors, i.e., their greatest common divisor is one (the only positive integer that can divide both numbers is one). For example, a=9 and b=14 are relatively prime, as are a=9 and b=35. If a and b are relatively prime, we also say that a is relatively prime to b or b is relatively prime to a. Our notation for greatest common divisor is \text{GCD}(a,b).

In working with modular arithmetic where the modulus is the positive integer m, every integer is congruent modulo m to exactly one number in the set \left\{0,1,2,\cdots,m-1 \right\}. The numbers in this set are called the least residues modulo m. In doing modulus m calculation, for some purposes we only need to reduce the result to one number in this set. For convenience, we use the notation \mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}.

An even more interesting set is the set of all integers a in \mathbb{Z}_m such that a and the modulus m are relatively prime. To facilitate the discussion, we describe this set as follows:

    \displaystyle \begin{aligned} (\mathbb{Z}_m)^*&=\left\{a \in \mathbb{Z}_m: a \text{ is relatively prime to } m \right\} \\&=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\}  \end{aligned}

When the modulus m is a prime number, (\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}, the non-zero elements of \mathbb{Z}_m. The following theorem gives some indication why (\mathbb{Z}_m)^* is an interesting set, which provides alternative characterizations of (\mathbb{Z}_m)^*.

    Theorem 1

      Let a be an integer in \mathbb{Z}_m. The following conditions are equivalent.

      1. \text{GCD}(a,m)=1.
      2. There is a b \in \mathbb{Z}_m such that a \cdot b \equiv 1 \ (\text{mod} \ m).
      3. Some positive power of a modulo m is 1, i.e., a^n \equiv 1 \ (\text{mod} \ m) for some positive integer n.

\text{ }

The proof of Theorem 1 can be found in the post Euler’s phi function, part 1.

The Euler’s phi function, denoted by \phi(m), is the number of integers a where 0 \le a \le m-1 such that a and the modulus m are relatively prime. In light of the above discussion, \phi(m) is the number of elements in the set (\mathbb{Z}_m)^*. It is also the case that \phi(m) is the number of elements in \mathbb{Z}_m that satisfies any one of the three conditions in Theorem 1.

___________________________________________________________________________________________________________________

Defining Primitive Root

When we are interested in the power of a number being one congruence modulo m, according to Theorem 1, the base has to be a number that is relatively prime to the modulus. We have already come across two such situations – Fermat’s little theorem and its generalization, Euler’s theorem.

    Theorem 2 (Fermat’s little theorem)

      Let the modulus m be a prime number. Then a^{m-1} \equiv 1 \ (\text{mod} \ m) for any integer a that is relatively prime to m.

\text{ }

    Theorem 3 (Euler’s theorem)

      It is the case that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) for any integer a that is relatively prime to m.

\text{ }

Theorem 2 follows from Theorem 3, which is proved in the post Euler’s phi function, part 1.

Definitions
We now define the notion of primitive root. Let a be an integer in \mathbb{Z}_m that is relatively prime to the modulus m. Based on the above theorems, a^k \equiv 1 \ (\text{mod} \ m) for some positive integer k. By the order of a modulo m, we mean the least positive integer k such that a^k \equiv 1 \ (\text{mod} \ m). The number a is a primitive root modulo m if the order of a modulo m is the number \phi(m).

By Theorem 3, the order of a modulo m is always \le \phi(m). We will see below that the order always divides \phi(m) (see Theorem 4).

One comment. The notions of order and primitive roots are defined above for integers in \mathbb{Z}_m. In actuality, the two notations can be defined for all positive integers. It is just that we are interested in finding primitive roots among the residues, i.e., the elements of the set \mathbb{Z}_m. In some cases, it will be helpful to think of orders of numbers outside of \mathbb{Z}_m and think of numbers outside of \mathbb{Z}_m as primitive roots (e.g. in the proof of Theorem 6 below).

Suppose that the modulus m is a prime number. Fermat’s little theorem tells us that a^{m-1} \equiv 1 \ (\text{mod} \ m) for any a that is relatively prime to m. Is m-1 the only exponent for which the power of a is one? Take m=11. The following table gives the powers of a modulus m=11 where 1 \le a \le 10.

    \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 shows that for a=2,6,7,8, the number 10 is the least exponent for which the power of a is one. In other words, the order for these a is \phi(11)=10. The numbers a=2,6,7,8 are primitive roots modulo m=11. The other values of a are not primitive roots. The order for a=1 is 1. The order for a=10 is 2. The order for a=3,4,5,9 is 5.

Note that in the above table, for the numbers a that are primitive roots, the set \left\{a^1,a^2,a^3,\cdots,a^{\phi(11)} \right\} equals the set \left\{1,2,3,\cdots,10 \right\}. So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Let’s look at a modulus that is not prime. Take m=10. The following table gives the powers of a modulus m=10 where 1 \le a \le 9.

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

Note that \phi(10)=4 since (\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\} is the set of all the least residues that are relatively prime to m=10. In terms of powers of a, we should only focus on \left\{1,3,7,9 \right\}. The following is the reduced table.

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

Note that a^4 \equiv 1 \ (\text{mod} \ 10) for all four a. But only a=3,7 are primitive roots modulo m=10.

Also note that in the above table, for the numbers a that are primitive roots, the set \left\{a^1,a^2,a^3,a^4 \right\} equals the set \left\{1,3,7,9 \right\}. So a primitive root generates by powering all the least residues that are relatively prime to the modulus.

Not all moduli have primitive roots. Take m=8. The least residues that are relatively prime to m=8 are the set \left\{1,3,5,7 \right\}. Note that a^2 \equiv 1 \ (\text{mod} \ 8) for every a in this set. Thus no number a in this set can have order = \phi(8)=4.

___________________________________________________________________________________________________________________

Elementary Results

One observation can be made about the above small tables for m=11 and m=10 is that all exponents for which the power of a is one are the multiples of the order. We have the following theorem.

    Theorem 4

      Let a be an integer where 0 \le a \le m-1 such that a is relatively prime to the modulus m. Suppose k is the order of the number a modulo m. Then a^n \equiv 1 \ (\text{mod} \ m) if and only if n is a multiple of k.

Proof of Theorem 4

\Longleftarrow
This direction is clear. If n=q \cdot k for some integer q, then a^n=(a^k)^q \equiv 1 \ (\text{mod} \ m).

\Longrightarrow
Suppose that a^n \equiv 1 \ (\text{mod} \ m). By the division algorithm, we have n=q \cdot k+r for some integers q and r where 0 \le r <k. We have the following:

    a^n=(a^k)^q \cdot a^r \equiv a^r \ (\text{mod} \ m)

Since r<k and a^r \equiv 1 \ (\text{mod} \ m), it must be the case that r=0, implying that n=q \cdot k. \blacksquare

We have the following corollary.

    Corollary 5

      Let a be an integer where 0 \le a \le m-1 such that a is relatively prime to the modulus m. Suppose k is the order of the number a modulo m. Then \phi(m) is a multiple of k.

Another observation from the above small tables is that a primitive root, through powering, is a generator of the least residues that are relatively prime to the modulus.

    Theorem 5

      Let a be an integer where 0 \le a \le m-1 such that a is relatively prime to the modulus m. The following conditions are equivalent.

      1. The number a is a primitive root modulo m.
      2. The set \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\}, where each a^j is considered as the least residues modulo m, is precisely the set (\mathbb{Z}_m)^*.

\text{ }

Recall that (\mathbb{Z}_m)^* is the set of all a \in \mathbb{Z}_m=\left\{0,1,2,3,\cdots,m-1 \right\} such that a is relatively prime to m.

Proof of Theorem 5

1 \Longrightarrow 2
Suppose that the number a is a primitive root modulo m. The first step in showing condition 2 is to show that the \phi(m) numbers in the set \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} are distinct congruent modulo m. Then it follows that their least residues modulo m are distinct too.

Suppose a^j \equiv a^i \ (\text{mod} \ m) where i,j  \le \phi(m). We want to show that i=j. Suppose i<j. Then cancel out a^i on both sides of the equation since a^i is relatively prime to m. We have a^{j-i} \equiv 1 \ (\text{mod} \ m). But j-i<\phi(m). Since a is a primitive root modulo m, we cannot have a^{j-i} \equiv 1 \ (\text{mod} \ m). So it must be the case that j=i. So if a^j \equiv a^i \ (\text{mod} \ m), then i=j. Equivalently, if i \ne j, a^j \not \equiv a^i \ (\text{mod} \ m). Thus the least residues modulo m of the values in \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} are distinct too.

Since a^i is relatively prime to m, its least residue is also relatively prime to m. Now the least residues modulo m of the values in \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} consist of \phi(m) numbers inside (\mathbb{Z}_m)^*, which is also a set of \phi(m) many numbers. So the two sets must equal.

2 \Longrightarrow 1
We show the contrapositive of 2 \Longrightarrow 1. Suppose that the order of a modulo m is j where 1 \le j<\phi(m). So a^j \equiv 1 \ (\text{mod} \ m) and a^{j+1} \equiv a \ (\text{mod} \ m). So a and a^{j+1} are two elements in the set \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} that are congruent to each other. This means that the least residues of \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} have less than \phi(m) many values. In other words, the number a, through powering, cannot generate all the least residues that are relatively prime to the modulus m. \blacksquare

The following theorem and corollary give the number of primitive root modulo m as long as it is known that there is a primitive root modulo m.

    Theorem 6

      Let a be a primitive root modulo m. Then for any positive integer k, the least residue of a^k is a primitive root modulo m if and only if k is relatively prime to \phi(m).

Proof of Theorem 6

\Longrightarrow
Suppose that k is not relatively prime to \phi(m). So d=\text{GCD}(k,\phi(m))>1. Then we have:

    \displaystyle (a^k)^{\frac{\phi(m)}{d}}=(a^{\phi(m)})^{\frac{k}{d}} \equiv 1 \ (\text{mod} \ m)

With \displaystyle b=\frac{\phi(m)}{d}<\phi(m) and (a^k)^b \equiv 1 \ (\text{mod} \ m), it follows that a^k is not a primitive root modulo m. Hence the least residue of a^k modulo m is also not a primitive root. Thus if the least residue of a^k is a primitive root modulo m, it must be that \text{GCD}(k,\phi(m))=1.

\Longleftarrow
Suppose \text{GCD}(k,\phi(m))=1. Let \alpha be the order of a^k modulo m. By the definition of order, a^{k \cdot \alpha}=(a^k)^\alpha \equiv 1 \ (\text{mod} \ m). Based on the fact that the order of a modulo m is \phi(m), we have \phi(m) \ \lvert \ k \cdot \alpha (also using Theorem 4). Since \text{GCD}(k,\phi(m))=1, it must be the case that \phi(m) \ \lvert \ \alpha.

On the other hand, (a^k)^{\phi(m)}=(a^{\phi(m)})^k \equiv 1 \ (\text{mod} \ m). Using the fact that the order of a^k is \alpha (and using Theorem 4), \alpha \ \lvert \ \phi(m).

With \phi(m) \ \lvert \ \alpha and \alpha \ \lvert \ \phi(m), it follows that \alpha = \phi(m). This implies that a^k is a primitive root modulo m, and so is its least residue modulo m. \blacksquare

    Corollary 7

      Suppose that there exists a primitive root modulo m. Then there are exactly \phi(\phi(m)) many primitive roots modulo m.

Proof of Corollary 7

Let a be a primitive root modulo m. By Theorem 6, the least residue of a^k is a primitive roots modulo m if and only if k is relatively prime to the number \phi(m). There are precisely \phi(\phi(m)) many such numbers k.

Furthermore, according to Theorem 5, the least residues of the values in \left\{a^1,a^2,a^3,\cdots,a^{\phi(m)} \right\} are all distinct. Thus the least residues of the powers a^k for the \phi(\phi(m)) many k are primitive roots modulo m. \blacksquare

___________________________________________________________________________________________________________________

An Algorithm

The theorems and corollaries in this post form an elementary algorithm for finding primitive roots of a modulus (if one is known to exist). The algorithm is described in the post An elementary algorithm for finding primitive roots. An example is given in the post Finding Primitive Roots.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Euler’s phi function, part 1

This is our first post of an introductory discussion on Euler’s phi function. The next post on phi function is here.

___________________________________________________________________________________________________________________

Setting Up the Scene

The starting point of this discussion is the relative primality of two integers. Two positive integers a and b are relatively prime if 1 is the only common divisor of a and b. Note that a and b need not be prime. For example, a=9 and b=14 are relatively prime, as are a=9 and b=35. It is clear that a and b are relatively prime if and only if they share no common prime factors. The last point is equivalent to the condition that the greatest common divisor of a and b is 1. Our notation for greatest common divisor is \text{GCD}(a,b).

If a and b are relatively prime, we also say that a is relatively prime to b or b is relatively prime to a. In the remainder of the blog post, m is always a positive integer that is the modulus used for modular arithmetic.

In modular arithmetic where the modulus is m, we only need to focus on m distinct numbers, namely the elements in the set \left\{0,1,2,\cdots,m-1 \right\}. Any integer is congruent modulo m to exactly one element of this set (the elements of this set are also called the least residues modulo m). For convenience, we use the notation \mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}.

An even more interesting set is the set of all integers a in \mathbb{Z}_m such that a and the modulus m are relatively prime. To facilitate the discussion, we describe this set as follows:

    (\mathbb{Z}_m)^*=\left\{a \in \mathbb{Z}_m:\text{GCD}(a,m) =1 \right\}

When the modulus m is a prime number, (\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}, the non-zero elements of \mathbb{Z}_m. When the modulus is not prime, there are fewer least residues that are relatively prime to the modulus. The following shows (\mathbb{Z}_m)^* for the first several integers.

    (\mathbb{Z}_{2})^*=\left\{1 \right\}

    (\mathbb{Z}_{3})^*=\left\{1,2 \right\}

    (\mathbb{Z}_{4})^*=\left\{1,3 \right\}

    (\mathbb{Z}_{5})^*=\left\{1,2,3,4 \right\}

    (\mathbb{Z}_{6})^*=\left\{1,5 \right\}

    (\mathbb{Z}_{7})^*=\left\{1,2,3,4,5,6 \right\}

    (\mathbb{Z}_{8})^*=\left\{1,3,5,7 \right\}

    (\mathbb{Z}_{9})^*=\left\{1,2,4,5,7,8 \right\}

    (\mathbb{Z}_{10})^*=\left\{1,3,7,9 \right\}

    (\mathbb{Z}_{11})^*=\left\{1,2,3,4,5,6,7,8,9,10 \right\}

The following theorem gives some indication why (\mathbb{Z}_m)^* is an interesting set, which provides alternative characterizations of (\mathbb{Z}_m)^*.

Theorem 1

Let a be an integer in \mathbb{Z}_m. The following conditions are equivalent.

  1. \text{GCD}(a,m)=1.
  2. There is a b \in \mathbb{Z}_m such that a \cdot b \equiv 1 \ (\text{mod} \ m).
  3. Some positive power of a modulo m is 1, i.e., a^n \equiv 1 \ (\text{mod} \ m) for some positive integer n.

\text{ }

The number b indicated in condition 2 is said to be the multiplicative inverse of a. Theorem 1 says that only the least residues that are relatively prime to the modulus have multiplicative inverses. Condition 3 tells us that to have a power congruent to one, which is of interest in many situations, the base must be relatively prime to the modulus.

We need the following lemma to prove Theorem 1.

Lemma 2

If \text{GCD}(a,m)=1, then for any positive integer n, a^n is also relatively prime to m.

Proof of Lemma 2
Suppose \text{GCD}(a,m)=1. By the extended Euclidean algorithm, we have the following:

    ax+my=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

for some integers and x and y.

We prove by induction on n. When n=1, lemma is true. Suppose that a^n is relatively prime to m where n \ge 1. We show that a^{n+1} is relatively prime to m. Multiple both sides of (1) by a^n. We have a^{n+1} x+m (ya^n)=a^n. Let d=\text{GCD}(a^{n+1},m). Note that d is a divisor of the left-hand side of a^{n+1} x+m (ya^n)=a^n. So d is a divisor of a^n. Now we know that d is a common divisor of a^n and m. Then d=1, which means that a^{n+1} is relatively prime to m. \blacksquare

Proof of Theorem 1

\bold 3 \bold \Longrightarrow \bold 2
Suppose that a^n \equiv 1 \ (\text{mod} \ m) for some positive integer n. If n=1, then let b=1. If n>1, then let b=a^{n-1}. Either way, there is b \in \mathbb{Z}_m such that a \cdot b \equiv 1 \ (\text{mod} \ m).

\bold 2 \bold \Longrightarrow \bold 1
Suppose there is a b \in \mathbb{Z}_m such that a \cdot b \equiv 1 \ (\text{mod} \ m). Then we have

    ab+my=1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

for some integer y.

Let d=\text{GCD}(a,m). Since d divides both numbers in the left-hand side of (2), d \ \lvert \ 1. Then d=1.

\bold 1 \bold \Longrightarrow \bold 3
Suppose \text{GCD}(a,m)=1. Consider the a^1,a^2,a^3,\cdots and then consider their least residues modulo m. By Lemma 2, each a^n and m are relatively prime. Hence the least residue of a^n and m are also relatively prime. But there are only finitely many least residues modulo m. So there exist positive integers i<j the least residues of a^i and a^j are identical.

We have a^j \equiv a^i \ (\text{mod} \ m). Since a^i and m are relatively prime, we can cancel out a^i on both sides. Thus a^{j-i} \equiv 1  \ (\text{mod} \ m). \blacksquare

___________________________________________________________________________________________________________________

Euler’s Phi Function

The Euler’s phi function, denoted by \phi(m), is the number of integers a where 0 \le a \le m-1 such that a and the modulus m are relatively prime. In light of the above discussion, \phi(m) is the number of elements in the set (\mathbb{Z}_m)^*. It is also the case that \phi(m) is the number of elements in \mathbb{Z}_m that satisfies any one of the three conditions in Theorem 1.

If the modulus m is a prime number, then \phi(m)=m-1. The following shows several values of \phi(m).

    \displaystyle \begin{aligned} &\phi(2)=1 \\&\phi(3)=2 \\&\phi(4)=2 \\&\phi(5)=4 \\&\phi(6)=2 \\&\phi(7)=6 \\&\phi(8)=4 \\&\phi(9)=6 \\&\phi(10)=4 \\&\phi(11)=10 \end{aligned}

When the modulus m is a prime number, Fermat’s little theorem tells us that a^{\phi(m)}=a^{m-1} \equiv 1 \ (\text{mod} \ m) for any a \in (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,m-1 \right\}. This fact is true even when the modulus is not prime if the power is kept as \phi(m). We have the following theorem.

Theorem 3 (Euler’s Theorem)

We have a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) for any integer a that is relatively prime to the modulus m.

Theorem 3 can also be stated as: a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) for any a \in (\mathbb{Z}_m)^*. The proof is amazingly similar to that of Fermat’s little theorem (see the post Proving Fermat’s Little Theorem). We use the following lemma in proving Theorem 3.

Lemma 4

If integers h and k satisfy any condition in Theorem 1, then so does the product h \cdot k.

Proof of Lemma 4

Since the 3 conditions in Theorem 1 are equivalent, it does not matter which one we pick. Condition 2 is probably the most convenient. So we show that if h has a multiplicative inverse and k has a multiplicative inverse, then h \cdot k has a multiplicative inverse modulo m.

Suppose h \cdot h_0 \equiv 1 \ (\text{mod} \ m) and k \cdot k_0 \equiv 1 \ (\text{mod} \ m) for some integers h_0 and k_0 in \mathbb{Z}_m. We multiply the two congruences and obtain:

    h \cdot h_0 \cdot k \cdot k_0=(h \cdot k) \cdot (h_0 \cdot k_0) \equiv 1 \ (\text{mod} \ m)

if h_0 \cdot k_0 is in \mathbb{Z}_m, then it is the multiplicative inverse of h \cdot k. If not, then take the least residue mod m. \blacksquare

Proof of Theorem 3

Let a be an integer that is relatively prime to the modulus m, i.e., \text{GCD}(a,m)=1. Let \left\{t_1,t_2,t_3,\cdots,t_{\phi(m)} \right\} enumerate the \phi(m) many elements of (\mathbb{Z}_m)^*. Multiply these elements by a and we have the following set:

    A=\left\{a \cdot t_1,a \cdot t_2,a \cdot t_3,\cdots,a \cdot t_{\phi(m)} \right\}

Consider the least residues modulo m of the members of the set A. We have:

    B=\left\{b_1,b_2,b_3,\cdots,b_{\phi(m)} \right\}

Note that for each b_j \in B, b_j \in \mathbb{Z}_m and b_j \equiv a \cdot t_j \ (\text{mod} \ m). We have two claims.

  • The numbers b_i and b_j are distinct whenever i \ne j.
  • Each b_j is relatively prime to the modulus m, i.e., b_j \in (\mathbb{Z}_m)^* for each j.

The first claims tells us that the set B has \phi(m) many distinct elements. The second claims tells us that the set B is a subset of (\mathbb{Z}_m)^*=\left\{t_1,t_2,t_3,\cdots,t_{\phi(m)} \right\}. Since the subset B has \phi(m) many distinct elements and (\mathbb{Z}_m)^* has \phi(m) many distinct elements, they must equal. So we have B=(\mathbb{Z}_m)^*. With this information, we have the following congruence equation.

    \displaystyle at_1 \cdot a t_2 \cdot a t_3 \cdots a t_{\phi(m)} \equiv t_1 \cdot t_2 \cdot t_3 \cdots t_{\phi(m)} \ (\text{mod} \ m)

Because each t_j is relatively prime to the modulus, we can cancel out all t_j and obtain:

    \displaystyle a^{\phi(m)} \equiv 1 \ (\text{mod} \ m)

So the theorem hinges on the two claims listed above. We now prove them one by one. To show the first claim, suppose b_i=b_j. Then a \cdot t_i \equiv a \cdot t_j \ (\text{mod} \ m). We can cancel out a on both sides since a is relatively prime to m. We have t_i \equiv t_j \ (\text{mod} \ m). Since both t_i and t_j are least residues mod m, for them to be congruent to each other, the only possibility is t_i=t_j. Thus i=j. The contrapositive of what we just show is that if i \ne j, then b_i \ne b_j. So the numbers b_j are all distinct.

To show the second claim, note that b_j \equiv a \cdot t_j \ (\text{mod} \ m). Both a and t_j are relatively prime to m. So by Lemma 4, a \cdot t_j is relatively prime to m. Hence b_j is relatively prime to the modulus m. \blacksquare

___________________________________________________________________________________________________________________

Comments

The setting for the phi function deserves some comments. The sets \mathbb{Z}_m and (\mathbb{Z}_m)^* defined above can be considered as algebraic objects.

The set \mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\} along with addition and multiplication modulo m is a ring. Thus \mathbb{Z}_m is often called the ring of integers modulo m.

Based on Theorem 1 and Lemma 4, the set (\mathbb{Z}_m)^* with the multiplication modulo m is a group, i.e., it is a set with a binary operation called multiplication such that every element has an inverse.

Let the modulus m is a prime number. As indicated above, (\mathbb{Z}_m)^*=\left\{1,2,\cdots,m-1 \right\}. An interesting angle is that \mathbb{Z}_m can be considered a commutative ring in which every non-zero element has a multiplicative inverse, i.e., \mathbb{Z}_m is a field (in fact a finite field).

Though we do not focus too much on the algebraic side of things in this blog, \mathbb{Z}_m, as a field, plays an important role in number theory and has applications in cryptography.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

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}

Using Fermat’s Little Theorem to Test Primality

Fermat’s little theorem describes a property that is common to all prime numbers. This property can be used as a way to detect the “prime or composite” status of an integer. Primality testing using Fermat’s little theorem is called the Fermat primality test. In this post, we explain how to use this test and to discuss some issues surrounding the Fermat test.

___________________________________________________________________

Describing the test

The Fermat primality test, as mentioned above, is based on Fermat’s little theorem. The following is the statement of the theorem.

    Fermat’s little theorem
    If n is a prime number and if a is an integer that is relatively prime to n, then the following congruence relationship holds:

      a^{n-1} \equiv 1 (\text{mod} \ n) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

The above theorem indicates that all prime numbers possess a certain property. Therefore if a given positive integer does not possess this property, we know for certain that this integer is not prime. Suppose that the primality of an integer n is not known. If we can find an integer a that is relatively prime to n such that a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then we have conclusive proof that n is composite. Such a number a is said to be a Fermat witness for (the compositeness of) n.

The Fermat test is closedly linked to the notations of probable primes and pseudoprimes. If the congruence relation (1) is true for n and a, then n is said to be a probable prime to base a. Furthermore, if n happens to be a composite number, then n is said to be a pseudoprime to base a. Pseudoprime prime is a composite number that possesses the prime-like property as indicated by (1) for one base a.

The Fermat primality test from a compositeness perspective is about looking for Fermat witnesses. If a Fermat witness is found, the number being tested is proved to be composite. On the other hand, the Fermat primality test, from a primality perspective, consists of checking the congruence relation (1) for several bases that are randomly selected. If the number n is found to be a probable prime to all the randomly chosen bases, then n is likely a prime number.

If the number n is in reality a prime number, then the Fermat test will always give the correct result (as a result of Fermat’s little theorem). If the number n is in reality a composite number, the Fermat test can make the mistake of identifying the composite number n as prime (i.e. identifying a pseudoprime as a prime). For most composite numbers this error probability can be made arbitrarily small (by testing a large number of bases a). But there are rare composite numbers that evade the Fermat test. Such composite numbers are called Carmichael numbers. No matter how many bases you test on a Carmichael number, the Fermat test will always output Probably Prime. Carmichael numbers may be rare but there are infinitely many of them over the entire number line. More about Carmichael numbers below.

The following describes the steps of the Fermat primality test.

    Fermat primality test
    The test is to determine whether a large positive integer n is prime or composite. The test will output one of two results: n is Composite or n is Probably Prime.

  • Step 1. Choose a random integer a \in \left\{2,3,\cdots,n-1 \right\}.
  • Step 2. Compute \text{GCD}(a,n). If it is greater than 1, then stop and output n is Composite. Otherwise go to the next step.
  • Step 3. Compute a^{n-1} \ (\text{mod} \ n).
    • If a^{n-1} \not \equiv 1 \ (\text{mod} \ n), then stop and output n is Composite.
    • If a^{n-1} \equiv 1 \ (\text{mod} \ n), then n may be a prime number. Do one of the following:
      • Return to Step 1 and repeat the process with a new a.
      • Output n is Probably Prime and stop.

    \text{ }

The exponentiation in Step 3 can be done by the fast powering algorithm. This involves a series of squarings and multiplications. Even for numbers that have hundreds of digits, the fast powering algorithm is efficient.

One comment about Step 2 in the algorithm. Step 2 could be called the GCD test for primality. If you can find an integer a such that 1<a<n and such that \text{GCD}(a,n) \ne 1, then the integer n is certainly composite. Such a number a is called a GCD witness for the compositeness of n. So the Fermat test as described above combines the GCD test and the Fermat test. We can use the Euclidean algorithm to find the GCD. If we happen to stumble upon a GCD witness, then we can try another n for a candidate of a prime number. For most composite numbers, it is not likely to stumble upon a GCD witness. Thus when using the Fermat test, it is likely that Step 3 in the algorithm is used.

An example of Fermat primality testing is the post called A primality testing exercise from RSA-100.

____________________________________________________________________________

More about the test

When using the Fermat test, what is the probability of the test giving the correct result? Or what is the probability of making an error? Because the Fermat test is not a true probabilistic primality test, the answers to these questions are conditional. In one scenario which covers most of the cases, the test works like an efficient probabilistic test. In another scenario which occurs very rarely, the Fermat test fails miserably.

As with most diagnostic tests, the Fermat test can make two types of mistakes – false positives or false negatives. For primality testing discussed in this post, we define a positive result as the outcome that says the number being tested is a prime number and a negative result as the outcome that says the number being tested is a composite number. Thus a false positive is identifying a composite number as a prime number and a false negative is identifying a prime number as a composite number.

For the Fermat test, there is no false negative. If n is a prime number in reality, the statement of Fermat’s little theorem does not allow the possibility that n be declared a composite number. Thus if the Fermat test gives a negative result, it would be a true negative. In other words, finding a Fermat witness for n is an irrefutable proof that n is composite.

However, there can be false positives for the Fermat test. This is where things can get a little tricky. A composite number n is said to be a Carmichael number if the above congruence relationship (1) holds for all bases a relatively prime to n. In other words, n is a Carmichael number if a^{n-1} \equiv 1 (\text{mod} \ n) for all a that are relatively prime to n. Saying it in another way, n is a Carmichael number if there exists no Fermat witness for n.

The smallest Carmichael number is 561. Carmichael numbers are rare but there are infinitely many of them. The existence of such numbers poses a challenge for the Fermat test. If you apply the Fermat test on a Carmichael number, the outcome will always be Probably Prime. So the Fermat test will always give a false positive when it is applied on a Carmichael number. To put it in another way, with respect to Carmichael numbers, the error probability of the Fermat test is virtually 100%!

So should a primality tester do? To keep things in perspective, Carmichael numbers are rare (see this post). If the primality testing is done on randomly chosen numbers, choosing a Carmichael number is not likely. So the Fermat test will often give the correct results. For those who are bothered by the nagging fear of working with Carmichael numbers, they can always switch to a Carmichael neutral test such as the Miller-Rabin test.

___________________________________________________________________

One bright spot about the Fermat test

There is one bright spot about the Fermat test. When applying the Fermat test on numbers that are not Carmichael numbers, the error probability can be made arbitrarily small. In this sense the Fermat test works like a true probabilistic primality test. Consider the following theorem.

    Theorem 1
    Let n be a composite integer such that it is not a pseudoprime to at least one base (i.e. n has a Fermat witness). In other words, n is not a Carmichael number. Then n is not a pseudoprime to at least half of the bases a (1<a<n) that are relatively prime to n. In other words, n is a pseudoprime to at most half of the bases a (1<a<n) that are relatively prime to n.

Theorem 1 means that the Fermat test can be very accurate on composite numbers that are not Carmichael numbers. As long as there is one base to which the composite number is not a pseudoprime (i.e. as long as there is a Fermat witness for the composite number in question), there will be enough of such bases (at least 50% of the possible bases). As a result, it is likely that the Fermat test will find a witness, especially if the tester is willing to use enough bases to test and if the bases are randomly chosen. When a base is randomly chosen, there is at least a 50% chance that the number n is not a pseudoprime to that base (i.e. the Fermat test will detect the compositeness) or putting it in another way, there is at most a 50% chance that the Fermat test will not detect the compositeness of the composite number n. So if k values of a are randomly selected, there is at most 0.5^k probability that the Fermat test will not detect the compositeness of the composite number n (i.e. making a mistake). So the probability of a false positive is at most 0.5^k. For a large enough k, this probability is practically zero.

Proof of Theorem 1
A base to which n is a pseudoprime or not a pseudoprime should be a number in the interval 1<a<n that is relatively prime to n. If n is a pseudoprime to base a, then a raised to some power is congruent to 1 modulo n. For this to happen, a must be relatively prime to the modulus n. For this reason, when we consider a base, it must be a number that is relatively prime to the composite integer n (see the post on Euler’s phi function).

Let a be a base to which n is not a pseudoprime. We make the following claim.

    Claim
    If b is a number such that 1<b<n and such that n is a pseudoprime to base b, then n is not a pseudoprime to base a \cdot b.

Since both integers a and b are assumed to be relatively prime to n, the product a \cdot b is also relatively prime to n (see Lemma 4 in this post). Now consider the congruence (ab)^{n-1} \ (\text{mod} \ n), which is derived as follows:

    (ab)^{n-1} \equiv a^{n-1} \cdot b^{n-1} \equiv a^{n-1} \not \equiv 1 \ (\text{mod} \ n)

In the above derivation, we use the fact that n is not a pseudoprime to base a and n is a pseudoprime to base b. The above derivation shows that n is not a pseudoprime to base ab.

If n is not a pseudoprime to all bases in 1<w<n, then we are done. So assume that n is a pseudoprime to at least one base. Let b_1,b_2,\cdots,b_k enumerate all bases to which n is a pseudoprime. We assume that the b_j are all distinct. So b_i \not \equiv b_j \ (\text{mod} \ n) for all i \ne j. By the above claim, the composite number n is not a pseudoprime to all the following k numbers:

    a \cdot b_1, \ a \cdot b_2, \cdots, \ a \cdot b_k

It is also clear that a \cdot b_i \not \equiv a \cdot b_j \ (\text{mod} \ n) for i \ne j. What we have just shown is that there are at least as many bases to which n is not a pseudoprime as there are bases to which n is a pseudoprime. This means that n is not a pseudoprime to at least 50% of the bases that are relatively prime to n. In other words, as long as there exists one Fermat witness for n, at least 50% of the bases are Fermat witnesses for n. It then follows that n is a pseudoprime to no more than 50% of the bases relatively prime to n. \blacksquare

There is another way to state Theorem 1. Recall that Euler’s phi function \phi(n) is defined to be the number of integers a in the interval 1<a<n that are relatively prime to n. With this in mind, Theorem 1 can be restated as the following:

    Corollary 2
    Let n be a composite integer such that it is not a pseudoprime to at least one base. Then n is not a pseudoprime to at least \displaystyle \frac{\phi(n)}{2} many bases in the interval 1<a<n.

___________________________________________________________________

Concluding remarks

Of course, Theorem 1 works only for the composite numbers that are not pseudoprime to at least one base (i.e. they are not Carmichael numbers). When you test the compositeness of a number, you do not know in advance if it is Carmichael or not. On the other hand, if the testing is done on randomly chosen numbers, it is not likely to randomly stumble upon Carmichael numbers. The Fermat test works well for the most part and often give the correct results. If one is concerned about the rare chance of a false positive in the form of a Carmichael number, then the Miller-Rabin test will be a good alternative.

Note:
The original post was written in August 10, 2013. On March 29, 2015, this post is replaced with a blog post called The Fermat primality test from the companion math crypto blog.

___________________________________________________________________
\copyright \ \ 2013 - 2015 \ \text{Dan Ma}

How to toss a coin

In this post, we demonstrate how to simulate a random coin toss using a cryptographic algorithm that was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm). Tossing a coin using a cryptographic algorithm is an example of a game of mental poker.

The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).

___________________________________________________________________________________________________________________

Setting the Algorithm

A full discussion of the algorithm used here can be found in the previous post Fermat’s Little Theorem and Mental Poker.

Andy and Becky are in different locations and they would like to simulate a random coin toss. First they need to agree on two positive integers that are to represent head and tail, say m_h for head and m_t for tail. These two numbers should be less than the prime number p discussed in the next paragraph.

They now need to encrypt the numbers before tossing the coin. Both players agree on a large prime number p. If the goal of preventing or minimizing cheating is important, the players should choose a prime number that is as large as feasible computationally speaking.

With the prime number p decided, each of the players chooses an encryption-decryption key, which is a pair of positive integers x_0 and x_1 such that

    x_0 \cdot x_1 \equiv 1 \ (\text{mod} \ p-1),

meaning that x_0 \cdot x_1=1+(p-1) \cdot k for some integer k.

Each of the players chooses such a pair of numbers. In terms of notation, Andy chooses a_0 and a_1. Becky chooses b_0 and b_1. Each player chooses the number pair independently and keeps it secret from the other player.

The number with the 0-subscript is the encryption key and the number with the 1-subscript is the decryption key. The following are the encryption functions, expressed in congruence modulo p, for Andy and Becky, respectively.

    f_a(m) \equiv m^{a_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}

    f_b(m) \equiv m^{b_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}

For example, if Andy wants to encrypt the number m, he raises m to the power of a_0 and looks for the remainder upon division by p. The remainder will be denoted by f_a(m). The function f_b(m) works similarly for Becky.

The following are the decryption functions, expressed in congruence modulo p, for Andy and Becky, respectively.

    g_a(c) \equiv c^{a_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}

    g_b(c) \equiv c^{b_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}

For example, if Andy wants to decrypt the number c=f_a(m), he raises c to the power of a_1 and looks for the remainder upon division by p. The remainder will be denoted by g_a(m), which will be the original number m. The proof of this fact is based on the Fermat’s Little Theorem (see the previous post Fermat’s Little Theorem and Mental Poker).

The function g_b(m) works similarly for Becky.

___________________________________________________________________________________________________________________

A Numerical Example

For illustration, we use a small prime number. We use p=7919. We emphasize that this is just for illustration. In an application where the chance for cheating is to be minimized, a large prime number should be used.

Andy and Becky use the following assignment for Head and Tail.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000}    \end{bmatrix}

For this illustration, Andy chooses a_0=\text{47} and a_1=\text{52,899} by letting k=\text{314} in the equation below. Becky chooses b_0=\text{71} and b_1=\text{26,319} by letting k=\text{236} in the following equation.

    x_0 \cdot x_1=1+7918 \cdot k

Andy and Becky choose these keys independently and they keep them secret without letting the other person know. Andy encrypts both the head and tail numbers as follows:

    2500^{47} \equiv 7518=f_a(2500) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

    5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

The encrypted numbers and the original numbers are displayed in the following table.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Andy}&\text{ }&\text{7,518}&\text{ }&\text{698}   \end{bmatrix}

Of course, the above table is kept secret from Becky. However, the encrypted numbers (just the encrypted numbers) are sent to Becky for random selection.

Becky selects one of the encrypted numbers for herself (perhaps thru a coin toss). Then the other encrypted number is the choice for Andy. Suppose Becky selects 7518. Becky then encrypted the number 7518 using her key.

    7518^{71} \equiv 1341=f_b(7518) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

Becky passes the encrypted number 1341 (her selection) and 698 (Andy’s selection) back to Andy. The following table lists out the numbers received by Andy.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341}   \end{bmatrix}

Andy decrypts his number 698 and gets back 2500, which is tail. He also decrypts 1341 and obtains 223, which he passes back to Becky.

    698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)

    1341^{52899} \equiv 223=g_a(1341) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)

The following summarizes the results up to this point.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \end{bmatrix}

Once Becky gets the decrypted number 223 from Andy, she decrypts it using her own key to obtain 2500, which is a head.

    223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)

The following table summarizes the results of the coin toss.

    \displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341}  \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{2,500} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Results of Coin Toss}&\text{ }&\text{5,000}&\text{ }&\text{2,500} \end{bmatrix}

___________________________________________________________________________________________________________________

Numerical Calculation

We now show some of the calculations involved in the above encryption and decryption. We show three calculations.

    5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919)  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

    698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)

    223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)

Even with the small prime number p=7919, the calculation is not done directly. For example, unless special software is used, f_a(5000) is not found by calculating 5000^{47} and then finding the remainder upon division by 7919. The following demonstrates a “divide and conquer” approach for the calculation for (2) where in each step the exponent is reduced by half.

    \displaystyle \begin{aligned} 5000^{47}&\equiv (5000^2)^{23} \cdot 5000 \ (\text{mod} \ 7919) \\&\text{ } \\&=7636^{23} \cdot 5000 \equiv (7636^2)^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 2501 \equiv (899^2)^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 7322 \equiv (463^2)^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 754 \\&\text{ } \\&\equiv 295 \cdot 754  \\&\text{ } \\&\equiv 698 \ (\text{mod} \ 7919) \end{aligned}

In each step in the above calculation, we use the division algorithm to obtain the remainder. For example, to go from the first line to the second line, divide 5000^2 by 7919 to obtain the remainder of 7636. The number 698 in the last step is the remainder when 295 \cdot 754 is divided by 7919. These calculations are tedious if done by hand and should be done by computer.

The calculation for (4) is that 698^{52899} \equiv 5000 \ (\text{mod} \ 7919). In other word, decrypting the encrypted number of 698 recovers the original number of 5000. This calculation can be shortened by using Fermat’s Little Theorem, which implies that 698^{7919-1} \equiv 1 \ (\text{mod} \ 7919). Thus we have:

    698^{47508} \equiv 698^{6 \cdot 7918} \equiv 1 \ (\text{mod} \ 7919)

So we can reduce 47508 from the exponent 52899, leaving the exponent 5391. We have:

    698^{52899} \equiv 698^{47508} \cdot 698^{5391} \equiv 1 \cdot 698^{5391} \ (\text{mod} \ 7919)

The following uses the “divide and conquer” approach to compute 698^{5391} modulo 7919.

    \displaystyle \begin{aligned} 698^{5391}&\equiv (698^2)^{2695} \cdot 698 \ (\text{mod} \ 7919) \\&\text{ } \\&=4145^{2695} \cdot 698 \equiv (4145^2)^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 2775 \equiv (4714^2)^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 7081 \equiv (1082^2)^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 3969 \equiv (6631^2)^{168} \cdot 3969 \\&\text{ } \\&\equiv 3873^{168} \cdot 3969 \equiv (3873^2)^{84} \cdot 3969 \\&\text{ } \\&\equiv 1543^{84} \cdot 3969 \equiv (1543^2)^{42} \cdot 3969 \\&\text{ } \\&\equiv 5149^{42} \cdot 3969 \equiv (5149^2)^{21} \cdot 3969\\&\text{ } \\&\equiv 7308^{21} \cdot 3969 \equiv (7308^2)^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 6074 \equiv (1128^2)^{5} \cdot 6074\\&\text{ } \\&\equiv 5344^5 \cdot 6074 \equiv (5344^2)^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv 2422^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv2422^2 \cdot 7394 \\&\text{ } \\&\equiv 6024 \cdot 7394    \\&\text{ } \\&\equiv 5000 \ (\text{mod} \ 7919) \end{aligned}

The calculation for (6) is 223^{26319} \equiv 2500 \ (\text{mod} \ 7919). We can also get an assist from the Fermat’s Little Theorem. In this particular case, 223^{7918} \equiv 1 \ (\text{mod} \ 7919). With 26319=3 \cdot 7918+2565, we only need to calculate 223^{2565} \ (\text{mod} \ 7919), which is done below.

    \displaystyle \begin{aligned} 223^{2565}&\equiv (223^2)^{1282} \cdot 223 \ (\text{mod} \ 7919) \\&\text{ } \\&=2215^{1282} \cdot 223 \equiv (2215^2)^{641} \cdot 223 \\&\text{ } \\&\equiv 4364^{641} \cdot 223 \equiv (4364^2)^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 7054 \equiv (7220^2)^{160} \cdot 7054 \\&\text{ } \\&\equiv 5542^{160} \cdot 7054 \equiv (5442^2)^{80} \cdot 7054 \\&\text{ } \\&\equiv 3882^{80} \cdot 7054 \equiv (3882^2)^{40} \cdot 7054 \\&\text{ } \\&\equiv 67^{40} \cdot 7054 \equiv (67^2)^{20} \cdot 7054 \\&\text{ } \\&\equiv 4489^{20} \cdot 7054 \equiv (4489^2)^{10} \cdot 7054\\&\text{ } \\&\equiv 5185^{10} \cdot 7054 \equiv (5185^2)^{5} \cdot 7054  \\&\text{ } \\&\equiv 7139^{5} \cdot 7054 \equiv (7139^2)^{2} \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 1585  \\&\text{ } \\&\equiv 4723 \cdot 1585    \\&\text{ } \\&\equiv 2500 \ (\text{mod} \ 7919) \end{aligned}

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Fermat’s Little Theorem and Mental Poker

In this post we demonstrate another use of the Fermat’s Little Theorem.

How can two people play poker when they are not sitting face to face from each other? If the game of poker is played over long distance (e.g. via a telephone line or some electronic communication channel), there will be a need to ensure a fair game. For example, the two players must use the same deck of cards (ensuring that there will be no duplicates). The deck of cards will need to be well shuffled. Each player cannot see the cards of the other player. One solution is to use a trusted third party to do the shuffling and selecting of cards. If a third party cannot be found or it is felt that the third party cannot be trusted to be fair, then one should consider the cryptographic solution described in this post. This soultion was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm).

The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).

___________________________________________________________________________________________________________________

Setting Up the Deck of Cards

Let’s say that the players are Andy and Becky. Since they are not using a physical deck of cards, they need to represent the cards by numbers. Let’s say that they agree to number the cards as follows:

    \displaystyle \heartsuit 2=1020 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 2=2020  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 2=3020 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 2=4020

    \displaystyle \heartsuit 3=1030 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 3=2030  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 3=3030 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 3=4030

    \displaystyle \heartsuit 4=1040 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 4=2040  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 4=3040 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 4=4040

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

    \displaystyle \heartsuit Q=1120 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit Q=2120  \ \ \ \ \ \ \ \ \ \ \spadesuit Q=3120 \ \ \ \ \ \ \ \ \clubsuit Q=4120

    \displaystyle \heartsuit K=1130 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit K=2130  \ \ \ \ \ \ \ \ \ \spadesuit K=3130 \ \ \ \ \ \ \ \ \clubsuit K=4130

    \displaystyle \heartsuit A=1140 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit A=2140  \ \ \ \ \ \ \ \ \ \ \spadesuit A=3140 \ \ \ \ \ \ \ \ \ \clubsuit A=4140

___________________________________________________________________________________________________________________

Setting Up the Pad Locks

The card numbers need to be encrypted before they can be passed between the two players. Here’s how it works.

Both players agree to choose a large prime number p. This number p needs to be larger than all the card numbers and the encrypted card numbers. The larger p is, the harder it will be for any one of the players to cheat.

Now each of the players needs to choose an encryption-decryption key (a padlock) that the player keeps secret. Let’s start with Andy. He chooses a pair of positive numbers a_0 and a_1 such that the following holds:

    a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1)

Equivalently the pair a_0 and a_1 satisfies the equation a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. The number a_0 will be used for locking (encryption) and the number a_1 will be used for unlocking (decryption). Andy will also keep this pair of numbers away from Becky.

How will Andy use this padlock? Suppose that m is a number to be encrypted. To encrypt the number, Andy raises m to the power of a_0 and then finds the remainder upon division by p. He will call the remainder f_a(m). Using congruence notation, the following is the encryption function:

    f_a(m) \equiv m^{a_0} \ (\text{mod} \ p)

If Andy needs to recover m from the encrypted card number c=f_a(m), all he has to do is to raise c to the power of a_1 and then find the remainder upon division by p. Call the remainder g_a(c), which will be the original card number m. Using congruence notation, the following is the decryption function:

    g_a(c) \equiv c^{a_1} \ (\text{mod} \ p)

The decrypted number is the original number. Thus we have g_a(c)=m. A proof of this relies on the Fermat’s Little Theorem (see proof).

Because the numbers involved are usually large, no one will try to raise m to the power of a_0 and then divides by p to find the remainder. Instead, Andy should use special software. If software is not available, Andy can rely on congruence modulo arithmetic, which should also be done by a computer. See below for a demonstration of the congruence modulo arithmetic.

The other player Becky also needs a padlock. Specifically, she chooses a pair of numbers b_0 and b_1 that satisfy the following:

    b_0 \cdot b_1 \equiv 1 \ (\text{mod} \ p-1)

This pair of number serves the same purpose as the pair that belongs to Andy. Of course, b_0 and b_1 need to be kept secret from Andy. The following shows the encryption and decryption functions for Becky’s padlock.

    f_b(m) \equiv m^{b_0} \ (\text{mod} \ p)

    g_b(c) \equiv c^{b_1} \ (\text{mod} \ p)

___________________________________________________________________________________________________________________

How to Play the Game

Suppose the card numbers are m_1, m_2, m_3, \cdots, m_{52} (the above is one example of card number assigment). Andy then encrypts the card number using his encryption function f_a(m). The following lists the encrypted card numbers.

    \displaystyle f_a(m_1),\ f_a(m_2), \ f_a(m_3),\cdots,f_a(m_{52})

Andy then passes these encrypted card numbers to Becky. She shuffles the encrypted deck thorughly. She then chooses a 5-card hand for Andy. Becky then chooses another 5-card hand for herself. Becky uses her key to encrypt her 5-card hand. Becky passes both 5-card hands to Andy. The following shows what Becky passes to Andy.

    Andy’s 5-card hand: f_a(m_i) \equiv m_i^{a_0} \ (\text{mod} \ p) for 5 distinct values of i.

    Becky’s 5-card hand: f_b(f_a(m_j)) \equiv f_a(m_j)^{b_0} \ (\text{mod} \ p) for 5 distinct values of j.

Once Andy gets the two 5-card hands, he decrypts his own 5-card hand and gets back the original card numbers. He also decrypts Becky’s 5-card hand and passes that back to Becky.

    Andy’s 5-card hand: g_a(f_a(m_i)) \equiv (m_i^{a_0})^{a_1} \equiv m_i \ (\text{mod} \ p)

    Becky’s 5-card hand: g_a(f_b(f_a(m_j))) \equiv (f_a(m_j)^{b_0})^{a_1}=(f_a(m_j)^{a_1})^{b_0} \equiv m_j^{b_0} \ (\text{mod} \ p), which Andy passes back to Becky.

Once Becky’s recieves her 5-card hand back from Andy, she decrypts the cards immediately and gets back the original card numbers.

    Becky’s 5-card hand: g_b(m_j^{b_0}) \equiv (m_j^{b_0})^{b_1} \equiv m_j \ (\text{mod} \ p)

Now each of the players has a 5-card hand that is only known to himself or herself. If they need to select new cards from the deck, they can follow the same back-and-forth procedures of encrypting and decrypting.

How fair is the poker game played in this manner? How secure is the game? It is very fair and secure if the players follow the rules and do not cheat. It is obviously possible to cheat. When Andy passes the 52 encrypted card numbers to Becky, Becky certainly can try to break Andy’s lock by figuring out Andy’s a_0. When Becky passes her encrypted cards to Andy, he can try to figure out Becky’s b_0. For that to happen, the player who wants to cheat will need to have enormous amount of computational resources at the ready. Thus the prime number p should be large enough to make cheating an intractable problem. On the other hand, even when the prime number is of a moderate size, there has to be a fair amount of computational resources in order to play the game efficiently, with all the encrypting and decrypting that have to be done.


___________________________________________________________________________________________________________________

Fermat’s Little Theorem

We now use Fermat’s Little Theorem to show that the encryption-decryption key works correctly and accurately. We show the following:

    (m^{a_0})^{a_1} \equiv m \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

For the descriptions of the numbers m, p, a_0 and a_1, see the above section Setting Up the Padlocks. First we state the Fermat’s Little Theorem.

Fermat’s Little Theorem
Let q be a prime number. Then for any integer a, a^q-a is an integer multiple of q (or q divides a^q-a). Using congruence notation, the theorem can be expressed as:

    a^q \equiv a \ (\text{mod} \ q)

If the integer a is not divisible by q, then we can divide out a and the theorem can be expressed as:

    a^{q-1} \equiv 1 \ (\text{mod} \ q)

For a proof and a fuller discussion of Fermat’s little theorem, see this post.

We now prove the property (1). Recall that the pair of positive integers a_0 and a_1 are keys to lock and unlock a number m. They are chosen such that a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1), or equivalently a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. This integer k must be positive since a_0 and a_1 are both positive.

In the derivation below, we repeated use the fact that m^p \equiv m \ (\text{mod} \ p) (applying the Fermat’s Little Theorem).

    \displaystyle \begin{aligned} m&\equiv m^p \ (\text{mod} \ p)=m \cdot m^{p-1} \\&\equiv m^p \cdot m^{p-1} \ (\text{mod} \ p)=m \cdot m^{2(p-1)} \\&\equiv m^p \cdot m^{2(p-1)} \ (\text{mod} \ p)=m \cdot m^{3(p-1)} \\&\cdots \\&\cdots \\&\cdots \\&\equiv m^p \cdot m^{(k-1)(p-1)} \ (\text{mod} \ p)=m \cdot m^{k(p-1)} \\&=m \cdot m^{k(p-1)} \equiv m^{a_0 \cdot a_1} \ (\text{mod} \ p) \end{aligned}


___________________________________________________________________________________________________________________

Example of Congruence Calculation

For a numerical example, we use a small prime number p=55,049. Though a small prime number, it is large enough to make the illustration meaningful. Andy chooses a_0 \cdot a_1 such that a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. Andy decides to use k=3817, leading to a_0=2,657 and a_1=79,081.

As illustration of how the calculation is done, let m=1020 (the number for \heartsuit 2 as indicated above).

To decrypt this card, Andy needs to raise 1020 to the 2657th power and then find the remainder upon division by p=50,049. This is the definition for 1010200^{269} modulo p. But the calculation is not easy to do directly without special software. We present here a “divide and conquer” approach that use the division algorithm in each step to reduce the exponent by half.

To start, note that 1020^2 \equiv 49518 \ (\text{mod} \ 55049), meaning that the remainder is 49518 when 1020^2 is divided by 55049. In the following series of steps, a congruence calculation is performed in each step (using the division algorithm) to reduce the exponent by half.

    \displaystyle \begin{aligned} 1020^{2657}&\equiv (1020^2)^{1328} \cdot 1020 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 49518^{1328} \cdot 1020 \equiv (49518^2)^{664} \cdot 1020  \\&\text{ } \\& \equiv 39766^{664} \cdot 1020 \equiv (39766^2)^{332} \cdot 1020 \\&\text{ } \\& \equiv 52231^{332} \cdot 1020 \equiv (52231^2)^{166} \cdot 1020 \\&\text{ } \\&\equiv 14068^{166} \cdot 1020 \equiv (14068^2)^{83} \cdot 1020 \\&\text{ } \\& \equiv 7469^{83} \cdot 1020 \equiv (7469^2)^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\& \equiv 21324^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\&\equiv 21324^{41} \cdot 21618 \equiv (21324^2)^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\&  \equiv 8236^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\& \equiv 8236^{20} \cdot 1906 \equiv (8236^2)^{10} \cdot 1906 \\&\text{ } \\& \equiv 11328^{10} \cdot 1906 \equiv (11328^2)^{5} \cdot 1906 \\&\text{ } \\& \equiv 4365^5 \cdot 1906 \equiv (4365^2)^2 \cdot 4365 \cdot 1906 \\&\text{ } \\& \equiv 6271^2 \cdot 4365 \cdot 1906 \\&\text{ } \\&\equiv 6271^2 \cdot 7291  \\&\text{ } \\&\equiv 20455 \cdot 7291 \\&\text{ } \\&\equiv 9664 \ (\text{mod} \ 55049)  \end{aligned}

Thus the card number 1020 is encrypted as 9664. To recover the original card number from this encrypted number, Andy needs to raise 9664 to the power of a_1=79081. Here, we get an assist from Fermat’s Little Theorem in addition to the ‘divide and conquer” congruence arithmetic that is used above.

According to Fermat’s Little Theorem, 9664^{55048} \equiv 1 \ (\text{mod} \ 55049). Thus we have

    9664^{79081} \equiv 9664^{55048} \cdot 9664^{24033} \equiv 9664^{24033} \ (\text{mod} \ 55049)

With the help of Fermat’s Little Theorem, the exponent 79081 has come down to 24033. In the rest of the way, the “divide and conquer” approach is used.

    \displaystyle \begin{aligned} 9664^{24033}&\equiv (9664^2)^{12016} \cdot 9664 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 29782^{12016} \cdot 9664 \equiv (29782^2)^{6008} \cdot 9664 \\&\text{ } \\&\equiv 8237^{6008} \cdot 9664 \equiv (8237^2)^{3004} \cdot 9664 \\&\text{ } \\&\equiv 27801^{3004} \cdot 9664 \equiv (27801^2)^{1502} \cdot 9664 \\&\text{ } \\&\equiv 7641^{1502} \cdot 9664 \equiv (7641^2)^{751} \cdot 9664 \\&\text{ } \\&\equiv  32941^{751} \cdot 9664 \equiv (32941^2)^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 48506 \equiv (38642^2)^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 5451 \equiv (39^2)^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 47442 \equiv (1521^2)^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv 1383^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv  1383^{46} \cdot 45092 \equiv (1383^2)^{23} \cdot 45092 \\&\text{ } \\&\equiv 41023^{23} \cdot 45092 \equiv (41023^2)^{11} \cdot 41023 \cdot 45092 \\&\text{ } \\&\equiv 38599^{11} \cdot 41023 \cdot 45092  \\&\text{ } \\&\equiv 38599^{11} \cdot 52618 \equiv (38599^2)^{5} \cdot 38599 \cdot 52618 \\&\text{ } \\&\equiv 36665^5 \cdot 38599 \cdot 52618  \\&\text{ } \\&\equiv 36665^5 \cdot 24376 \equiv (36665^2)^{2} \cdot 36665 \cdot 24376  \\&\text{ } \\&\equiv 25645^2 \cdot 36665 \cdot 24376  \\&\text{ } \\&\equiv 25645^2 \cdot 25525  \\&\text{ } \\&\equiv 50671 \cdot 25525  \\&\text{ } \\&\equiv 1020 \ (\text{mod} \ 55049)  \end{aligned}

In each step of the above calculation, the division algorithm is applied to reduce the exponent by half. For example, to go from the first line to the second line, 9664^2 is divided by 55049 to obtain the remainder 29782, i.e. 9664^2 \equiv 29782 \ (\text{mod} \ 55049). The number 1020 in the last line is the remainder when 50671 \cdot 25525 is divided by 55049.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}