Results 1 to 3 of 3

Math Help - Chinese remainder theorem

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    7

    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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Re: Chinese remainder theorem

    Quote Originally Posted by jishnuray View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,367
    Thanks
    736

    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 25th 2010, 07:56 PM
  2. Chinese remainder theorem 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 19th 2009, 10:38 AM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2009, 08:26 PM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 01:27 AM
  5. chinese remainder theorem
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 29th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum