Chinese Remainder Theorem

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. $x \equiv 3 \bmod 8$ $x \equiv 4 \bmod 9$ $x \equiv 2 \bmod 5$

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 $9 \times 5$ which is congruent to $3 \bmod 8$ 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. $315+40+72 \equiv 315 \equiv 3 \bmod 8$ $315+40+72 \equiv 40 \equiv 4 \bmod 9$ $315+40+72 \equiv 72 \equiv 2 \bmod 5$

Thus, 315+40+72 = 427  fulfills all congruences. Since $427 \equiv 67 \bmod (8 \times 9 \times 5)$, hence 67 is the expected value.

Formally, the CRT claims that if $m_{1},m_{2},...,m_{k}$ are pairwise relative prime positive integers and $a_{1},a_{2},...,a_{k}$ are any integers, then the congruences system $x \equiv a_{i} \bmod m_{i},$

for $1 \leq i \leq k$, has a unique solution modulo $M=m_{1} \times m_{2} \times ... \times m_{k}$. And the solution of the system is given by $x \equiv \sum_{i=1}^{k} a_{i}M_{i}(M_{i}^{-1} \bmod m_{i}) \bmod M$

where $M_{i} = \frac{M}{m_{i}}$, for $1 \leq i \leq k$.

Directly applying the formula, a value that meet the system $x \equiv 40 \bmod 439$ $x \equiv 128 \bmod 187$ $x \equiv 37 \bmod 345$ $x \equiv 159 \bmod 233$ $x \equiv 238 \bmod 413$

is 736388737.

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.1. $c_{i} \leftarrow 1.$
1.2. For j from 1 to (i-1) do the following:
1.2.1. $u \leftarrow m_{j}^{-1} \bmod m_{i}.$
1.2.2. $c_{i} \leftarrow u.c_{i} \bmod m_{i}.$
2. $u \leftarrow a_{1}$, $x \leftarrow u.$
3. For i from 2 to k do the following:
3.1. $u \leftarrow (a_{i}-x) c_{i} \bmod m_{i}$
3.2. $x \leftarrow x + u.\prod_{j=1}^{i-1} m_{j}$
4. Return x.

The incremental computation using the Garner’s algorithm can be described follows. Let $X_{i}$ and $Y_{i}$, are updated solution and sub solution, respectively, of the system of the first i congruences. In this case, $X_{1}=Y_{1}=a_{1}$. Subsequent computations for each congruence addition are $Y_{i}= ( (a_{i}-X_{i-1})\prod_{j=1}^{i-1}m_{j}^{-1} \bmod m_{i}).\prod_{j=1}^{i-1}m_{j},$

and $X_{i}=X_{i-1}+Y_{i},$

for $2 \leq i \leq k$. 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