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 are positive integers that are pairwise relatively prime. Let . Suppose we have the following system of linear congruence equations
such that each of the linear congruence equations has a unique solution, i.e. for each , and are relatively prime. Then the system of linear congruence equations has a unique solution modulo .
We first start with two examples.
Solve the following system of linear congruence equations.
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 . The solution is unique modulo 10353 = 17 x 21 x 29. This means that if is another solution, then .
The solution is where
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 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
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 . To this end, solve the linear diophantine equation . Then work backward.
The calculation on the left shows the repeated applications of divisions to show that . The calculation on the right works backward to solve . The solution is , the least residue of which is .
Solve the following system of linear congruence equations.
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).
The problem is then to solve the system of the above 3 linear congruence equations. The solution is where:
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:
The above gives the unique solution to the given system of linear equations.
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 are pairwise relatively prime and such that each equation by itself has a unique solution, i.e. and are relatively prime for each .
The following three steps describe how to obtain the solution to this system of equations.
Solve each equation individually to obtain the solution . 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.
For each , let be the product of all moduli where . Each is relatively prime to . Thus has a multiplicative inverse modulo . Equivalently solve the following equations individually.
For each , let be the inverse of modulo , i.e. .
The solution is given by
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 . The extended Euclidean algorithm is an excellent approach, especially in computer implementation.
Step 2 involves finding multiplicative inverses of the numbers . 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 .
Why does the algorithm work?
The number is a solution to each of the equations in the given system of linear congruence equations. To see that is a solution to the equation , note that:
In the above derivation, all the terms containing with drop out. This is because has as a factor. The product drops out since is the multiplicative inverse if modulo . Finally since is a solution of the equation . By the same reasoning, is the solution to all the other equations in the system.
To see that the solution is unique, see the proof in this previous post.