From the classical Chinese remainder theorem on rings{concerning ideals}(one can see Dummit &foote for the theorem) How to Prove that
1)Let a & b be two relatively prime integers in Z.Let c & d be any two arbitrary integers.The there exits an integer x such that x=c(mod a) & x=d(mod b) & this x is unique upto (mod ab)
well given a and b, with gcd(a,b) = 1, since Z/(abZ) ≅ Z/aZ x Z/bZ, if we knew x, we could easily find c and d.
what we have to construct is the inverse isomorphism. so let's look at it a litle closer:
x (mod ab) ---> (x mod a, x mod b). it's always helpful to see a concrete example: let's take a = 2, b = 3:
0 --> (0,0)
1 --> (1,1)
2 --> (0,2)
3 --> (1,0)
4 --> (0,1)
5 --> (1,2). so given (y,z) in Z2 x Z3, how do we recover its correspondent in Z6?
the main thing we have to use is that gcd(2,3) = 1. obviously adding or multiplying the components together doesn't work.
but gcd(2,3) = 1, means there are integers (this is good) r,s with 2r + 3s = 1.
we can take r = -1, and s = 1. note that 2r + 3s = 1 --> 2r = 1 (mod 3) and 3s = 1 (mod 2).
this suggests we use -1 mod 3 (i.e.; 2) and 1 mod 2 in our formula.
since we want (1,1) to map back to 1, let's try: (y,z) --> (3s)y + (2r)z, modulo 6.
that is: (y,z) --> 3y + 4z (mod 6) (you can verify that this works).
note that if the z-coordinate is 0, we get an element of {0,3}, and if the y-coordinate is 0, we get an element of {0,2,4}, that is,
isomorphic images of Z2 and Z3 in Z6, respectively.
this approach works in general: we find m in Za such that bm = 1 (mod a), and n in Zb such that an = 1 (mod b).
then x = c(bm) + d(an) is the desired result: mod a, the d(an) term disappears, and the c(bm) term is c(1).
mod b, the c(bm) term disappears, and the d(an) term is d(1).