display | more...
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 n1,....nm be pairwise coprime positive integers, that is, (ni,nj)=1 for each distinct i,j. Then if a1,... am are integers the system of equations

a cgt a1 (mod n1), ..., a cgt to am (mod nm)
has an integer solution that is uniquely determined modulo n1...nm.

Here's an example:

n1=3, n2=4, a1=1, a2=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 I1,...,Im be ideals in a ring R and suppose that Ii+Ij=R for each distinct i,j. Then if a1,... am are elements of R there exists a in R such that the images of a and ai in the quotient ring R/Ii coincide. Further a is uniquely determined up to its coset a+I, where I is the intersection of all the Ii.

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

1 = nir + njs
On the other hand, if Ii+Ij=Z then we have an equation like the displayed one. Clearly any common divisor of ni and nj is a unit. Finally, note that the quotient ring Z/nZ is the ring of integers modulo n and that n1...nmZ is the intersection of the Ii.

Proof of the second theorem: Consider the inductive statement

S(k) R=I1 + I2 n....n Ik
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=I1 + I2 n....n Ik-1
Since R.R=R (it contains 1) and I1+Ik=R we deduce that
R=(I1+Ik)(I1 + I2 n....n Ik-1)
Multiplying out the brackets we see that the LHS is contained in
I1 + Ik(I2 n....n Ik-1)
But the second of thse terms is contained in I2 n....n Ik, and so we are done. Thus S(m) is true.

The same argument (with different labelling of the ideals) shows that Ii + the intersection of all Ij, with j different from i, is equal to R. Thus, for each i, we can choose bi in Ii and ci in the intersection of all Ij, for j different from i, such that ai=bi + ci. Now let a=c1+...+cn. Think about the image of a in R/Ii. In this ring each cj, for j different from i, has image zero. Also in this ring ci has the the same image as ai. Thus a has the required property that it has the same image as ai in R/Ii. If a' also has the same property then a-a' lies in each Ii, 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/I1 x....x R/Im.

Proof: Define a ring homomorphism f:R-->R/I1 x....x R/Im by f(a)=(a+I1,...,a+Im). 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.

"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?"

Log in or register to write something here or to contact authors.