Results 1 to 5 of 5

Math Help - Chinese Remainder Theorem

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    19

    Chinese Remainder Theorem

    I'm finding it hard to get my head around Chinese Remainder Theorem. So wondering if anyone could help with this problem?

    Solve the egg problem used to illustrate the Chinese Remainder Theorem if the remainders on division by 2,3,4,5,6 and 7 are all 1 by (i) the given proceduce (ii) the easier way.

    I have no idea what the easier way is.

    But I have managed to set up the problem for (i) as below:

    X=1(Mod2)
    X=1(Mod3)
    X=1(Mod4) this is ignored as it is the same as the first
    X=1(Mod5)
    X=1(Mod6)
    X=1(Mod7)

    Is this correct and if so what is my next step?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by LL_5 View Post
    I'm finding it hard to get my head around Chinese Remainder Theorem. So wondering if anyone could help with this problem?

    Solve the egg problem used to illustrate the Chinese Remainder Theorem if the remainders on division by 2,3,4,5,6 and 7 are all 1 by (i) the given proceduce (ii) the easier way.

    I have no idea what the easier way is.

    But I have managed to set up the problem for (i) as below:

    X=1(Mod2)
    X=1(Mod3)
    X=1(Mod4) this is ignored as it is the same as the first
    X=1(Mod5)
    X=1(Mod6)
    X=1(Mod7)

    Is this correct and if so what is my next step?
    If x\equiv a(\bmod N) and x\equiv a(\bmod M) and \gcd(N,M)=1 then x\equiv a(\bmod NM). We will use this result.

    The first congruence can be ignored since x\equiv 1(\bmod 4) implies x\equiv 1(\bmod 2).

    The fifth congruence, x\equiv 1(\bmod 6) is equivalent to x\equiv 1(\bmod 2) \text{ and }x\equiv 1(\bmod 3). But these are already true. Thus, this congruence can be ignored also.

    We are left with,
    x\equiv 1(\bmod 3)
    x\equiv 1(\bmod 4)
    x\equiv 1(\bmod 5)
    x\equiv 1(\bmod 7)

    This is equivalent to,
    x\equiv 1(\bmod ~ 3\cdot 4\cdot 5\cdot 7)
    Last edited by ThePerfectHacker; November 6th 2008 at 07:07 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2008
    Posts
    19
    Thank you for that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2008
    Posts
    19
    What would the 'easier' way be?

    Would it be to take one egg away and then find the LCM.
    Last edited by LL_5; November 6th 2008 at 03:43 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by LL_5 View Post
    What would the 'easier' way be?

    Would it be to take one egg away and then find the LCM.
    This is the simpliest way. You bring all moduli to the point that each two are pairwise relatively prime. And then apply the theory that was posted above. With this approach all chinese remainder computations are eliminated.
    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, 08:56 PM
  2. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 08:34 AM
  3. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 23rd 2009, 09:26 PM
  4. Chinese Remainder Theorem 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2007, 09:00 PM
  5. Chinese Remainder Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 17th 2006, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum