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}

Advertisements

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}