# How to Chinese remainder, part 1

This is the third post in a series of posts on the Chinese remainder theorem (first post and second post). In this and the next post, we highlight two algorithms for obtaining the solution of a system of linear congruence equations. The Chinese remainder theorem guarantees that, under certain condition, any system of linear congruence equations has a unique solution (unique modulo the product of all the moduli of the congruence equations). The theorem is usually abbreviated as CRT. Even though the solution is unique, there are more than one way to solve systems of simultaneous linear congruence equations. In this post, we extract an algorithm from a constructive proof of CRT that is found in many textbooks (used here in this previous post). In the next post, we present another algorithm for solving systems of linear congruence equations.

The statement of CRT only guarantees the existence of a solution and does not show how to derive the unique solution. In many situations, it is sufficient to know that solutions exist (e.g. using CRT to prove theorems). In other situations where actual solutions are sought, we need more than the statement of CRT. In these situations, an algorithm is needed to actually find a solution. It is critical to have an algorithm for solving CRT problems, especially in computer implementation.

The algorithm discussed here is to solve the following is the version of the Chinese remainder theorem. This version has been shown to be equivalent to several other versions in this previous post.

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

____________________________________________________________________________

Examples

Example 1
Solve the following system of linear congruence equations.

$x \equiv 3 \ (\text{mod} \ 17)$

$x \equiv 10 \ (\text{mod} \ 21)$

$x \equiv 15 \ (\text{mod} \ 29)$

Both 17 and 29 are prime. The factors of 21 are 3 and 7. The three moduli are pairwise relatively prime (i.e. no two of which have a common factor other than 1). Thus CRT implies that the three equations have a solution $x_0$. The solution is unique modulo 10353 = 17 x 21 x 29. This means that if $y$ is another solution, then $y\equiv x_0 \ (\text{mod} \ 10353)$.

The solution is $x_0=3 \cdot 609 \cdot 11+10 \cdot 493 \cdot 19+15 \cdot 357 \cdot 13 \ (\text{mod} \ 10353)$ where

$609=21 \cdot 29$ and $609 \cdot 11 \equiv 1 \ (\text{mod} \ 17)$

$493=17 \cdot 29$ and $493 \cdot 19 \equiv 1 \ (\text{mod} \ 21)$

$357=17 \cdot 21$ and $357 \cdot 13 \equiv 1 \ (\text{mod} \ 29)$

The number 609 is the product of the remaining moduli (all the modulo not 17). Because 609 and the modulus 17 are relatively prime, the number 609 has a multiplicative inverse modulo 17. The multiplicative inverse is 11, found using the extended Euclidean algorithm. The other two pairs “493 and 19” and “357 and 13” are found similarly. Thus the solution $x_0$ is the sum of three numbers. The first is 3 x 609 x 11, where 3 is the solution to the first equation, and 609 and 11 multiplicative inverses to each other modulo 17. The other two numbers 10 x 493 x 19 and 15 x 357 x 13 are obtained similarly.

After reducing modulo 10353, the solution is

\displaystyle \begin{aligned} x_0&\equiv 3 \cdot 609 \cdot 11+10 \cdot 493 \cdot 19+15 \cdot 357 \cdot 13 \ (\text{mod} \ 10353) \\&\equiv 20097+93670+69615 \ (\text{mod} \ 10353) \\&\equiv 9744+493+7497 \ (\text{mod} \ 10353) \\&\equiv 17734 \ (\text{mod} \ 10353) \\&\equiv 7381 \ (\text{mod} \ 10353) \end{aligned}

The algorithm demonstrated here requires the computation of three multiplicative inverses. One try and true method for finding multiplicative inverse in the extended Euclidean algorithm (i.e. applying the Euclidean algorithm and then work backward). We demonstrate how to solve $609y \equiv 1 \ (\text{mod} \ 17)$. To this end, solve the linear diophantine equation $609y+17z=1$. Then work backward.

\displaystyle \begin{aligned} &609=17 \cdot 35+1 \\&17=14 \cdot 1+3 \\&14=3 \cdot 4+2 \\&3=2 \cdot 1+1 \\&2=1 \cdot 2+0 \\&\text{ } \\&\text{ } \end{aligned} \ \ \ \ \ \ \ \ \ \displaystyle \begin{aligned} 1&=3-2 \\&=3-(14-3 \cdot 4) \\&=14(-1)+3(5) \\&=14(-1)+(17-14)5 \\&=17(5)+14(-6) \\&=17(5)+(609-17 \cdot 35) (-6) \\&=609(-6)+17(215) \end{aligned}

The calculation on the left shows the repeated applications of divisions to show that $(609,17)=1$. The calculation on the right works backward to solve $609y+17z=1$. The solution is $y=-6$, the least residue of which is $y=11$. $\square$

Example 2
Solve the following system of linear congruence equations.

$3 \ x \equiv 1 \ (\text{mod} \ 5)$

$4 \ x \equiv 6 \ (\text{mod} \ 14)$

$5 \ x \equiv 11 \ (\text{mod} \ 3)$

The algorithm used in Example 1 works here. The only difference is that each equation needs to be solved individually. The numbers here are small. The equations can be solved by inspection. Otherwise, each equation can also be solved by solving an appropriate linear diophantine equation (as discussed here). The following are the solutions to the above equations (individually).

