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

We first start with two 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}

Advertisements

4 thoughts on “How to Chinese remainder, part 1

  1. Pingback: How to Chinese remainder, part 2 | 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