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 are positive integers that are pairwise relatively prime. Let . For any sequence of integers , the following system of linear congruence equations
has a unique solution modulo .
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 . Then the solution is used to build a solution to the first two equations, say , 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: and . Then is the solution to the first equation. Express the equation as for some integer . We would like to be the solution to the second equation too. Then we need to solve for in the following equation
Once we know what is, is the desired solution to the system of two equations. To solve for , subtract on both sides of (*) and then multiply both sides by the inverse of . Then where is the multiplicative inverse of modulo . The desired solution is where . From the way it is set up, is a solution to both equations.
Let’s look at the case of equations as described in the statement of Theorem F. Let be the solution to the first equations. We will use this to build , the solution to all the equations. The key is to solve for in the equation
Then where is the multiplicative inverse of modulo . Then the following
It is clear that for . This is because the term in vanishes. From the way is set up, it is clear that .
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 equations, as described and notated in the statement of Theorem F above. The algorithm is then to build a series of numbers
leading to the desired solution where and is the solution to the first equations and is obtained using as follows:
is defined such that
Note that the number is the multiplicative inverse of modulo . The desired solution may have to be reduced modulo .
In a computer implementation, the algorithm in 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 is to know that each step is obtained from solving for in the following equation:
If there are equations, the algorithm as described here requires the finding of applications of the extended Euclidean algorithm (for the multiplicative inverse in each induction step). If the given equations are in the form , then additional applications of the extended Euclidean algorithm are required to convert the equations to the form . 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.
Solve the following system of linear congruence equations.
This is Example 1 from this previous post. The results are , and as derived below:
where 5 is obtained by solving
where 13 is obtained by solving
Example is now completed.
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.
From Example 1, the solution to the first three equations is where 10353 is the product of the first three moduli. The following gives the solution:
where 30 is obtained by solving
The above gives the unique solution to the given system of linear equations.