Speeding up modular exponentiation using CRT

This is the fifth post in a series of posts on the Chinese remainder theorem (CRT). When solving a congruence equation with a composite modulus, it is often easier to convert the problem to one of solving several congruence equations with smaller moduli that are primes or powers of primes. Then combine the individual solutions using the Chinese remainder theorem. In this post, we demonstrate this process for modular exponentiation x \equiv c^d \ (\text{mod} \ m) where the exponent d and the modulus m are large. Given x \equiv c^d \ (\text{mod} \ m), the algorithm discussed here is to produce a system of equations with smaller moduli and exponents that give the same answer as for the original problem.

The previous posts in the series on CRT: first post; second post; third post; fourth post

____________________________________________________________________________

Preliminary discussion

The exponentiation c^d is usually programmed using the fast powering algorithm. The CRT method will convert the exponentiation c^d to several exponentiations that involve much smaller exponents and moduli, thus greatly reducing the calculation time, in particular speeding up the fast powering algorithm. One application of the CRT method is to improve the run time of the decryption process in the RSA algorithm (up to four times faster).

As already mentioned, the goal of the algorithm discussed here is to produce an equivalent system of linear congruence equations. Once this system is produced, the Chinese remainder theorem only guarantees a solution and does not actually produce a solution. So we need to know how to Chinese remainder, i.e. using an algorithm for solving a simultaneous linear congruences. We can use the one discussed here (the first method) or here (the second method). The following examples are worked using the second method.

The CRT algorithm discussed here makes use of Euler’s theorem, which states that a^{\phi(m)} \equiv 1 \ (\text{mod} \ m) whenever a and the modulus m are relatively prime where \phi(m) is the phi function evaluated at m. For this reason, the algorithm requires the evaluation of the phi function.

When calculating c^d \ (\text{mod} \ m), the use of the phi function \phi(m) is to reduce the exponent d by the largest multiple of \phi(m). For example, since \phi(17)=16 and 2^{16} \equiv 1 \ (\text{mod} \ 17), the problem of 2^{250} \ (\text{mod} \ 17) is converted to finding 2^{10} \ (\text{mod} \ 17). Here, the original exponent of 250 is reduced to 10 after taking out the largest multiple of 16. Note that 10 \equiv 250 \ (\text{mod} \ \phi(17)=16). In general, we want to replace the original exponent d by a smaller exponent d_1 where d_1 \equiv d \ (\text{mod} \ \phi(m)).

____________________________________________________________________________

Examples

In the following three examples, we use the algorithm discussed here to solve systems of linear congruence equations (this is the iterative approach). These examples are by no means realistic since the numbers used are small. So they are for demonstration of how CRT works.

Example 1
Calculate x \equiv 2^{3163} \ (\text{mod} \ 3969).

First, factor the modulus 3969=3^4 \times 7^2=81 \times 49. Now the problem is converted to solving the following system of two equations:

    x \equiv 2^{3163} \ (\text{mod} \ 81)

    x \equiv 2^{3163} \ (\text{mod} \ 49)

By CRT, any solution to the two equations is also a solution to the original equation. However, the exponent of 3163 should first be reduced. To this end, calculate the phi function, where \phi(3^4)=3^2 \cdot (3-1)=54 and \phi(7^2)=7 \cdot (7-1)=42. We should reduce from 3163 the largest multiple of 54 in the first equation and reduce the largest multiple of 42 in the second equation. In other words, reduce the exponent 3163 modulo the two phi function values:

    3163 \equiv 31 \ (\text{mod} \ 54)

    3163 \equiv 13 \ (\text{mod} \ 42)

As a result, we solve the following two equations:

    x \equiv 2^{3163} \equiv 2^{31} \equiv 65 \ (\text{mod} \ 81)

    x \equiv 2^{3163} \equiv 2^{13} \equiv 9 \ (\text{mod} \ 49)

Note that the original exponentiation 2^{3163} is turned into the easier ones of 2^{31} and 2^{13}. The following gives the solution to the above two equations.

    \displaystyle \begin{aligned} x_0&=65+81 \cdot 23 \cdot (9-65) \ (\text{mod} \ 3969)  \\&\equiv -104263 \ (\text{mod} \ 3969) \\&\equiv 2900 \ (\text{mod} \ 3969) \end{aligned}

    where 23 is obtained by solving for y in 81y \equiv 1 \ (\text{mod} \ 49)

By CRT, the answer to the original problem is 2^{3163} \equiv 2900 \ (\text{mod} \ 3969). \square

Example 2
Calculate x \equiv 3^{3163} \ (\text{mod} \ 3969).

In this example, the number 3 and the modulus 3969 are not relatively prime. The CRT method still applies. As in Example 1, the problem can be reduced in the following way:

    x \equiv 3^{3163} \equiv 3^{31} \equiv 0 \ (\text{mod} \ 81)

    x \equiv 2^{3163} \equiv 3^{13} \equiv 10 \ (\text{mod} \ 49)

The first equation is congruent to 0 since 3^{31} contains 81 as a factor. The following gives the solution to the above two equations:

    \displaystyle \begin{aligned} x_0&=0+81 \cdot 23 \cdot (10-0) \ (\text{mod} \ 3969)  \\&\equiv 18630 \ (\text{mod} \ 3969) \\&\equiv 2754 \ (\text{mod} \ 3969) \end{aligned}

By CRT, the answer to the original problem is 3^{3163} \equiv 2754 \ (\text{mod} \ 3969). \square

Example 3
The above 2 examples use small numbers to illustrate the CRT technique. In this example, we use slightly larger numbers. Calculate x \equiv 355^{d} \ (\text{mod} \ m) where d=\text{1,759,695,794} and m=\text{3,055,933,789}=1277 \cdot 1439 \cdot 1663.

As in the other examples, we break up the problem in three congruences. The three factors of the modulus are prime numbers. Thus we reduce the exponent d by multiples of a prime factor less one.

    \text{1,759,695,794} \equiv 1198 \ (\text{mod} \ 1276)

    \text{1,759,695,794} \equiv 814 \ (\text{mod} \ 1438)

    \text{1,759,695,794} \equiv 110 \ (\text{mod} \ 1662)

Then the original problem is transformed to solving the following three equations.

    x \equiv 355^{d} \equiv 355^{1198} \equiv 189 \ (\text{mod} \ 1277)

    x \equiv 355^{d} \equiv 355^{814} \equiv 1010 \ (\text{mod} \ 1439)

    x \equiv 355^{d} \equiv 355^{110} \equiv 315 \ (\text{mod} \ 1663)

Notice that the original exponentiation is transformed to the smaller ones of 355^{1198}, 355^{814} and 355^{315}. The remaining task is to solve the system of three equations. One way to find to solution to the above three equations is to use the iterative approach, starting with the solution x_1=189 to the first equation. Then find the solution x_2 to the first two equations and then the solution x_3 to all three equations.

    \displaystyle \begin{aligned} x_2&=189+1277 \cdot 151 \cdot (1010-189) \ (\text{mod} \ 1277 \cdot 1439)  \\&\equiv 158311156 \ (\text{mod} \ 1837603) \\&\equiv 277298 \ (\text{mod} \ 1837603) \end{aligned}

    where 151 is obtained by solving for y in 1277y \equiv 1 \ (\text{mod} \ 1439)

    \displaystyle \begin{aligned} x_3&=277298+(1277 \cdot 1439) \cdot 970 \cdot (315-277298) \ (\text{mod} \ 1277 \cdot 1439 \cdot 1663)  \\&\equiv 277298+1782474910 \cdot (-276983) \ (\text{mod} \ m) \\&\equiv 277298+1414954310 \ (\text{mod} \ m) \\&\equiv 1415231608 \ (\text{mod} \ m) \end{aligned}

    where 970 is obtained by solving for y in (1277 \cdot 1439) y \equiv 1 \ (\text{mod} \ 1663)

By CRT, the answer to the original problem is 355^{d} \equiv 1415231608 \ (\text{mod} \ m). \square

____________________________________________________________________________

The CRT algorithm to speed exponentiation

Suppose we wish to evaluate x \equiv c^{d} \ (\text{mod} \ m) where the prime factorization of m is m=p_1^{n_1} \cdot p_2^{n_2} \cdots p_t^{n_t}. The numbers p_i are distinct prime numbers and each exponent n_i \ge 1. To prepare for the calculation, do the following:

    Let m_i=p_i^{n_i} for each i.

    Calculate \phi(m_i) for each i.

