Versions of the Chinese remainder theorem

This post is the second post in a series of posts on the Chinese remainder theorem (CRT). The previous post sets up the scene by discussing the fundamental theorem of arithmetic. In this post, we derive the various versions of CRT from a lemma (Lemma A below) that is equivalent to the fundamental theorem of arithmetic.

Links to the other posts in the series: first post, third post, fourth post.

____________________________________________________________________________

The starting point

Lemma A and Theorem B are discussed in the previous post. Lemma A is shown to be equivalent to the fundamental theorem of arithmetic. Lemma A makes CRT possible.

Lemma A
Let a, b and d>0 be integers. Suppose that \text{GCD}(a,d)=1, i.e. the greatest common divisor of a and d is 1. If d \lvert (a \cdot b), then d \lvert b.

Theorem B
The following conditions are equivalent:

  1. The statement of Lemma A.
  2. (Euclid’s lemma) If p is a prime number and p \lvert (a \cdot b), then either p \lvert a or p \lvert b.
  3. Every positive integer n>1 can be written as a product of prime numbers and that this product (called a factorization) is unique.

In this post, we start from Lemma A and derive several versions of CRT. First, let’s look at a consequence of Lemma A.

Lemma C
Let m_1,m_2,\cdots,m_t be positive integers that are pairwise relatively prime. Let M=m_1 \cdot m_2 \cdots m_t. Then for any integer n,

    M \lvert n if and only if m_i \ \lvert \ n for each i.

Proof
The direction \rightarrow is clear.

We show the direction \leftarrow. Suppose that for each i, m_i \lvert n. Then n=m_1 \cdot r_1 for some integer r_1. Note that m_2 \lvert n=m_1 \cdot r_1. By Lemma 1, m_2 \lvert r_1. We can write n=m_1 \cdot m_2 \cdot r_2 for some integer r_2. Continue the same argument, it follows that n=m_1 \cdot m_2 \cdots m_t \cdot r for some integer r. This means that M \lvert n. \square

____________________________________________________________________________

The Chinese remainder theorem

The following are several statements of the Chinese remainder theorem. The first version is a re-statement of Lemma C using congruence notation.

Theorem D (Chinese Remainder Theorem)
Let m_1,m_2,\cdots,m_t be positive integers that are pairwise relatively prime. Let M=m_1 \cdot m_2 \cdots m_t. Then for any integers a and b,

    a \equiv b \ (\text{mod} \ M) if and only if a \equiv b \ (\text{mod} \ m_i) for each i.

The proof of Lemma C would take care of Theorem D. Note that a \equiv b \ (\text{mod} \ y) means that y \lvert (a-b).

Theorem E (Chinese Remainder Theorem)
Let m_1,m_2,\cdots,m_t be positive integers that are pairwise relatively prime. Let M=m_1 \cdot m_2 \cdots m_t. Then for any integers a and b,

    the integer x_0 is a solution of the linear congruence equation a \cdot x \equiv b \ (\text{mod} \ M) if and only if the integer x_0 is satisfies simultaneously the following linear congruence equations:

      a \cdot x \equiv b \ (\text{mod} \ m_1)

      a \cdot x \equiv b \ (\text{mod} \ m_2)

      \cdots

      a \cdot x \equiv b \ (\text{mod} \ m_t)

Proof
By Theorem D, a \cdot x_0 \equiv b \ (\text{mod} \ M) if and only if a \cdot x_0 \equiv b \ (\text{mod} \ m_i) for each i. \square

Theorem F (Chinese Remainder Theorem)
Suppose m_1,m_2,\cdots,m_t are positive integers that are pairwise relatively prime. Let m=m_1 \cdot m_2 \cdots m_t. Suppose we have the following system of linear congruence equations

    a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)

    a_2 \ x \equiv b_2 \ (\text{mod} \ m_2)

      \cdots

    a_{t-1} \  x \equiv b_{t-1} \ (\text{mod} \ m_{t-1})

    a_t \  x \equiv b_t \ (\text{mod} \ m_t)

such that each of the linear congruence equations has a unique solution, i.e. for each i, a_i and m_i are relatively prime. Then the system of linear congruence equations has a unique solution modulo m=m_1 \cdot m_2 \cdots m_t.

Proof
First, a solution is produced. Then it is shown that the solution is unique. To produce the solution, the first step is solve each equation individually. Because a_i and m_i are relatively prime, the equation a_i \ x \equiv b_i \ (\text{mod} \ m_i) has a unique solution c_i. Thus a_i \ c_i \equiv b_i \ (\text{mod} \ m_i) for each i.

Next, let N_i be the product of all the moduli m_j where j \ne i. Note that N_i and m_i are still relatively prime. There exists a unique n_i such that N_i \ n_i \equiv  1 \ (\text{mod} \ m_i). In other words, n_i is the multiplicative inverse of N_i modulo m_i.

