Results 1 to 3 of 3

Math Help - Chinese remainder theorem

  1. #1
    Newbie
    Joined
    Oct 2008
    From
    Montreal, Canada
    Posts
    7

    Chinese remainder theorem

    Hello everyone.
    This is not really a homework but it is very urgent.
    I have a Discrete math exam in one day and this problem is giving me so much headache!

    x\equiv 1(\bmod 4) (1)
    x\equiv 2(\bmod 5) (2)
    x\equiv 3(\bmod 7) (3)

    I tried finding inverses as well as reducing these three equations to two equations like:

    x+3\equiv 0(\bmod 28)
    x+3\equiv 0(\bmod 5)

    and in both cases the result does not work out for the equation (3).
    Could anyone please explain me why it is so and how to do this in a right way?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    The LCD is (4)(5)(7)=140

    I like to do it like this:

    Divide by the 'mods':

    140/4=35, 140/5=28, 140/7=20

    Now, find the inverses.

    35p_{1}\equiv 1(mod \;\ 4)\Rightarrow p_{1}=3

    28p_{2}\equiv 1(mod \;\ 5)\Rightarrow p_{2}=2

    20p_{3}\equiv 1(mod \;\ 7)\Rightarrow p_{3}=6

    Now, multiply:

    (1)(35)(3)+(2)(28)(2)+(3)(20)(6)=577

    x\equiv 577(mod 140)

    \boxed{x=17}

    Check the solution here:

    Javascript Calculator

    or the old-fashioned way:

    \frac{17-1}{4}=4
    \frac{17-2}{5}=3
    \frac{17-3}{7}=2

    Check.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    From
    Montreal, Canada
    Posts
    7
    Thank you very much! It turns out I made a miscalculation... few times in a row . {shame on me} But anyway, thank you for your answer and for you time.
    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