Case 1. The base c and the modulus m are relatively prime.
Then the answer to the original exponentiation problem is identical to the solution to the following system of t congruence equations:

    x \equiv c^{d_1} \ (\text{mod} \ m_1)

    x \equiv c^{d_2} \ (\text{mod} \ m_2)

    \cdots

    x \equiv c^{d_t} \ (\text{mod} \ m_t)

where d_i \equiv d \ (\text{mod} \ \phi(m_i)) for each i. If possible, each c^{d_i} should be reduced modulo m_i.

Case 2. The base c and the modulus m are not relatively prime.
In this case, c and m have prime factors in common (at least one p_i). The idea here is that for any p_i that is a prime factor of c, the equation x \equiv c^{d_i} \ (\text{mod} \ m_i) in Case 1 is replaced by x \equiv 0 \ (\text{mod} \ m_i). Then solve the resulting system of equations (see Example 2). Essentially, Case 2 can fall under Case 1 with c^{d_i} being congruent to zero. We call out Case 2 for the sake of clarity.

The original exponentiation c^d boils down to solving an appropriate system of CRT congruences as described above. Once the equivalent system of congruences is set up, use the algorithm discussed here or here to do Chinese remaindering.

Comment
Both Case 1 and Case 2 produce a system of linear congruence equations that have identical solution to the original equation. This is a result of using CRT (see Theorem D and Theorem G here). The savings in the calculation come in the form of the smaller exponentiations in the resulting congruence equations.

In Case 2, some of the congruence equations are x \equiv 0. This is because the base c and some moduli m_i are not relatively prime. For these moduli, c^{d_i} would contain p_i^{n_i} as a factor (assuming that d_i \ge n_i). Hence, x \equiv c^{d_i} \equiv 0 \ (\text{mod} \ m_i).

The two-equation case
When the modulus is the product of two factors that are relatively prime, the CRT algorithm involves only two equations. We write out the solution explicitly for this case. To evaluate x \equiv c^{d} \ (\text{mod} \ m) where m=m_1 \cdot m_2 and m_1 and m_2 are relatively prime, solve the following system of two equations,

    x \equiv c^{d_1} \ (\text{mod} \ m_1)

    x \equiv c^{d_2} \ (\text{mod} \ m_2)

The solution is x \equiv  c^{d_1}+m_1 \cdot v_1 \cdot (c^{d_2}-c^{d_1}) \ (\text{mod} \ m) where v_1 is the multiplicative inverse of m_1 modulo m_2. If possible, each c^{d_i} should be reduced modulo m_i.

____________________________________________________________________________

RSA application

The algorithm to speed the exponentiation is possible because the factorization of the modulus m is known (as a result, the values of \phi(m_i) are known). Knowing the values of \phi(m_i) makes it possible to reduce the large exponent d. For this reason, the decryption process in the RSA algorithm is a perfect place to apply the CRT technique described here.

With the RSA cryptosystem, a public key consists of N and e, where N is a large modulus that is a product of two large primes p and q (the two primes are not published) and e is the encryption exponent. Say Bob is the originator of the RSA public key. Bob also generates a private key, which is a number d that is used for decrypting any messages that he receives. The number d must be kept private. The prime factors p and q must also be kept secret since knowing p and q can derive d.

Suppose that Alice has a message to send to Bob. She can do so using the published key of N and e through the exponentiation c \equiv m^e \ (\text{mod} \ N). Here, m is the plaintext (the message to be sent) and c is the ciphertext (the encrypted message). Upon receiving the ciphertext c, Bob can then decrypt through the exponentiation m \equiv c^d \ (\text{mod} \ N) where d is the decryption exponent. In realistic RSA calculation, the public modulus N and the private decryption exponent d are large integers (N is at minimum a 2048-bit number). With CRT, the decryption can be reduced to two much smaller exponentiations. The effect can be at least four times faster.

We illustrate this with an example. This is a toy example since the numbers used are small. It is only intended as an illustration.

Example 4
Suppose the public key consists of N=\text{17,086,049} and e=65537. Bob has the additional information of N=p \cdot q where p=3863 and q=4423, which are kept secret. Knowing p and q allows Bob to compute d=\text{5,731,241}. Suppose that Bob receives a message c= 4831984 from Alice. Use the CRT approach to find the plaintext m.

The exponentiation is m \equiv 4831984^{5731241} \ (\text{mod} \ N), which is equivalent to the following two equations by CRT:

    m \equiv 4831984^{5731241} \ (\text{mod} \ 3863)

    m \equiv 4831984^{5731241} \ (\text{mod} \ 4423)

which is further simplified to:

    m \equiv 4831984^{5731241} \equiv 4831984^{33} \equiv 3084 \ (\text{mod} \ 3863)

    m \equiv 4831984^{5731241} \equiv 4831984^{329} \equiv 1436 \ (\text{mod} \ 4423)

where 33 \equiv 5731241 \ (\text{mod} \ 3862) and 329 \equiv 5731241 \ (\text{mod} \ 4422). Then the following is the plaintext (the original message).

    \displaystyle \begin{aligned} m&=3084+3863 \cdot 1319 \cdot (1436-3084) \ (\text{mod} \ 3863 \cdot 4423)  \\&\equiv 3084+5095297 \cdot (-1648) \ (\text{mod} \ N) \\&\equiv 9289736 \ (\text{mod} \ N) \end{aligned}

    where 1319 is obtained by solving for y in 3683y \equiv 1 \ (\text{mod} \ 4423)

The answer is 4831984^{5731241} \equiv 9289736 \ (\text{mod} \ N). \square

____________________________________________________________________________

Closing comment

In conclusion, we state the explcit formula for providing the CRT answer to the RSA decryption.

    m \equiv  c^{d_p}+p \cdot p_{inv} \cdot (c^{d_q}-c^{d_p}) \ (\text{mod} \ p \cdot q) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where d_p \equiv d \ (\text{mod} \ p-1), d_q \equiv d \ (\text{mod} \ q-1) and p_{inv} is the multiplicative inverse of p modulo q.

The decryption formula of (1) represends tremendous saving in calculation (up to four times faster). It is possible only for the holder of the RSA private key. It requires knowledge of the decryption exponent d, which is calculated from the factors p and q of the modulus N.
____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Euler’s phi function is multiplicative

This post gives a proof that Euler’s phi function is multiplicative. The proof is a simpler and more elegant proof, as compared to the one presented here. The combinatorial argument is greatly simplified using the Chinese remainder theorem (abbreviated CRT).

The letter m is used below to denote the modulus in modular arithmetic. The phi function \phi(m) is defined to be the count of all the integers 0 \le a \le m-1 such that a and m are relatively prime. If m is prime, then \phi(m)=m-1 since all integers from 1 to m-1 have no factors in common with m (other than 1). If m=10, then \phi(10)=4 since 1, 3, 7, and 9 are the only numbers that are relatively prime to m=10.

To properly work with the phi function, conmsider the following setting. Given a modulus m, a set of interest is \mathbb{Z}_m=\left\{0,1,2,\cdots,m-1 \right\}. This is the set of all least resdues modulo m, i.e., every integer is congruent modulo m to exactly one element of \mathbb{Z}_m. Another set of interest is \mathbb{Z}_m^*, which is the set of all elements a in \mathbb{Z}_m such that a and m are relatively prime. In other words, \phi(m) is defined to be the cardinality of the set \mathbb{Z}_m^*.

The set \mathbb{Z}_m is called the ring of integers modulo m since it satisfies the definition of a ring with regard to addition and multiplication modulo m. The set \mathbb{Z}_m^* with the multiplication modulo m is a group, i.e. every element of \mathbb{Z}_m^* has a multiplicative inverse with respect to the binary operation of multiplication modulo m. The set \mathbb{Z}_m^* is called the multiplicative group of integers modulo m. The fact that \mathbb{Z}_m^* is a group is established by the following theorem, which is proved here.

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

  1. The numbers a and m are relatively prime, i.e. \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.

