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

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}