Encyclopedia > Chinese remainder theorem

  Article Content

Chinese remainder theorem

The Chinese remainder theorem is the name applied to 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 Ch'in Chiu-Shao[?] published in 1247, is a statement about simultaneous congruences (see modular arithmetic). Suppose n1, ..., nk are positive integers which are pairwise coprime (meaning gcd(ni, nj) = 1 whenever ij). Then, for any given integers a1, ..., ak, there exists an integer x solving the system of simultaneous congruences

xai (mod ni)    for i = 1...k     (1)
Furthermore, all solutions x to this system are congruent modulo the product n = n1...nk.

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

ei ≡ 1 (mod ni)    and     ei ≡ 0 (mod nj)    for ji.
The number x = ∑i=1..k ai ei then solves the given system (1) of simultaneous congruences.

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

x ≡ 2 (mod 3)
x ≡ 3 (mod 4)
x ≡ 2 (mod 5)
Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (-13) × 3 + 2 × 20 = 1 (i.e. e1 = 40). Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1 (hence e2 = 45). Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (-2) × 12 = 1 (meaning e3 = -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.

Note that some systems of the form (1) can be solved even if the numbers ni are not pairwise coprime. The precise criterion is as follows: a solution x exists if and only if aiaj (mod gcd(ni, nj)) for all i and j. All solutions x are congruent modulo the least common multiple of the ni.

Statement for principal ideal domains

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

 f :     R/uR    -->  R/u1R x ... x R/ukR
       x mod uR  |-> ( (x mod u1R), ..., (x mod ukR) )

The inverse isomorphism can be constructed as follows. For each i, the elements ui and u/ui are coprime, and therefore there exist elements r and s in R with r ui + s u/ui = 1. Set ei = s u/ui. Then the map

 g :  R/u1R x ... x R/ukR  -->    R/uR    
      ( (a1 mod u1R), ..., (ak mod ukR) )  |->  ∑i=1..k ai ei mod 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 I1, ..., Ik are ideals of R which are pairwise coprime (meaning that Ii + Ij = R whenever ij), then the product I of these ideals is equal to their intersection, and the ring R/I is isomorphic to the product ring R/I1 x R/I2 x ... x R/Ik via the isomorphism

 f :     R/I    -->  R/I1 x ... x R/Ik
       x mod I  |-> ( (x mod I1), ..., (x mod Ik) )

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Ocean Beach, New York

... two or more races. 2.17% of the population are Hispanic or Latino of any race. There are 61 households out of which 29.5% have children under the age of 18 living wi ...

This page was created in 23.4 ms