Another interesting fact to point out is that when m is a prime number, \mathbb{Z}_m is a field, i.e. it is a commutative ring in which every non-zero element has a multiplicative inverse. Another terminology that is used by some authors is that the elements in \mathbb{Z}_m that have multiplicative inverses are called units. Thus \mathbb{Z}_m^* is also called the group of units of the ring of integers modulo m. Our notation here is not standard. The usual notation for the ring \mathbb{Z}_m is \mathbb{Z}/m\mathbb{Z}. The usual notation for \mathbb{Z}_m^* is (\mathbb{Z}/m\mathbb{Z})^*.

The phi function is multiplicative in the following sense.

Theorem 2
Let m and n be positive integers such that they are relatively prime. Then \phi(m \times n)=\phi(m) \times \phi(n).

Theorem 2 is established by the following results.

Lemma 3
Let m and n be positive integers such that they are relatively prime. Then the set \mathbb{Z}_{mn} and the set \mathbb{Z}_m \times \mathbb{Z}_n have the same cardinality.

Proof
To prove that the two sets have the same cardinality, we define a bijection f: \mathbb{Z}_{mn} \rightarrow \mathbb{Z}_m \times \mathbb{Z}_n, i.e. f is a one-to-one function that maps \mathbb{Z}_{mn} onto the set \mathbb{Z}_m \times \mathbb{Z}_n. For each a \in \mathbb{Z}_{mn}=\left\{0,1,2,\cdots,m \cdot n-1 \right\}, define f(a)=(c, d) where c \in \mathbb{Z}_m with c \equiv a \ (\text{mod} \ m) and d \in \mathbb{Z}_n with d \equiv a \ (\text{mod} \ n).

To see that f is one-to-one, let f(a)=f(b). Then we have a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). By the Chinese remainder theorem, a \equiv b \ (\text{mod} \ mn). Since a,b \in \mathbb{Z}_{mn}, a=b.

To show that f maps \mathbb{Z}_{mn} onto the set \mathbb{Z}_m \times \mathbb{Z}_n, let (c,d) \in \mathbb{Z}_m \times \mathbb{Z}_n. Consider the equations x \equiv c \ (\text{mod} \ m) and x \equiv d \ (\text{mod} \ n). By CRT, these two equations have a simultaneous solution a that is unique modulo m \times n. This means that f(a)=(c, d). \square

Lemma 4
Let m and n be positive integers such that they are relatively prime. Then the set \mathbb{Z}_{mn}^* and the set \mathbb{Z}_m^* \times \mathbb{Z}_n^* have the same cardinality.

Proof
The same mapping f defined in the proof of Lemma 3 is used. We show that when f is restricted to the set \mathbb{Z}_{mn}^*, it is a bijection from \mathbb{Z}_{mn}^* onto the set \mathbb{Z}_m^* \times \mathbb{Z}_n^*. First, we show that for any a \in \mathbb{Z}_{mn}^*, f(a) is indeed in \mathbb{Z}_m^* \times \mathbb{Z}_n^*. To see this, note that a and m \times n are relatively prime. So it must be that a and m are relatively prime too and that a and n are relatively prime.

The function f is one-to-one as shown above. The remaining piece is that for each (c,d) \in \mathbb{Z}_m^* \times \mathbb{Z}_n^*, there is some a \in \mathbb{Z}_{mn}^* such that f(a)=(c,d). As in the proof of Lemma 3, there is some a \in \mathbb{Z}_{mn} such that f(a)=(c,d). Note that a and m are relatively prime and a and n are relatively prime. This means that a and m \times n are relatively prime (see Lemma 4 here). Thus the function f is a one-to-one from \mathbb{Z}_{mn}^* onto \mathbb{Z}_m^* \times \mathbb{Z}_n^*. \square

Proof of Theorem 2
Lemma 4 shows that the set \mathbb{Z}_{mn}^* and the set \mathbb{Z}_m^* \times \mathbb{Z}_n^* have the same cardinality. First, \phi(m \times n) is the cardinality of the set \mathbb{Z}_{mn}^*. Theorem 2 is established by noting that \phi(m) \times \phi(n) is the cardinality of \mathbb{Z}_m^* \times \mathbb{Z}_n^*. \square

____________________________________________________________________________

Evaluating the phi function

The combinatorial argument for \phi(m \times n)=\phi(m) \times \phi(n) is greatly simplified by using the Chinese remainder theorem. Compare the above proof with the lengthier proof in an earlier post (see Theorem 3 here). With the multiplicative property of the phi function, we can evaluate the phi function for any positive integer.

For any positive integer m, consider its unique prime factorization m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}. Then we have:

    \displaystyle \begin{aligned} \phi(m)&=\phi(p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}) \\&=\phi(p_1^{e_1}) \times \phi(p_2^{e_2}) \times \cdots \times \phi(p_t^{e_t}) \\&=p_1^{e_1-1} \cdot (p_1-1) \times p_2^{e_2-1} \cdot (p_2-1) \times \cdots \times p_t^{e_t-1} \cdot (p_t-1) \\&=p_1^{e_1} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times p_2^{e_2} \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times p_t^{e_t} \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t} \cdot \biggl(1-\frac{1}{p_1}\biggr) \times  \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times  \cdot \biggl(1-\frac{1}{p_t}\biggr) \\&=m \cdot \biggl(1-\frac{1}{p_1}\biggr) \times  \cdot \biggl(1-\frac{1}{p_2}\biggr) \times \cdots \times  \cdot \biggl(1-\frac{1}{p_t}\biggr)\end{aligned}

In the above evaluation, this fact is used. For any prime p, \phi(p^n)=p^{n-1} \times (p-1) (see see Theorem 2 here). We also use the extended version of Theorem 2: if m_1,m_2,\cdots,m_t are pairwise relatively prime, then

    \phi(m_1 \times m_2 \times \cdots \times m_t)=\phi(m_1) \times \phi(m_2) \times \cdots \times \phi(m_t).

The extended result is to extend the product to more than two numbers. It is derived by a simple inductive argument.

____________________________________________________________________________

A formula for the phi function

The above evaluation leads us to the following way to express the phi function. For m=p_1^{e_1} \cdot p_2^{e_2} \cdots p_t^{e_t}, we have the following:

    \displaystyle \phi(m)=m \ \prod \limits_{p \lvert m} \biggl( 1-\frac{1}{p} \biggr)

In the above product, the p ranges over all prime divisors of m. A quick example: for 33075=3^3 \cdot 5^2 \cdot 7^2,

    \displaystyle \begin{aligned}\phi(33075)&=33075 \times \biggl( 1-\frac{1}{3} \biggr) \times \biggl( 1-\frac{1}{5} \biggr) \times \biggl( 1-\frac{1}{7} \biggr) \\&=33075 \times \frac{2}{3} \times \frac{4}{5} \times \frac{6}{7} \\&=315 \times 2 \times 4 \times 6 \\&=15120 \end{aligned}

One comment. For the above formula to work, we only need to know the prime divisors of the number, not necessarily the powers of the primes. For example, for 33075, we only need to know that the prime divisors are 3, 5 and 7.

____________________________________________________________________________

\copyright \ 2015 \text{ by Dan Ma}

Proving Chinese Remainder Theorem

In this post, we consider systems of linear congruence equations with respect to pairwise relatively prime moduli. The theorem we prove here is known as the Chinese remainder theorem (see Theorem 1 below). It is useful in many contexts. For an example, see the blog post Introducing Carmichael numbers (used in proving the Korselt’s Criterion). Theorem 2 below is a useful corollary of the Chinese remainder theorem. For examples of applications, see Primitive roots of twice the powers of odd primes and The primitive root theorem (used in proving the primitive root theorem).

    Theorem 1 (Chinese Remainder Theorem)

      Let n_1,n_2,\cdots,n_k be positive integers that are pairwise relatively prime. Let a_1,a_2,\cdots,a_k be any integers. Then the following system of linear congruence equations

        x \equiv a_1 \ (\text{mod} \ n_1)

        x \equiv a_2 \ (\text{mod} \ n_2)

        x \equiv a_3 \ (\text{mod} \ n_3)

          \cdots
          \cdots
          \cdots

        x \equiv a_k \ (\text{mod} \ n_k)

      has a solution x=b.

      Furthermore, x=b_0 is another solution to the above system of equations if and only if b_0 \equiv b \ (\text{mod} \ n_1 n_2 \cdots n_k).

Proof of Theorem 1
Let n=n_1 n_2 \cdots n_k. For each i=1,\cdots,k, let \displaystyle t_i=\frac{n}{n_i}. Note that t_i is the product of all n_j where j \ne i. So t_i and n_i are relatively prime. Thus for each i, t_i has a multiplicative inverse modulo n_i. Let (t_i)^{-1} be the inverse of t_i. Now define g_i=t_i \cdot (t_i)^{-1} for each i.

It is clear that for each i, g_i \equiv 1 \ (\text{mod} \ n_i) for each i and g_i \equiv 0 \ (\text{mod} \ n_j) for all j \ne i. Now define b as the following:

    b=g_1 \cdot a_1+g_2 \cdot a_2+\cdots+g_k \cdot a_k

It follows that b \equiv a_i \ (\text{mod} \ n_i) for each i=1,\cdots,k. Thus x=b is a solution that we are looking for.

It remains to show that solutions to the above system of equations are unique modulo n. Suppose that b_0 \equiv b \ (\text{mod} \ n). This means that b_0=b+n_1 n_2 \cdots n_k \cdot y for some integer y. It follows from this equation that b_0 \equiv b \ (\text{mod} \ n_i) for each i. Thus b_0 \equiv a_i \ (\text{mod} \ n_i) for each i.

On the other hand, suppose that x=b_0 is another solution to the above system of equations. Then b_0 \equiv b \ (\text{mod} \ n_i) for each i. So n_i \ \lvert \ (b_0-b) for each i. We have the following equations

    b_0-b=n_1 \cdot c_1

    b_0-b=n_2 \cdot c_2

    b_0-b=n_3 \cdot c_3

      \cdots
      \cdots
      \cdots

    b_0-b=n_k \cdot c_k

for some integers c_1, c_2, \cdots, c_k. From these equations, it follows that b_0-b=n_1 n_2 \cdots n_k \cdot c for some integer c. This is due to the fact that the integers n_1,n_2,\cdots,n_k are relatively prime. For example, from the first two equations, n_2 \ \lvert \ n_1 \cdot c_1. Since n_1 and n_2 are relatively prime, n_2 \ \lvert \ c_1, we have b_0-b=n_1 \cdot n_2 \cdot c_{1,2} for some integer c_{1,2}. Then consider this new equation along with the third equation above, we have n_3 \ \lvert \ n_1 \cdot n_2 \cdot c_{1,2}. Because the integers n_j are pairwise relatively prime, n_3 \ \lvert \ c_{1,2}. So we can further factor c_{1,2} into n_3 \cdot c_{1,3} for some integer c_{1,3}. Continuing this process, we can obtain b_0-b=n_1 n_2 \cdots n_k \cdot c. It follows that b_0 \equiv b \ (\text{mod} \ n_1 n_2 \cdots n_k). \blacksquare

    Theorem 2 (Corollary of Chinese Remainder Theorem)

      Let n_1,n_2,\cdots,n_k be positive integers that are pairwise relatively prime. Then for any integers c and d, the following linear congruences hold

        c \equiv d \ (\text{mod} \ n_1)

        c \equiv d \ (\text{mod} \ n_2)

        c \equiv d \ (\text{mod} \ n_3)

          \cdots
          \cdots
          \cdots

        c \equiv d \ (\text{mod} \ n_k)

      if and only of c \equiv d \ (\text{mod} \ n_1 n_2 \cdots n_k).

Proof of Theorem 2
This is an easy consequence of Theorem 1. Let d=a_1=a_2=\cdots=a_k. Then x=d would be a solution to the resulting system of linear congruence equations in Theorem 1. Theorem 2 then follows from the fact that any other solution to the system is congruent to d modulo n_1 n_2 \cdots n_k. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Introducing Carmichael numbers

This is an introduction to Carmichael numbers. We first discuss Carmichael numbers in the context of Fermat primality test and then discuss several basic properties. We also prove Korselt’s criterion, which gives a useful characterization of Carmichael numbers.

___________________________________________________________________________________________________________________

Fermat Primality Test

Fermat’s little theorem states that if p is a prime number, then a^p \equiv a \ (\text{mod} \ p) for any integer a. Fermat primality test refers to the process of using Fermat little theorem to check the “prime vs. composite” status of an integer.

Suppose that we have a positive integer n such that the “prime vs. composite” status is not known. If we can find an integer a such that a^n \not \equiv a \ (\text{mod} \ n), then we know for certain that the modulus n is composite (or not prime). For example, let n = \text{8,134,619}. Note that 2^{8134619} \equiv 3024172 \ (\text{mod} \ 8134619). So we know right away that n = \text{8,134,619} is not prime, even though we do not know what its prime factors are just from applying this test.

Given a positive integer n, whenever a^n \not \equiv a \ (\text{mod} \ n), we say that a is a Fermat witness for (the compositeness of) the integer n. Thus 2 is a Fermat witness for n = \text{8,134,619}.

What if we try one value of a and find that a is not a witness for (the compositeness of) n? Then the test is inconclusive. The best we can say is that n is probably prime. It makes sense to try more values of a. If all the values of a we try are not witnesses for n (i.e. a^n \equiv a \ (\text{mod} \ n) for all the values of a we try), then it “seems likely” that n is prime. But if we actually declare that n is prime, the decision could be wrong!

Take n=\text{10,024,561}. For several randomly chosen values of a, we have the following calculations:

    \displaystyle 5055996^{10024561} \equiv 5055996 \ (\text{mod} \ 10024561)

    \displaystyle 4388786^{10024561} \equiv 4388786 \ (\text{mod} \ 10024561)

    \displaystyle 4589768^{10024561} \equiv 4589768 \ (\text{mod} \ 10024561)

    \displaystyle  146255^{10024561} \equiv 146255 \ (\text{mod} \ 10024561)

    \displaystyle 6047524^{10024561} \equiv 6047524 \ (\text{mod} \ 10024561)

The above calculations could certainly be taken as encouraging signs that n=\text{10,024,561} is prime. With more values of a, we also find that a^{10024561} \equiv a \ (\text{mod} \ 10024561). However, if we declare that n=\text{10,024,561} is prime, it turns out to be a wrong conclusion.

In reality, n=\text{10,024,561} is composite with \text{10,024,561}=71 \cdot 271 \cdot 521. Furthermore a^{10024561} \equiv a \ (\text{mod} \ 10024561) for any integer a. So there are no witnesses for n=\text{10,024,561}. Any composite positive integer that has no Fermat witnesses is called a Carmichael number, in honor of Robert Carmichael who in 1910 found the smallest such number, which is 561.

Fermat primality test is always correct if the conclusion is that the integer being tested is a composite number (assuming there is no computational error). If the test says the number is composite, then it must be a composite number. In other words, there are no false negatives in using Fermat primality test as described above.

On the other hand, there can be false positives as a result of using Fermat primality test. If the conclusion is that the integer being tested is a prime number, it is possible that the conclusion is wrong. For a wrong conclusion, it could be that there exists a witness for the number being tested and that we have missed it. Or it could be that the number being tested is a Carmichael number. Though Carmichael numbers are rare but there are infinitely many of them. So we cannot ignore them entirely. For these reasons, Fermat primality test as described above is often not used. Instead, other extensions of the Fermat primality test are used.

___________________________________________________________________________________________________________________

Carmichael Numbers

As indicated above, a Carmichael number is a positive composite integer that has no Fermat witnesses. Specifically, it is a positive composite integer that satisfies the conclusion of Fermat’s little theorem. In other words, a Carmichael number is a positive composite integer n such that a^n \equiv a \ (\text{mod} \ n) for any integer a.

Carmichael numbers are rare. A recent search found that there are \text{20,138,200} Carmichael numbers between 1 and 10^{21}, about one in 50 trillion numbers (documented in this Wikipedia entry on Carmichael numbers). However it was proven by Alford, Granville and Pomerance in 1994 that there are infinitely many Carmichael numbers (paper).

The smallest Carmichael number is 561=3 \cdot 11 \cdot 17. A small listing of Carmichael numbers can be found in this link, where the example of n=\text{10,024,561} is found.

