# 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.

____________________________________________________________________________

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.
$\copyright \ 2015 \text{ by Dan Ma}$