How to Chinese remainder, part 2

This is the fourth post in a series of posts on the Chinese remainder theorem (usually abbreviated as CRT). The previous post presents an algorithm for solving systems of linear congruence equations, which is based on a constructive proof of CRT. This post presents another algorithm that is based on another constructive proof of CRT. Links to the previous posts in the series: first post, second post, third post.

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

____________________________________________________________________________

Discussion of Proof/Algorithm

To understand the algorithm, it is a good idea to understand the constructive proof of CRT on which the algorithm is based. The constructive proof is to build up a solution to the system of equations in CRT in an iterative fashion. The first equation (stated in the above statement of CRT) has a solution, which is $x_1=c_1$. Then the solution $x_1$ is used to build a solution to the first two equations, say $x_2$, which is then used to build the solution to the first three equations, and so on. So this constructive proof of a solution is an inductive proof.

Let’s look at the case of two equations: $x \equiv c_1 \ (\text{mod} \ m_1)$ and $x \equiv c_2 \ (\text{mod} \ m_2)$. Then $x_1=c_1$ is the solution to the first equation. Express the equation $x_1 \equiv c_1 \ (\text{mod} \ m_1)$ as $c_1=x_1+m_1 y$ for some integer $y$. We would like $x_1+m_1 y$ to be the solution to the second equation too. Then we need to solve for $y$ in the following equation

$x_1+m_1 \cdot y \equiv c_2 \ (\text{mod} \ m_2) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)$

Once we know what $y$ is, $x_1+m_1 \cdot y$ is the desired solution to the system of two equations. To solve for $y$, subtract $x_1$ on both sides of (*) and then multiply both sides by the inverse of $m_1$. Then $y=v_1 \cdot (c_2-x_1)$ where $v_1$ is the multiplicative inverse of $m_1$ modulo $m_2$. The desired solution is $x_2$ where $x_2=x_1+m_1 \cdot v_1 \cdot (c_2-x_1)$. From the way it is set up, $x_2$ is a solution to both equations.

Let’s look at the case of $t$ equations as described in the statement of Theorem F. Let $x_{t-1}$ be the solution to the first $t-1$ equations. We will use this to build $x_{t}$, the solution to all the $t$ equations. The key is to solve for $y$ in the equation

$x_{t-1}+m_1 \cdot m_2 \cdots m_{t-1} \cdot y \equiv c_{t} \ (\text{mod} \ m_{t})$

Then $y=v_{t-1} \cdot (c_{t}-x_{t-1})$ where $v_{t-1}$ is the multiplicative inverse of $m_1 \cdot m_2 \cdots m_{t-1}$ modulo $m_{t}$. Then the following

$x_{t}=x_{t-1}+(m_1 \cdot m_2 \cdots m_{t-1}) \cdot v_{t-1} \cdot (c_{t}-x_{t-1})$

It is clear that $x_{t} \equiv x_{t-1} \equiv c_i \ (\text{mod} \ m_i)$ for $i=1,\cdots,t-1$. This is because the term $(m_1 \cdot m_2 \cdots m_{t-1}) \cdot v_{t-1} \cdot (c_{t}-x_{t-1})$ in $x_{t}$ vanishes. From the way $x_{t}$ is set up, it is clear that $x_{t} \equiv c_{t} \ (\text{mod} \ m_{t})$.

The inductive argument just presented establishes that the system of linear congruence equations in Theorem F always has a solution. An algorithm can be created based on this inductive proof.

____________________________________________________________________________

An algorithm for CRT

Assume that the system has $t$ equations, as described and notated in the statement of Theorem F above. The algorithm is then to build a series of numbers

$x_1, x_2, \cdots, x_j, \cdots, x_t \ \ \ \ \ \ 2 \le j \le t$

leading to the desired solution $x_t$ where $x_1=c_1$ and $x_j$ is the solution to the first $j$ equations and is obtained using $x_{j-1}$ as follows:

$x_{j}=x_{j-1}+(m_1 \cdot m_2 \cdots m_{j-1}) \cdot v_{j-1} \cdot (c_{j}-x_{j-1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$v_{j-1}$ is defined such that $(m_1 \cdot m_2 \cdots m_{j-1}) \cdot v_{j-1} \equiv 1 \ (\text{mod} \ m_j)$

Note that the number $v_{j-1}$ is the multiplicative inverse of $m_1 \cdot m_2 \cdots m_{j-1}$ modulo $m_j$. The desired solution $x_t$ may have to be reduced modulo $m=m_1 \cdot m_2 \cdots m_{t}$.

In a computer implementation, the algorithm in $(1)$ is carried out iteratively to find the solution. If the calculation is to be carried by hand as an exercise, an alternative to memorizing the formula $(1)$ is to know that each step $x_{j}$ is obtained from solving for $y$ in the following equation:

$x_j \equiv x_{j-1}+m_1 \cdot m_2 \cdots m_{j-1} \cdot y \equiv c_{j} \ (\text{mod} \ m_{j})$

Comment
If there are $t$ equations, the algorithm as described here requires the finding of $t-1$ applications of the extended Euclidean algorithm (for the multiplicative inverse in each induction step). If the given equations are in the form $a_i \cdot x \equiv b_i \ (\text{mod} \ m_i)$, then $t$ additional applications of the extended Euclidean algorithm are required to convert the equations to the form $x \equiv c_i \ (\text{mod} \ m_i)$. Overall, the amount of computation is comparable to the algorithm discussed in the previous post.

The iterative nature of this algorithm is useful in the situations where the solution to a smaller system is known. For example, if we add an additional equation to an existing system of equations, then the solution to the new system can be found based on the solution to the smaller system. In particular, with one additional application of the extended Euclidean algorithm, the new solution can be found. The following two examples demonstrate how this works.

____________________________________________________________________________

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

This is Example 1 from this previous post. The results are $x_1=3$, $x_2=241$ and $x_3=7381$ as derived below:

\displaystyle \begin{aligned} x_2&\equiv 3+17 \cdot 5 \cdot (10-3) \ (\text{mod} \ 17 \cdot 21) \\&\equiv 598 \ (\text{mod} \ 357) \\&\equiv 241 \ (\text{mod} \ 357) \end{aligned}

where 5 is obtained by solving $17y \equiv 1 \ (\text{mod} \ 21)$

\displaystyle \begin{aligned} x_3&\equiv 241+(17 \cdot 21) \cdot 13 \cdot (15-241) \ (\text{mod} \ 17 \cdot 21 \cdot 29) \\&\equiv -1048625 \ (\text{mod} \ 10353) \\&\equiv 7381 \ (\text{mod} \ 10353) \end{aligned}

where 13 is obtained by solving $(17 \cdot 21) y \equiv 1 \ (\text{mod} \ 29)$

Example is now completed. $\square$

Example 2
To illustrate the iterative nature of the algorithm, we add an addition equation to the system in 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)$

$x \equiv 16 \ (\text{mod} \ 31)$

From Example 1, the solution to the first three equations is $x_3=7381 \ (\text{mod} \ 10353)$ where 10353 is the product of the first three moduli. The following gives the solution:

\displaystyle \begin{aligned} x_4&\equiv 7381+10353 \cdot 30 \cdot (16-7381) \ (\text{mod} \ 17 \cdot 21 \cdot 29 \cdot 31) \\&\equiv -2287487969 \ (\text{mod} \ 320943) \\&\equiv 193735 \ (\text{mod} \ 320943) \end{aligned}

where 30 is obtained by solving $10353 y \equiv 1 \ (\text{mod} \ 31)$

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

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