Carmichael numbers must be odd integers. To see this, suppose n is a Carmichael number and is even. Let a=-1. By condition (1) of Theorem 1, we have (-1)^n=1 \equiv -1 \ (\text{mod} \ n). On the other hand, -1 \equiv n-1 \ (\text{mod} \ n). Thus n-1 \equiv 1 \ (\text{mod} \ n). Thus we have n \equiv 2 \ (\text{mod} \ n). It must be the case that n=2, contradicting the fact that n is a composite number. So any Carmichael must be odd.

The following theorem provides more insight about Carmichael numbers. A positive integer n is squarefree if its prime decomposition contains no repeated prime factors. In other words, the integer n is squarefree means that if \displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} is the prime factorization of n, then all exponents e_j=1.

    Theorem 1 (Korselt’s Criterion)

      Let n be a positive composite integer. Then the following conditions are equivalent.

      1. The condition a^n \equiv a \ (\text{mod} \ n) holds for any integer a.
      2. The condition a^{n-1} \equiv 1 \ (\text{mod} \ n) holds for any integer a that is relatively prime to n.
      3. The integer n is squarefree and p-1 \ \lvert \ (n-1) for any prime divisor p of n.

Proof of Theorem 1

1 \Longrightarrow 2
Suppose that a is relatively prime to the modulus n. Then let b be the multiplicative inverse of a modulo n, i.e., ab \equiv 1 \ (\text{mod} \ n). By (1), we have a^n \equiv a \ (\text{mod} \ n). Multiply both sides by the multiplicative inverse b, we have a^{n-1} \equiv 1 \ (\text{mod} \ n).

2 \Longrightarrow 3
Let \displaystyle n=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of n where p_i \ne p_j for i \ne j and each exponent e_j \ge 1. Since n must be odd, each p_j must be an odd prime.

We first show that each e_j=1, thus showing that n is squarefree. To this end, for each j, let a_j be a primitive root modulo p_j^{e_j} (see Theorem 4 in the post Primitive roots of powers of odd primes). Consider the following system of linear congruence equations:

    x \equiv a_1 \ (\text{mod} \ p_1^{e_1})

    x \equiv a_2 \ (\text{mod} \ p_2^{e_2})

      \cdots
      \cdots
      \cdots

    x \equiv a_t \ (\text{mod} \ p_t^{e_t})

Since the moduli p_j^{e_j} are pairwise relatively prime, this system must have a solution according to the Chinese Remainder Theorem (a proof is found here). Let a one such solution. For each j, since a_j is a primitive root modulo p_j^{e_j}, a_j is relatively prime to p_j^{e_j}. Since a \equiv a_j \ (\text{mod} \ p_j^{e_j}), a is relatively prime to p_j^{e_j} for each j. Consequently, a is relatively prime to n. By assumption (2), we have a^{n-1} \equiv 1 \ (\text{mod} \ n).

Now fix a j with 1 \le j \le t. We show that e_j=1. Since a^{n-1} \equiv 1 \ (\text{mod} \ n), a^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j}). Since a \equiv a_j \ (\text{mod} \ p_j^{e_j}), we have a_j^{n-1} \equiv 1 \ (\text{mod} \ p_j^{e_j}). Note that the order of a_j modulo p_j^{e_j} is \phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1). Thus we have p_j^{e_j-1}(p_j-1) \ \lvert \ (n-1). If e_j>1, then p_j \ \lvert \ (n-1), which would mean that p_j \ \lvert \ 1. So it must be the case that e_j=1. It then follows that (p_j-1) \ \lvert \ (n-1).

3 \Longrightarrow 1
Suppose that n=p_1 p_2 \cdots p_t is a product of distinct prime numbers such that for each j, (p_j-1) \ \lvert \ (n-1).

Let a be any integer. First we show that a^n \equiv a \ (\text{mod} \ p_j) for all j. It then follows that a^n \equiv a \ (\text{mod} \ n).

Now fix a j with 1 \le j \le t. First consider the case that a and p_j are relatively prime. According to Fermat’s little theorem, a^{p_j-1} \equiv 1 \ (\text{mod} \ p_j). Since (p_j-1) \ \lvert \ (n-1), a^{n-1} \equiv 1 \ (\text{mod} \ p_j). By the Chinese Remainder Theorem, it follows that a^{n-1} \equiv 1 \ (\text{mod} \ n) and a^n \equiv a \ (\text{mod} \ n). \blacksquare

Examples
With Korselt’s criterion, it is easy to verify Carmichael numbers as long as the numbers are factored. For example, the smallest Carmichael number is 561=3 \cdot 11 \cdot 17. The number is obviously squarefree. furthermore 560 is divisible by 2, 10 and 16.

The number \text{10,024,561}= 71 \cdot 271 \cdot 521 is discussed above. We can also verify that this is a Carmichael number: 70 \ \lvert \ \text{10,024,560}, 270 \ \lvert \ \text{10,024,560} and 520 \ \lvert \ \text{10,024,560}.

Here’s three more Carmichael numbers (found here):

    \text{23,382,529} = 97 \cdot 193 \cdot 1249

    \text{403,043,257} = 19 \cdot 37 \cdot 43 \cdot 67 \cdot 199

    \text{154,037,320,009} = 23 \cdot 173 \cdot 1327 \cdot 29173

We end the post by pointing out one more property of Carmichael numbers, that Carmichael numbers must have at least three distinct prime factors. To see this, suppose that n=p \cdot q is a Carmichael number with two distinct prime factors p and q. We can express n-1 as follows:

    n-1=pq-1=(p-1)q+q-1

Since n is Carmichael, p-1 \ \lvert \ (n-1). So n-1=(p-1)w for some integer w. Plugging this into the above equation, we see that p-1 \ \lvert \ (q-1). By symmetry, we can also show that q-1 \ \lvert \ (p-1). Thus p=q, a contradiction. So any Carmichael must have at least three prime factors.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

The primitive root theorem

The primitive root theorem identifies all the positive integers for which primitive roots exist. The list of such integers is a restrictive list. This post along with two previous posts give a complete proof of this theorem using only elementary number theory. We prove the following theorem.

    Main Theorem (The Primitive Root Theorem)

      There exists a primitive root modulo m if and only if m=2, m=4, m=p^t or m=2p^t where p is an odd prime number and t is a positive integer.

The theorem essentially gives a list of the moduli that have primitive roots. Any modulus outside this restrictive list does not have primitive roots. For example, any integer that is a product of two odd prime factors is not on this list and hence has no primitive roots. In the post Primitive roots of powers of odd primes, we show that the powers of an odd prime have primitive roots. In the post Primitive roots of twice the powers of odd primes, we show that the moduli that are twice the power of an odd prime have primitive roots. It is easy to verify that the moduli 2 and 4 have primitive roots. Thus the direction \Longleftarrow of the primitive root theorem has been established. In this post we prove the direction \Longrightarrow, showing that if there exists a primitive root modulo p, then p must be one of the moduli in the list stated in the theorem.

___________________________________________________________________________________________________________________

LCM

The proof below makes use of the notion of the least common multiple. Let a and b be positive integers. The least common multiple of a and b is denoted by \text{LCM}(a,b) and is defined as the least positive integer that is divisible by both a and b. For example, \text{LCM}(16,18)=144. We can also express \text{LCM}(a,b) as follows:

    \displaystyle \text{LCM}(a,b)=\frac{a \cdot b}{\text{GCD}(a,b)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

where \text{GCD}(a,b) is the greatest common divisor of a and b. The above formula reduces the calculation of LCM to that of calculating the GCD. To compute the LCM of two numbers, we can simply remove the common prime factors between the two numbers. When the number a and b are relatively prime, i.e., \text{GCD}(a,b)=1, we have \displaystyle \text{LCM}(a,b)=a \cdot b.

Another way to look at LCM is that it is the product of multiplying together the highest power of each prime number. For example, 48=2^4 \cdot 3 and 18=2 \cdot 3^2. Then \text{LCM}(16,18)=2^4 \cdot 3^2=144.

The least common divisor of the numbers a_1,a_2,\cdots,a_n is denoted by \text{LCM}(a_1,a_2,\cdots,a_n) and is defined similarly. It is the least positive integer that is divisible by all a_j. Since the product of all the numbers a_j is one integer that is divisible by each a_k, we have:

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le a_1 \cdot a_2 \cdots a_n  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)

As in the case of two numbers, the LCM of more than two numbers can be thought as the product of multiplying together the highest power of each prime number. For example, the LCM of 48=2^4 \cdot 3, 18=2 \cdot 3^2 and 45=3^2 \cdot 5 is 2^4 \cdot 3^2 \cdot 5=720.

