Chinese remainder theorem

The Chinese remainder theorem is any of a number of related results in abstract algebra and number theory.

Simultaneous congruences of integers

The original form of the theorem, contained in a book by the Chinese mathematician Qin Jiushao published in 1247, is a statement about simultaneous congruences (see modular arithmetic). Suppose n₁, ..., n_k are positive integers which are pairwise coprime (meaning gcd (n_i, n_j) = 1 whenever i ≠ j). Then, for any given integers a₁, ..., a_k, there exists an integer x solving the system of simultaneous congruences

$x\equiv a_{i}{\pmod {n_{i}}}\quad \mathrm {for} \;i=1,\cdots ,k$

Pseudocode "subtitle":

x_solves_it=true;
for(i= 1; i <= k; i++)
   if(x % n[i] != a[i] % n[i])
      x_solves_it=false;

Furthermore, all solutions x to this system are congruent modulo the product n = n₁...n_k.

A solution x can be found as follows. For each i, the integers n_i and n/n_i are coprime, and using the extended Euclidean algorithm we can find integers r and s such that r n_i + s n/n_i = 1. If we set e_i = s n/n_i, then we have

$e_{i}\equiv 1{\pmod {n_{i}}}\quad \mathrm {and} \quad e_{i}\equiv 0{\pmod {n_{j}}}$

for j ≠ i.

for (i= 1; i <= k; i++)
  {r, s}= ExtendedEuclid( n[i], n / n[i] );
  e[i]= s * n / n[i];
  for(j= 1; j <= k; j++)
    if (j != i)
      assert( e[i] % n[i] == 1 && e[i] % n[j] == 0 );

The solution to the system of simultaneous congruences is therefore

$x=\sum _{i=1..k}a_{i}e_{i}\$

for(i= 1; i <= k; i++)
  x += a[i] * e[i];

For example, consider the problem of finding an integer x such that

$x\equiv 2{\pmod {3}}$

$x\equiv 3{\pmod {4}}$

$x\equiv 2{\pmod {5}}$

 x % 3 == 2 % 3 &&
 x % 4 == 3 % 4 &&
 x % 5 == 2 % 5

Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (-13) × 3 + 2 × 20 = 1, i.e. e₁ = 40 (e[1] == 40). Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1. Hence, e₂ = 45 (e[2] == 45). Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (-2) × 12 = 1, meaning e₃ = -24 (e[3] == -24). A solution x is therefore 2 × 40 + 3 × 45 + 2 × (-24) = 167. All other solutions are congruent to 167 modulo 60, which means that they are all congruent to 47 modulo 60.

Sometimes, the simultaneous congruences can be solved even if the n_i's (n[i]'s) are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if a_i ≡ a_j (mod gcd(n_i, n_j)) (a[i] == a[j] % gcd(n[i], n[j]) for all i and j. All solutions x are congruent modulo the least common multiple of the n_i (n[i]).

Using the method of successive substitution can often yield solutions to simultaneous congruences, even when the moduli are not pairwise coprime.

Statement for principal ideal domains

For a principal ideal domain R the Chinese remainder theorem takes the following form: If u₁, ..., u_k are elements of R which are pairwise coprime, and u denotes the product u₁...u_k, then the ring R/uR and the product ring R/u₁R x ... x R/u_kR are isomorphic via the isomorphism

$f:R/uR\rightarrow R/u_{1}R\times \cdots \times R/u_{k}R$

such that

$x\;\mathrm {mod} \,uR\rightarrow (x\;\mathrm {mod} \,u_{1}R)\times \cdots \times (x\;\mathrm {mod} \,u_{k}R)$

The inverse isomorphism can be constructed as follows. For each i, the elements u_i and u/u_i are coprime, and therefore there exist elements r and s in R with

$ru_{i}+su/u_{i}=1$

Set e_i = s u/u_i. Then the inverse is the map

$g:R/u_{1}R\times \cdots \times R/u_{k}R\rightarrow R/uR$

such that

$(a_{1}\;\mathrm {mod} \,u_{1}R)\times \cdots \times (a_{k}\;\mathrm {mod} u_{k}R)\rightarrow \sum _{i=1..k}a_{i}e_{i}{\pmod {uR}}$

Statement for general rings

One of the most general forms of the Chinese remainder theorem can be formulated for rings and (two-sided) ideals. If R is a ring and I₁, ..., I_k are ideals of R which are pairwise coprime (meaning that I_i + I_j = R whenever i ≠ j), then the product I of these ideals is equal to their intersection, and the ring R/I is isomorphic to the product ring R/I₁ x R/I₂ x ... x R/I_k via the isomorphism

$f:R/I\rightarrow R/I_{1}\times \cdots \times R/I_{k}$

such that

$x\;\mathrm {mod} \,I\rightarrow (x\;\mathrm {mod} \,I_{1})\times \cdots \times (x\;\mathrm {mod} I_{k})$

External links

• Chinese remainder theorem