The Chinese remainder theorem
There is a different interpretation of the Chinese remainder theorem. Let ℤr × ℤs be the Cartesian product of ℤr and ℤs. As ℤr and ℤs are rings, the set ℤr × ℤs itself is in a natural way a product ring, in which the operations are defined by
(ār, b̄s) + (c̄r, d̅s) := (ār + c̄r, b̄s + d̅s),
(ār, b̄s) · (c̄r, d̅s) := (ār · c̄r, b̄s · d̅s)
Proposition. Let r and s be two relatively prime integers greater than or equal to 2.
The map f: ℤrs ⟶ ℤr x ℤs, defined by f([x]rs) = ([x]r, [x]s), is a ring isomorphism. By the Chinese remainder theorem the system of congruences
x ≡ a (mod r)
x ≡ a (mod s)
admits exactly one solution modulo rs. This implies the surjectivity and the injectivity of the map. It is left to prove the fact that this map preserves the operations.
f is well defined if a ≡ b mod mn, then f(a mod mn) = f(b mod mn). Indeed, suppose that a ≡ b mod mn. Then mn divides a − b, and therefore m and n are divisors of a - b. This shows that a ≡ b mod m and a ≡ b mod n. hence
f(a mod mn) = (a mod m, mod n) = (b mod m, b mod n) = f(b mod mn)
| Z6 | Z2 | Z3 |
|---|---|---|
| 0 0 0 | ||
| 1 1 1 | ||
| 2 0 2 | ||
| 3 1 0 | ||
| 4 0 1 | ||
| 5 1 2 |
The map defined in Proposition 3.4.5 may also be described as follows. Write down all the elements of Z rs in a column. Next to it, in a second
column write down s times the elements of Z r . In a third column write down r times the elements of Z s . The correspondence f associates to each element
of Z rs the pair in Z r × Z s that can be read on its right. The reader will easily be able to check this result. Proposition 3.4.5 has an important application in computer science, as it allows to translate calculations in Z n into independent calculations in several Z n i , for i = 1, . . . , r, when n = n 1 n 2 · · · n r , with GCD(n i , n j ) = 1 for i = j.
The following example allows us to fully appreciate the advantages of this
method.