Chinese remainder theorem

From Exampleproblems

Jump to: navigation, search

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

Contents

Simultaneous congruences of integers

The original form of the theorem, contained in a third-century book by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, 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

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

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

e_i \equiv 1 \pmod{n_i} \quad\mathrm{and}\quad
e_i \equiv 0 \pmod{n_j}

for ji.

The solution to the system of simultaneous congruences is therefore

 x = \sum_{i=1..k} 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}.

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.

Sometimes, the simultaneous congruences can be solved even if the ni's 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.

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 u1, ..., uk are elements of R which are pairwise coprime, and 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 \rightarrow R/u_1R \times \cdots \times
R/u_k R

such that

x \;\mathrm{mod}\,uR \rightarrow (x \;\mathrm{mod}\,u_1R) \times \cdots \times
(x \;\mathrm{mod}\,u_kR).

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

rui + su / ui = 1.

Set ei = s u/ui. Then the inverse is the map

g : R/u_1R \times \cdots \times R/u_kR
\rightarrow R/uR

such that

(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}.

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 \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).

Applications of the Chinese remainder theorem

See also

External links

fr:Théorème des restes chinois id:Teorema sisa Cina nl:Chinese reststelling ja:中国の剰余定理 pl:Chińskie twierdzenie o resztach sv:Kinesiska restsatsen zh:中国剩余定理

Personal tools

Flash!
A Free Fun Game!
For Android 4.0

Get A Wifi Network
Switcher Widget for
Android