For a special case, there is a simple expression of LCM.

    Lemma 1

      Let a_1,a_2,\cdots,a_n be positive integers.

      Then \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=a_1 \cdot a_2 \cdots a_n if and only if the numbers a_1,a_2,\cdots,a_n are pairwise relatively prime, i.e., a_i and a_j are relatively prime whenever i \ne j.

Proof of Lemma 1
\Longleftarrow
Suppose the numbers are pairwise relatively prime. Then there are no common prime factors in common between any two numbers on the list. Then multiplying together the highest power of each prime factor is the same as multiplying the individual numbers a_1,a_2 \cdots,a_n.

\Longrightarrow
Suppose a_i and a_j are not relatively prime for some i \ne j. As a result, d=\text{GCD}(a_i,a_j)>1. It follows that

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n) \le \frac{a_1 \cdot a_2 \cdots a_n}{d} < a_1 \cdot a_2,\cdots a_n \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)

To give a sense of why the above is true, let’s look at a simple case of d=\text{GCD}(a_i,a_j)=p^u where p is a prime number and u \ge 1. Assume that a_i=a_1, a_j=a_2 and p^u is part of the prime factorization of a_1. Furthermore, note that \displaystyle \text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) is identical to \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n). The following derivation confirms (3):

    \displaystyle \text{LCM}(a_1,a_2,\cdots,a_n)=\text{LCM}(\frac{a_1}{p^u},a_2,\cdots,a_n) \le \frac{a_1}{p^u} \cdot a_2 \cdots a_n < a_1 \cdot a_2,\cdots a_n

With the above clarification, the lemma is established. \blacksquare

___________________________________________________________________________________________________________________

Other Tools

We need to two more lemmas to help us prove the main theorem.

    Lemma 2

      Let m and n be positive integers that are relatively prime. Then a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n) if and only if a \equiv b \ (\text{mod} \ mn).
    Lemma 3

      The number a is a primitive root modulo m if and only if \displaystyle a^{\frac{\phi(m)}{q}} \not \equiv 1 \ (\text{mod} \ m) for all prime divisors q of \phi(m).

Lemma 2 a version of the Chinese Remainder Theorem and is proved a previous post (see Theorem 2 in Primitive roots of twice the powers of odd primes or see Theorem 2 in Proving Chinese Remainder Theorem). Lemma 3 is also proved in a previous post (see Lemma 2 in More about checking for primitive roots).

___________________________________________________________________________________________________________________

Breaking It Up Into Smaller Pieces

The proof of the direction \Longrightarrow of the primitive root theorem is done in the following lemmas and theorems.

    Lemma 4

      Let \displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of the positive integer m. Let a be a primitive root modulo m. Then the numbers \phi(p_1^{e_1}), \phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}) are pairwise relatively prime.

Proof of Lemma 4
Note that a is relatively prime to m. So a is relatively prime to each p_j^{e_j}. By Euler’s theorem, we have \displaystyle a^{\phi(p_j^{e_j})} \equiv 1 \ (\text{mod} \ p_j^{e_j}) for each j. Let \displaystyle W=\text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t})).

By definition of LCM, \phi(p_j^{e_j}) \ \lvert \ W for each j. So \displaystyle a^{W} \equiv 1 \ (\text{mod} \ p_j^{e_j}) for each j. By the Chinese remainder theorem (Lemma 2 above), \displaystyle a^{W} \equiv 1 \ (\text{mod} \ m). Since a is a primitive root modulo m, it must be that \phi(m) \le W. Interestingly, we have:

    \displaystyle \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})=\phi(m) \le W \le \phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t})

Thus \displaystyle \text{LCM}(\phi(p_1^{e_1}),\phi(p_2^{e_2}),\cdots,\phi(p_t^{e_t}))=\phi(p_1^{e_1}) \phi(p_2^{e_2}) \cdots \phi(p_t^{e_t}). By Lemma 1, the numbers \phi(p_j^{e_j}) are relatively prime. \blacksquare

The following theorems follow from Lemma 4. The main theorem is a corollary of these theorems.

    Theorem 5

      If there exists a primitive root modulo m, then m cannot have two distinct prime divisors.

Proof of Theorem 5
Let \displaystyle m=p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} be the prime factorization of m where t \ge 2.

If p_i and p_j are odd prime with i \ne j, then \phi(p_i^{e_i})=p_i^{e_i-1}(p_i-1) and \phi(p_j^{e_j})=p_j^{e_j-1}(p_j-1) are both even and thus not relatively prime. If there exists a primitive root modulo m, \phi(p_i^{e_i}) and \phi(p_j^{e_j}) must be relatively prime (see Lemma 4). Since we assume that there exists a primitive root modulo m, m cannot have two distinct odd prime divisors. \blacksquare

    Theorem 6

      Suppose that there exists a primitive root modulo m and that m has exactly one odd prime factor p. Then m must be of the form p^e or 2p^e where e \ge 1.

Proof of Theorem 6
By Theorem 5, the prime factorization of m must be m=2^{e_1} p^{e_2} where e_1 \ge 0 and e_2 \ge 1.

We claim that e_1=0 or e_1=1. Suppose e_1 \ge 2. Then \phi(2^{e_1})=2^{e_1-1} and \phi(p^{e_2})=p^{e_2-1}(p-1) are both even and thus not relatively prime. Lemma 4 tells us that there does not exist a primitive root modulo m. So if there exists a primitive root modulo m, then it must be the case that e_1=0 or e_2=1.

If e_1=0, then m=p^{e_2}. If e_1=1, then m=2p^{e_2}. \blacksquare

    Lemma 7

      Let n=2^k where k \ge 3. Then \displaystyle a^{\frac{\phi(n)}{2}} \equiv 1 \ (\text{mod} \ n) for any a that is relatively prime to n.

Proof of Lemma 7
We prove this by induction on k. Let k=3. Then n=8 and \displaystyle \frac{\phi(8)}{2}=2. For any odd a with 1 \le a <8, it can be shown that a^2 \equiv 1 \ (\text{mod} \ 8).

Suppose that the lemma holds for k where k \ge 3. We show that it holds for k+1. Note that \phi(2^k)=2^{k-1} and \displaystyle \frac{\phi(2^k)}{2}=2^{k-2}. Since the lemma holds for k, we have \displaystyle v^{2^{k-2}} \equiv 1 \ (\text{mod} \ 2^k) for any v that is relatively prime to 2^k. We can translate this congruence into the equation v^{2^{k-2}}=1+2^k y for some integer y.

Note that \phi(2^{k+1})=2^{k} and \displaystyle \frac{\phi(2^{k+1})}{2}=2^{k-1}. It is also the case that (v^{2^{k-2}})^2=v^{2^{k-1}}. Thus we have:

    \displaystyle v^{2^{k-1}}=(1+2^k y)^2=1+2^{k+1} y+2^{2k} y^2=1+2^{k+1}(y+2^{k-1} y^2)

The above derivation shows that \displaystyle v^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1}) for any v that is relatively prime to 2^k.

On the other hand, a is relatively prime to 2^{k+1} if and only if a is relatively prime to 2^k. So \displaystyle a^{\frac{\phi(2^{k+1})}{2}} \equiv 1 \ (\text{mod} \ 2^{k+1}) for any a that is relatively prime to 2^{k+1}. Thus the lemma is established. \blacksquare

    Theorem 8

      Suppose that there exists a primitive root modulo m and that m=2^e where e \ge 1. Then m=2^e where e=1 or e=2.

Proof of Theorem 8
Suppose m=2^e where e \ge 3. By Lemma 7, \displaystyle a^{\frac{\phi(m)}{2}} \equiv 1 \ (\text{mod} \ n) for any a relatively prime to m. Since 2 is the only prime divisor of m, by Lemma 3, there cannot be primitive root modulo m. Thus if there exists a primitive root modulo m and that m=2^e where e \ge 1, then the exponent e can be at most 2. \blacksquare

___________________________________________________________________________________________________________________

Putting It All Together

We now put all the pieces together to prove the \Longrightarrow of the Main Theorem. It is a matter of invoking the above theorems.

