Chinese remainder theorem

The Chinese remainder theorem is the name for several related results in abstract algebra and number theory.

Contents

1 Simultaneous congruences of integers 2 Statement for principal ideal domains 3 Statement for general rings 4 External links

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

<math>x \equiv a_i \pmod{n_i} \quad\mathrm{for}\; i = 1, \cdots, k.<math>

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

<math>e_i \equiv 1 \pmod{n_i} \quad\mathrm{and}\quad

e_i \equiv 0 \pmod{n_j}<math>

for j ≠ i.

The solution to the system of simultaneous congruences is therefore

<math> x = \sum_{i=1..k} a_i e_i.\ <math>

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

<math>x \equiv 2 \pmod{3} <math>

<math>x \equiv 3 \pmod{4} <math>

<math>x \equiv 2 \pmod{5}. <math>

Using the extended Euclidean algorithm for 3 and 4×5 = 20, we find (-13) × 3 + 2 × 20 = 1, i.e. e₁ = 40. Using the Euclidean algorithm for 4 and 3×5 = 15, we get (-11) × 4 + 3 × 15 = 1. Hence, e₂ = 45. Finally, using the Euclidean algorithm for 5 and 3×4 = 12, we get 5 × 5 + (-2) × 12 = 1, meaning e₃ = -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 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)) for all i and j. All solutions x are congruent modulo the least common multiple of the 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

<math>f : R/uR \rightarrow R/u_1R \times \cdots \times

R/u_k R <math>

such that

<math>x \;\mathrm{mod}\,uR \rightarrow (x \;\mathrm{mod}\,u_1R) \times \cdots \times

(x \;\mathrm{mod}\,u_kR). <math>

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

<math>r u_i + s u/u_i = 1. <math>

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

<math>g : R/u_1R \times \cdots \times R/u_kR

\rightarrow R/uR <math>

such that

<math>(a_1 \;\mathrm{mod}\,u_1R) \times \cdots \times (a_k \;\mathrm{mod}u_kR) \rightarrow

\sum_{i=1..k} a_i e_i \pmod{uR}. <math>

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

<math>f : R/I \rightarrow R/I_1 \times \cdots \times R/I_k <math>

such that

<math>x \;\mathrm{mod}\,I \rightarrow (x \;\mathrm{mod}\,I_1) \times \cdots \times

(x \;\mathrm{mod} I_k).<math>

External links

• Chinese remainder theorem (http://www.cut-the-knot.org/blue/chinese.shtml)de:Chinesischer Restsatz

id:Teorema sisa Cina nl:Chinese reststelling ja:中国の剰余定理 pl:Chińskie twierdzenie o resztach sv:Kinesiska restsatsen zh:中国剩余定理