Prepared by Antonius Cahya Prihandoko
With a particular condition, the Chinese Remainder Theorem (CRT) is employed to obtain a single value x which is congruent to several different values in different modulus. It should be noted that all number of modulus have to be pairwise relative prime, that is no two of them have a common factor. Otherwise the existence of a solution cannot be guaranteed. For example, find an integer x which satisfies the following congruences.
A simple algorithm to compute x is, for each congruence, find a solution for such congruence which is a multiple of each other modulo and sum together all solutions. In practical, a multiple of which is congruent to is 315. In a similar way, an easy computation yields 40 and 72, for the second and third congruence, respectively. The sum of these three results can be analyzed follows.
Thus, 315+40+72 = 427 fulfills all congruences. Since , hence 67 is the expected value.
Formally, the CRT claims that if are pairwise relative prime positive integers and are any integers, then the congruences system
for , has a unique solution modulo . And the solution of the system is given by
where , for .
Directly applying the formula, a value that meet the system
For a fix system, the formula is powerful. It can be used to obtain solution of a system of many congruences in one computation. However, when the system is progressive, allowing congruences addition in further, the formula will less useful to update the system’s solution. In this case, a new solution has to be computed every time when a congruence is added to the system. This incremental computation will be efficiently done by meant of the Garner’s algorithm below.
1. For i from 2 to k do the following:
1.2. For j from 1 to (i-1) do the following:
3. For i from 2 to k do the following:
4. Return x.
The incremental computation using the Garner’s algorithm can be described follows. Let and , are updated solution and sub solution, respectively, of the system of the first i congruences. In this case, . Subsequent computations for each congruence addition are
for . It is clear that every time a congruence is added to the system, the updated solution is computed based on the previous last solution.
Townsville, 27 February 2013