Proof of Main Theorem
Suppose that there exists a primitive root modulo m. Consider the following three cases about the modulus m.

  1. m has no odd prime divisor.
  2. m has exactly one odd prime divisor.
  3. m has at least two odd prime divisors.

\text{ }
Suppose Case 1 is true. Then m=2^e where e \ge 1. By Theorem 8, m=2 or m=4.

Suppose Case 2 is true. Then Theorem 6 indicates that m must be the power of an odd prime or twice the power of an odd prime.

Theorem 5 indicates that Case 3 is never true. Thus the direction \Longrightarrow of the Main Theorem is proved. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Primitive roots of twice the powers of odd primes

In a previous post, we show that there exist primitive roots modulo the power of an odd prime number (see Primitive roots of powers of odd primes). In this post we show that there exist primitive roots modulo two times the power of an odd prime number. Specifically we prove the following theorem.

    Theorem 1

      Let p be an odd prime number. Let j be any positive integer. Then there exist primitive roots modulo p^j.

We make use of the Chinese Remainder Theorem (CRT) in proving Theorem 1. We use the following version of CRT (also found in this post)

    Theorem 2 (CRT)

      Let m and n be positive integers that are relatively prime. Then a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n) if and only if a \equiv b \ (\text{mod} \ mn).

Proof of Theorem 2
\Longrightarrow
Suppose a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). Converting these into equations, we have a=b+mx and a=b+ny for some integers x and y. It follows that mx=ny. This implies that m \ \lvert \ ny. Since m and n and relatively prime, m \ \lvert \ y and y=mt for some integer t. Now the equation a=b+ny can be written as a=b+mnt, which implies that a \equiv b \ (\text{mod} \ mn).

\Longleftarrow
Suppose a \equiv b \ (\text{mod} \ mn). Then a=b+mns for some integer s, which implies both congruences a \equiv b \ (\text{mod} \ m) and a \equiv b \ (\text{mod} \ n). \blacksquare

Proof of Theorem 1
Let a be a primitive root modulo p^j (shown to exist in the post Primitive roots of powers of odd primes). When a is odd, we show that a is a primitive root modulo 2p^j. When a is even, we show that a+p^j is a primitive root modulo 2p^j.

First the odd case. Since a is a primitive root modulo p^j, a^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j). Since a is odd, a^k is odd for all integers k \ge 1. So a^k \equiv 1 \ (\text{mod} \ 2) for all integers k \ge 1. By CRT (Theorem 2), a^k \not \equiv 1 \ (\text{mod} \ 2p^j) for all positive k<\phi(p^j)=\phi(2 p^j). This implies that a is a primitive root modulo 2p^j.

Now the even case. Note that a+p^j is odd (even + odd is odd). It is also the case that (a+p^j)^k is odd for all k \ge 1. Thus (a+p^j)^k \equiv 1 \ (\text{mod} \ 2) for all k \ge 1.

In expanding (a+p^j)^k using the binomial theorem, all terms except the first term a^k is divisible by p^j. So (a+p^j)^k \equiv a^k \ (\text{mod} \ p^j). Furthermore, a^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j) since a is a primitive root modulo p^j. So (a+p^j)^k \not \equiv 1 \ (\text{mod} \ p^j) for all positive k<\phi(p^j).

By CRT (Theorem 2), we have (a+p^j)^k \not \equiv 1 \ (\text{mod} \ 2p^j) for all positive k<\phi(p^j)=\phi(2p^j). This implies that a+p^j is a primitive root modulo 2p^j. \blacksquare

The remainder of the proof of the primitive root theorem is found in The primitive root theorem.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Primitive roots of powers of odd primes

Let p be an odd prime number. There exist primitive roots modulo p (in fact there are \phi(p-1) many). There are various strategies for finding primitive roots of a prime modulus, other than simply trying all candidates (discussed here and here). In this post we discuss how to obtain primitive roots of moduli that are power of odd primes. Starting from a given primitive root modulo p, we show how to get a primitive root modulo p^2. Next, starting with a primitive root modulo p^2, we show how to get a primitive root modulo p^n for any integer n \ge 3. It follows from these results that there exist primitive roots modulo any power of any odd prime number. The results discussed in this post build up to the primitive root theorem. See the following posts for the rest of the proof of the primitive root theorem.

___________________________________________________________________________________________________________________

Example

We start the discussion with an example. There are two primitive roots for the odd prime modulus p=7. They are 3 and 5. Are 3 and 5 also primitive roots modulo 7^2=49?

Note that \phi(49)=\phi(7^2)=7(7-1)=42. One way to find out is to check

    3^x \ (\text{mod} \ 49) and 5^x \ (\text{mod} \ 49)

by letting x be the proper divisors of 42. The proper divisors of 42 are 1, 2, 3, 6, 7, 14, and 21. However, it is not necessary to check all 7 proper divisors of 42.

There is a better check that requires only checking 3 divisors of 42. According to a previous post, we only need to check the following:

    \displaystyle 3^{\frac{\phi(49)}{2}} \ (\text{mod} \ 49) and \displaystyle 3^{\frac{\phi(49)}{3}} \ (\text{mod} \ 49) and \displaystyle 3^{\frac{\phi(49)}{7}} \ (\text{mod} \ 49)

    \displaystyle 5^{\frac{\phi(49)}{2}} \ (\text{mod} \ 49) and \displaystyle 5^{\frac{\phi(49)}{3}} \ (\text{mod} \ 49) and \displaystyle 5^{\frac{\phi(49)}{7}} \ (\text{mod} \ 49)

To see why this works, see Check #3 in the post More about checking for primitive roots. Even this better check can be improved.

According to Lemma 1 discussed below, all we need to do is to check the following:

    3^6 \ (\text{mod} \ 49) and 5^6 \ (\text{mod} \ 49)

If the congruence \not \equiv 1 \ (\text{mod} \ 49), then the number in question is a primitive root modulo 49. Otherwise, it is not a primitive root. Note that the exponent is \phi(7)=6.

We have 3^6 \equiv 43 \ (\text{mod} \ 49) and 5^6 \equiv 43 \ (\text{mod} \ 49). So the two numbers 3 and 5 are primitive roots modulo 49.

Remarks
In general, given that a is a primitive root modulo p, to check whether a is a primitive root modulo p^2, all we need to do is to check a^{p-1} \ (\text{mod} \ p^2). If it is \not \equiv 1 \ (\text{mod} \ p^2), then a is a primitive root modulo p^2. Otherwise, it is not a primitive root modulo p^2.

What makes this works is that if a is a primitive root modulo p, the order of a modulo p^2 can only be p-1 or p(p-1)=\phi(p^2) (see Lemma 1 below). When a^{p-1} \not \equiv 1 \ (\text{mod} \ p^2), the order of a modulo p^2 is not p-1 and is p(p-1)=\phi(p^2), which means that a is a primitive root modulo p^2. When a^{p-1} \equiv 1 \ (\text{mod} \ p^2), the order of a modulo p^2 is p-1, which means that a is not a primitive root modulo p^2.

Furthermore, in the case that the order of a modulo p^2 is p-1, even though the number a is not a primitive root modulo p^2, the number a+p is a primitive root modulo p^2 (see Theorem 2 below).

As an example, 31 \equiv 3 \ (\text{mod} \ 7). So 31 is also a primitive root modulo 7. But 31^6 \equiv 1 \ (\text{mod} \ 49). So 31 is not a primitive root modulo 49. However 38 is a primitive root modulo 49. Note that 38^6 \equiv 15 \ (\text{mod} \ 49). For more details, see Theorem 2 below.

Theorem 4 below states that any primitive root modulo p^2 is also a primitive root modulo any higher power of p. For example, 38 is a primitive root modulo 7^n for any n \ge 3.

___________________________________________________________________________________________________________________

Square of an Odd Prime

We now show that there exist primitive roots modulo the square of an odd prime (Theorem 2 below). The starting point is that there is a given primitive root modulo a prime number (the existence is proved in Primitive roots of prime moduli).

    Lemma 1

      Let p be a prime number. Let g be a primitive root modulo p. Let t be the order of g modulo p^2. Then either t=p or t=p(p-1).

Proof of Lemma 1
Immediately we know that t \ \lvert \ \phi(p^2)=p(p-1). Furthermore, it follows that g^t \equiv 1 \ (\text{mod} \ p^2), which implies g^t=1+p^2 y for some integer y. In turn this equation implies that g^t \equiv 1 \ (\text{mod} \ p). We also have we have p-1 \ \lvert \ t since the order of g modulo p is p-1.

