Chinese remainder theorem

The following result was known to Chinese mathematics in the first century AD. By way of notation, if a,b are integers and n is a positive integer we write a cgt b (mod n) if n divides a-b.

Theorem Let n₁,....n_m be pairwise coprime positive integers, that is, (n_i,n_j)=1 for each distinct i,j. Then if a₁,... a_m are integers the system of equations

a cgt a₁ (mod n₁), ..., a cgt to a_m (mod n_m)

has an integer solution that is uniquely determined modulo n₁...n_m.

Here's an example:

n₁=3, n₂=4, a₁=1, a₂=2

Then we can take a=10 (or a=...,-2,22,34,...).

A generalisation of this result to ring theory nowadays gets called the Chinese Remainder Theorem. Let's state and prove this generalisation.

Theorem Let I₁,...,I_m be ideals in a ring R and suppose that I_i+I_j=R for each distinct i,j. Then if a₁,... a_m are elements of R there exists a in R such that the images of a and a_i in the quotient ring R/I_i coincide. Further a is uniquely determined up to its coset a+I, where I is the intersection of all the I_i.

Proof that the first theorem follows from the second: Take the ring R=Z and consider the ideals I_i=n_iZ. One has that (n_i,n_j)=1 iff I_i+I_j=Z. For, if n_i and n_j are coprime then Euclid's algorithm for the highest common factor supplies r,s such that

1 = n_ir + n_js

On the other hand, if I_i+I_j=Z then we have an equation like the displayed one. Clearly any common divisor of n_i and n_j is a unit. Finally, note that the quotient ring Z/nZ is the ring of integers modulo n and that n₁...n_mZ is the intersection of the I_i.

Proof of the second theorem: Consider the inductive statement

S(k) R=I₁ + I₂ n....n I_k

for k=2,....,m. Here n denotes intersection. By assumption, S(2) is true. I will show that S(k) is true for all these values of k, by induction. So suppose that S(k-1) holds. Thus

R=I₁ + I₂ n....n I_k-1

Since R.R=R (it contains 1) and I₁+I_k=R we deduce that

R=(I₁+I_k)(I₁ + I₂ n....n I_k-1)

Multiplying out the brackets we see that the LHS is contained in

I₁ + I_k(I₂ n....n I_k-1)

But the second of thse terms is contained in I₂ n....n I_k, and so we are done. Thus S(m) is true.

The same argument (with different labelling of the ideals) shows that I_i + the intersection of all I_j, with j different from i, is equal to R. Thus, for each i, we can choose b_i in I_i and c_i in the intersection of all I_j, for j different from i, such that a_i=b_i + c_i. Now let a=c₁+...+c_n. Think about the image of a in R/I_i. In this ring each c_j, for j different from i, has image zero. Also in this ring c_i has the the same image as a_i. Thus a has the required property that it has the same image as a_i in R/I_i. If a' also has the same property then a-a' lies in each I_i, hence the claimed uniqueness.

Finally a corollary that restates the result in terms of direct products of rings.

Corollary With the hypotheses and notation of the theorem there is an isomorphism of rings between R/I and the direct product R/I₁ x....x R/I_m.

Proof: Define a ring homomorphism f:R-->R/I₁ x....x R/I_m by f(a)=(a+I₁,...,a+I_m). The theorem shows that this map is surjective and has kernel I, hence we are done by the first isomorphism theorem.

One of the first people to ask the question of the so called Chinese Remainder Theorem was the Chinese mathematician Sun-Tsu.

He asked:

"There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2. What will be the number of things?"