$x \equiv 2 \ (\text{mod} \ 5)$

$x \equiv 5 \ (\text{mod} \ 14)$

$x \equiv 1 \ (\text{mod} \ 3)$

The problem is then to solve the system of the above 3 linear congruence equations. The solution is $x_0=2 \cdot 42 \cdot 8+5 \cdot 15 \cdot 1+1 \cdot 70 \cdot 1$ where:

$42=14 \cdot 3$ and $42 \cdot 8 \equiv 1 \ (\text{mod} \ 5)$

$15=5 \cdot 3$ and $15 \cdot 1 \equiv 1 \ (\text{mod} \ 14)$

$70=5 \cdot 14$ and $70 \cdot 1 \equiv 1 \ (\text{mod} \ 3)$

The above calculation requires solving three linear congruence equations individually and finding three multiplicative inverses. Both tasks can be done using the extended Euclidean algorithm. After further reduction modulo 210, the unique solution is:

\displaystyle \begin{aligned} x_0&\equiv 2 \cdot 42 \cdot 8+5 \cdot 15 \cdot 1+1 \cdot 70 \cdot 1 \ (\text{mod} \ 210) \\&\equiv 672+75+70 \ (\text{mod} \ 210) \\&\equiv 42+75+70 \ (\text{mod} \ 210) \\&\equiv 187 \ (\text{mod} \ 210) \end{aligned}

The above gives the unique solution to the given system of linear equations. $\square$

____________________________________________________________________________

An algorithm for CRT

Now we describe the algorithm that is described by the above two examples. Suppose that the following system of equations such that the moduli $m1,m_2,\cdots,m_t$ are pairwise relatively prime and such that each equation by itself has a unique solution, i.e. $a_i$ and $m_i$ are relatively prime for each $i$.

$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)$

The following three steps describe how to obtain the solution to this system of equations.

Step 1
Solve each equation $a_i \ x \equiv b_i \ (\text{mod} \ m_i)$ individually to obtain the solution $x \equiv c_i \ (\text{mod} \ m_i)$. The original system is equivalent to the following equivalent system of equations, i.e. any solution to one system is the solution to the other.

$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)$

Step 2
For each $i$, let $n_i$ be the product of all moduli $m_j$ where $j \ne i$. Each $n_i$ is relatively prime to $m_i$. Thus $n_i$ has a multiplicative inverse modulo $m_i$. Equivalently solve the following equations individually.

$n_1 \ y \equiv 1 \ (\text{mod} \ m_1)$

$n_2 \ y \equiv 1 \ (\text{mod} \ m_2)$

$\cdots$

$n_{t-1} \ y \equiv 1 \ (\text{mod} \ m_{t-1})$

$n_t \ y \equiv 1 \ (\text{mod} \ m_t)$

For each $i$, let $w_i$ be the inverse of $n_i$ modulo $m_i$, i.e. $n_i^{-1} \equiv w_i \ (\text{mod} \ m_i)$.

Step 3
The solution is given by

$x_0 \equiv c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t \ (\text{mod} \ m)$

where $m=m_1 \cdot m_2 \cdots m_t$.

Let’s look at what the algorithm entails computationally. Step 1 requires solving a set of linear congruence equations individually (equivalently, solving linear diophantine equations individually), unless the equations are given in the form $x \equiv c_i \ (\text{mod} \ m_i)$. The extended Euclidean algorithm is an excellent approach, especially in computer implementation.

Step 2 involves finding multiplicative inverses of the numbers $n_i$. The extended Euclidean algorithm is also an excellent approach, especially in computer implementation.

Step 3 is to gather up the results from Step 1 and Step 2. The computation here is to reduce modulo $m=m_1 \cdot m_2 \cdots m_t$.

____________________________________________________________________________

Why does the algorithm work?

The number $x_0 \equiv c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t \ (\text{mod} \ m)$ is a solution to each of the equations in the given system of linear congruence equations. To see that $x_0$ is a solution to the equation $a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$, note that:

\displaystyle \begin{aligned} a_1 \cdot x_0&\equiv a_1 \cdot (c_1 \cdot n_1 \cdot w_1+c_2 \cdot n_2 \cdot w_2+\cdots+c_t \cdot n_t \cdot w_t) \\&\equiv a_1 \cdot c_1 \cdot n_1 \cdot w_1+a_1 \cdot c_2 \cdot n_2 \cdot w_2+\cdots+a_1 \cdot c_t \cdot n_t \cdot w_t \\&\equiv a_1 \cdot c_1 \cdot n_1 \cdot w_1 \\&\equiv a_1 \cdot c_1 \\&\equiv b_1 \ (\text{mod} \ m_1) \end{aligned}

In the above derivation, all the terms containing $n_j$ with $j \ne 1$ drop out. This is because $n_j$ has $m_1$ as a factor. The product $n_1 \cdot w_1$ drops out since $w_1$ is the multiplicative inverse if $n_1$ modulo $m_1$. Finally $a_1 \cdot c_1 \equiv b_1 \ (\text{mod} \ m_1)$ since $c_1$ is a solution of the equation $a_1 \ x \equiv b_1 \ (\text{mod} \ m_1)$. By the same reasoning, $x_0$ is the solution to all the other equations in the system.

To see that the solution $x_0$ is unique, see the proof in this previous post.

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