So we have p-1 \ \lvert \ t and t \ \lvert \ p(p-1). In words, the integer t is at least p-1 and at the same time t is a divisor of p(p-1). The only possibilities of t are t=p-1 or t=p(p-1). \blacksquare

    Theorem 2

      Let p be an odd prime number. Let a be a primitive root modulo p. Then either a or a+p is a primitive root modulo p^2. Thus there exist primitive roots modulo p^2.

Proof of Theorem 2
Let k be the order of a modulo p^2. By Lemma 1, we have k=p-1 or k=\ p(p-1). Note that \phi(p^2)=p(p-1). Thus if it is the case that k=\ p(p-1), then a is a primitive root modulo p^2. So in the remainder of the proof, we assume that k=p-1.

Since a+p \equiv a \ (\text{mod} \ p), the number a+p is a primitive root modulo p. Let h be the order of a+p modulo p^2. Using Lemma 1 again, there are only two possibilities for h, namely h=p-1 or h=\ p(p-1)=\phi(p^2). If we can show that the case h=p-1 is not possible, then a+p must be a primitive root modulo p^2. To this end, we show (a+p)^{p-1} \not \equiv 1 \ (\text{mod} \ p).

Using the binomial theorem, we expand (a+p)^{p-1} as follows:

    \displaystyle (a+p)^{p-1}=a^{p-1}+\binom{p-1}{1}a^{p-2}p+\binom{p-1}{2}a^{p-3}p^2+\binom{p-1}{3}a^{p-4}p^3 +\cdots+p^{p-1}

All terms except the first two terms are divisible by p^2. Recall that we assume above that k=p-1 (the order of a modulo p^2). So in the following derivation, we use a^{p-1} \equiv 1 \ (\text{mod} \ p^2).

    \displaystyle \begin{aligned} (a+p)^{p-1}&\equiv a^{p-1}+\binom{p-1}{1}a^{p-2}p \ (\text{mod} \ p^2) \\&\equiv a^{p-1}+(p-1)a^{p-2}p \ (\text{mod} \ p^2) \\&\equiv a^{p-1}+p^2 a^{p-2}-p a^{p-2} \ (\text{mod} \ p^2)  \\&\equiv 1+0-p a^{p-2} \ (\text{mod} \ p^2) \\&\equiv 1-p a^{p-2} \ (\text{mod} \ p^2) \end{aligned}

We now need to show that 1-p a^{p-2} \not \equiv 1 \ (\text{mod} \ p^2). Suppose that 1-p a^{p-2} \equiv 1 \ (\text{mod} \ p^2). Then we have -p a^{p-2} \equiv 0 \ (\text{mod} \ p^2).

Because a^{p-1} \equiv 1 \ (\text{mod} \ p^2), a^{p-2} is the multiplicative inverse of a modulo p^2. Now multiply both sides of -p a^{p-2} \equiv 0 \ (\text{mod} \ p^2) by a, we get -p \equiv 0 \ (\text{mod} \ p^2), which implies p is divisible by p^2, a contradiction. So (a+p)^{p-1} \equiv 1-p a^{p-2} \not \equiv 1 \ (\text{mod} \ p^2). Thus h=p-1 is not possible. Then h=p(p-1), which means that a+p is a primitive root modulo p^2. \blacksquare

___________________________________________________________________________________________________________________

Higher Powers of an Odd Prime

In this section, we show that there exist primitive roots modulo any higher power of an odd prime.

    Lemma 3

      Let p be an odd prime number. If g be a primitive root modulo p^2, then g is also a primitive root modulo p.

Proof of Lemma 3
Let g be a primitive root modulo p^2 where p is an odd prime number. To show that g be a primitive root modulo p, we use the following result:

Let t be a prime divisor of \phi(p)=p-1. Then t is a prime divisor of \phi(p^2)=p(p-1). By the result indicated by (*), we have \displaystyle g^{\frac{p(p-1)}{t}} \not \equiv 1 \ (\text{mod} \ p^2). It follows that \displaystyle g^{\frac{p-1}{t}} \not \equiv 1 \ (\text{mod} \ p). Thus by the result indicated by (*), g is a primitive root modulo p. Note that if \displaystyle g^{\frac{p-1}{t}} \equiv 1 \ (\text{mod} \ p), then \displaystyle (g^{\frac{p-1}{t}})^p \equiv 1 \ (\text{mod} \ p). \blacksquare

    Theorem 4

      Let p is an odd prime number. Let a be a primitive root modulo p^2. Then a is a primitive root modulo p^{j} for all integers j \ge 3.

Proof of Theorem 4
Note that \phi(p^2)=p(p-1). Thus a^{p-1} \not \equiv 1 \ (\text{mod} \ p^2). By Lemma 3, the number a is also a primitive root modulo p. Thus a^{p-1} \equiv 1 \ (\text{mod} \ p). Thus a^{p-1}=1+wp for some integer w. It is the case that w cannot be a multiple of p. Otherwise, we would have a^{p-1} \equiv 1 \ (\text{mod} \ p^2). We will use that fact that w cannot be a multiple of p at a later step in the proof.

Let j be any integer with j \ge 3. Note that \phi(p^j)=p^{j-1}(p-1). We establish the following three claims.

Claim 1
Let k be the order of a modulo p^j. The possibilities for k are p^n(p-1) where n=1,2,3,\cdots,j-1.

Claim 2
It is the case that k \ne p^{j-2}(p-1). To establish this, we show \displaystyle a^{p^{j-2}(p-1)} \not \equiv 1 \ (\text{mod} \ p^j).

Claim 3
It is the case that k \ne p^{n}(p-1) for n=1,2,3,\cdots,j-3.

Once the three claims are established, the order of a modulo p^j must be \phi(p^j)=p^{j-1}(p-1). Hence a is a primitive root modulo p^j.

Claim 3 follows from Claim 2. Note that if \displaystyle a^{p^{n}(p-1)} \equiv 1 \ (\text{mod} \ p^j) where n=0,1,2,3,\cdots,j-3, then we can raise both sides of the equation by an appropriate power of p to get \displaystyle a^{p^{j-2}(p-1)} \equiv 1 \ (\text{mod} \ p^j).

Proof of Claim 1. Since k is the order, we have \displaystyle a^{k} \equiv 1 \ (\text{mod} \ p^j), which leads to \displaystyle a^{k} \equiv 1 \ (\text{mod} \ p^2). These two congruences imply k \ \lvert \ \phi(p^j)=p^{j-1}(p-1) and p(p-1) \ \lvert \ k.

Thus k is at least p(p-1) and divides p^{j-1}(p-1). With p being a prime, k can only be p(p-1), p^{2}(p-1), \cdots, p^{j-1}(p-1).

Proof of Claim 2.
We show that \displaystyle a^{p^{j-2}(p-1)} \not \equiv 1 \ (\text{mod} \ p^j). With a^{p-1}=1+wp derived at the beginning of the proof, we have \displaystyle a^{p^{j-2}(p-1)}=(1+wp)^{p^{j-2}}. Upon using the binomial theorem to expand \displaystyle (1+wp)^{p^{j-2}}, we see that all terms except the first two are divisible by p^j. We can discard them since we take congruence modulo p^j. The following shows the first two terms:

    \displaystyle \begin{aligned} a^{p^{j-2}(p-1)}&= (1+wp)^{p^{j-2}}  \\&\equiv 1+p^{j-2} wp \ (\text{mod} \ p^j) \\&\equiv 1+wp^{j-1} \ (\text{mod} \ p^j) \end{aligned}

We claim that 1+wp^{j-1} \not \equiv 1 \ (\text{mod} \ p^j). Suppose 1+wp^{j-1} \equiv 1 \ (\text{mod} \ p^j). Then wp^{j-1} \equiv 0 \ (\text{mod} \ p^j), which implies wp^{j-1}=p^j c for some integer c. Cancelling out p^{j-1}, we have w=p c, which contradicts the fact that w cannot be a multiple of p. So 1+wp^{j-1} \not \equiv 1 \ (\text{mod} \ p^j). This establish Claim 3 and the theorem is also established. \blacksquare

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}