# Math Help - Chinese remainder theorem

1. ## Chinese remainder theorem

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)

2. ## Re: Chinese remainder theorem

Originally Posted by jishnuray
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 the Chinese remaind theorem tells you that there is an isomorphism $\mathbb{Z}/ab\mathbb{Z}\xrightarrow{\approx}\mathbb{Z}/a\mathbb{Z}\times\mathbb{Z}/b\mathbb{Z}$ and gives you the explicit isomorphim--it's the reduction morphism in each coordinate. Interpret your problem then as you are looking for $x\in[ab]$ with $f\left(x+\mathbb{Z}/ab\mathbb{Z}\right)=\left(c+\mathbb{Z}/a\mathbb{Z},x+\mathbb{Z}/b\mathbb{Z}\right)$ you see then how it should go?

3. ## Re: Chinese remainder theorem

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