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}

Advertisements

4 thoughts on “How to Chinese remainder, part 2

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

  2. Pingback: Versions of the Chinese remainder theorem | Exploring Number Theory

  3. Pingback: Another look at the fundamental theorem of arithmetic | 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