The proposed solution is x_0=c_1 \cdot N_1 \cdot n_1+c_2 \cdot N_2 \cdot n_2+\cdots+c_t \cdot N_t \cdot n_t. The following shows that x_0 is the solution to each equation.

    \displaystyle \begin{aligned} a_i x_0 &\equiv a_i (c_1 \cdot N_1 \cdot n_1+c_2 \cdot N_2 \cdot n_2+\cdots+c_i \cdot N_i \cdot n_i+ \cdots +c_t \cdot N_t \cdot n_t) \\&\equiv a_i \cdot c_1 \cdot N_1 \cdot n_1+a_i \cdot c_2 \cdot N_2 \cdot n_2+\cdots+a_i \cdot c_i \cdot N_i \cdot n_i +\cdots + a_i \cdot c_t \cdot N_t \cdot n_t \\&\equiv a_i \cdot c_i \cdot N_i \cdot n_i \\&\equiv a_i \cdot c_i \\&\equiv b_i  \ (\text{mod} \ m_i)  \end{aligned}

All the terms containing N_j with j \ne i drop out since N_j contains m_i as a factor. The product N_i \cdot n_i drops out since it is congruent to 1 modulo m_i. Then a_i \cdot c_i is congruent to b_i modulo m_i.

To show the uniqueness, suppose x is also a solution to the system of linear congruence equations. Then a_i \ x \equiv a_i \ x_0 \ (\text{mod} \ m_i) for each i. Multiplying the inverse of a_i on both sides, we have and x \equiv x_0 \ (\text{mod} \ m_i) for each i. By Theorem E, x \equiv x_0 \ (\text{mod} \ m). \square

Theorem G (Chinese Remainder Theorem)
Suppose m_1,m_2,\cdots,m_t are positive integers that are pairwise relatively prime. Let m=m_1 \cdot m_2 \cdots m_t. For any sequence of integers c_1,c_2,\cdots,c_t, the following system of linear congruence equations

    x \equiv c_1 \ (\text{mod} \ m_1)

    x \equiv c_2 \ (\text{mod} \ m_2)

      \cdots

    x \equiv c_{t-1} \ (\text{mod} \ m_{t-1})

    x \equiv c_t \ (\text{mod} \ m_t)

has a unique solution modulo m=m_1 \cdot m_2 \cdots m_t.

Proof
This follows directly from Theorem F. \square

____________________________________________________________________________

To complete the loop

To complete the loop, we show that Theorem G implies Theorem D. Suppose that a \equiv b \ (\text{mod} \ m_i) for each i. Consider the following system of congruence equations:

    x \equiv b \ (\text{mod} \ m_1)

    x \equiv b \ (\text{mod} \ m_2)

    \cdots

    x \equiv b \ (\text{mod} \ m_t)

The number b is clearly a solution to this system of equations. By Theorem G, this solution is unique. So any other solution to this system must be congruent to b modulo m=m_1 \cdot m_2 \cdots m_t. By assumption, a is a solution to the system. So a \equiv b \ (\text{mod} \ m). \square

The loop D \rightarrow E \rightarrow F \rightarrow G \rightarrow D is now complete. Theorem G is the usual statement of CRT. Based on the loop, any one of the theorems can be called the Chinese remainder theorem. Note that the loop by itself does not establish the Chinese remainder theorem. For that to happen, some condition outside the loop must imply one condition in the loop. The above discussion shows that the fundamental theorem of arithmetic (in the form of Lemma A) implies Theorem D.

____________________________________________________________________________

Comments

CRT is a versatile tool and is found to be useful in many areas of mathematics. One approach in applying CRT is that of a divide and conquer idea. The original problem is divided into smaller problems, which can be solved independently of one another. At the end, the results of the smaller problems are combined to form the solution of the original problem. For example, in solving a linear congruence equation a \cdot x \equiv b \ (\text{mod} \ M) for a large modulus M, CRT in the form of Theorem E suggests that the problem can be broken up into a set of linear congruence equations with smaller moduli. For this reason, CRT is important in computing (both theory and applications), especially in computing intensive areas such as coding theory and cryptography.

In the next posts, we discuss two algorithms for solving CRT simultaneous systems of equations and look at a few applications.

____________________________________________________________________________
\copyright \ 2015 \text{ by Dan Ma}

Advertisements

4 thoughts on “Versions of the Chinese remainder theorem

  1. Pingback: Another look at the fundamental theorem of arithmetic | Exploring Number Theory

  2. Pingback: How to Chinese remainder, part 1 | Exploring Number Theory

  3. Pingback: How to Chinese remainder, part 2 | Exploring Number Theory

  4. Pingback: Speeding up modular exponentiation using CRT | Exploring Number Theory

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s