Results 1 to 3 of 3

Math Help - Where's my mistake?! (Chinese Remainder Theorem)

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    21

    Where's my mistake?! (Chinese Remainder Theorem)

    All '=' mean 'congruent to'

    P1: 3x=5(mod2) --> x=1(mod2)
    P2: 5x=4(mod3) --> x=2(mod3)
    P3: 2x=1(mod5) --> x=3(mod5)
    P4: 5x=6(mod7) --> x=4(mod7)

    M1 is 210/2 = 105
    M2 is 210/3 = 70
    M3 is 210/5 = 42
    M4 is 210/7 = 30

    Therefore,
    105*Y1=1(mod2) --> Y1=1(mod2)
    70*Y2=2(mod3) --> Y2=2(mod3)
    42*Y3=3(mod5) --> Y3=4(mod5)
    30*Y4=4(mod7) --> Y4=2(mod7)

    x equals 1*105*1 + 2*70*2 + 3*42*4 + 4*30*2 --> 1129

    x=1129(mod210)
    x=79(mod210)

    Check:
    Works for P1 and P2, but fails for P3 and P4.


    Where'd I go wrong?!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2007
    Posts
    21
    Quote Originally Posted by AgentNXP View Post
    Therefore,
    105*Y1=1(mod2) --> Y1=1(mod2)
    70*Y2=2(mod3) --> Y2=2(mod3)
    42*Y3=3(mod5) --> Y3=4(mod5)
    30*Y4=4(mod7) --> Y4=2(mod7)
    ..should be..

    105*Y1=1(mod2) --> Y1=1(mod2)
    70*Y2=1(mod3) --> Y2=1(mod3)
    42*Y3=1(mod5) --> Y3=3(mod5)
    30*Y4=1(mod7) --> Y4=4(mod7)

    and corrections consequently follow..


    Correct? Yes/No?








    ... I tried it out, and this doesnt work. Is there another mistake? or am I doing this completely wrong?
    Last edited by AgentNXP; November 6th 2007 at 04:35 PM. Reason: To explain that my way didn't work...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2006
    From
    San Diego
    Posts
    101
    Quote Originally Posted by AgentNXP View Post
    P1: 3x=5(mod2) --> x=1(mod2)
    P2: 5x=4(mod3) --> x=2(mod3)
    P3: 2x=1(mod5) --> x=3(mod5)
    P4: 5x=6(mod7) --> x=4(mod7)
    Here's how I solve it:

    (For integers a, b, c, and d)

    x \equiv 1 \mod 2 \Rightarrow x = 2a+1, so
    2a + 1 \equiv 2 \mod 3 \Rightarrow a = 3b+2 \Rightarrow x = 2(3b+2)+1 = 6b+5, so
    6b+5 \equiv 3 \mod 5 \Rightarrow b = 5c + 3 \Rightarrow x = 6(5c+3)+5 = 30c+23, so
    30c+23 \equiv 4 \mod 7 \Rightarrow c = 7d + 1 \Rightarrow x = 30(7d+1)+23 = 210d + 53.

    So x \equiv 53 \mod 210.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 01:57 PM
  2. Chinese remainder theorem 2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 19th 2009, 11:38 AM
  3. Chinese remainder theorem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 15th 2008, 07:12 PM
  4. Chinese Remainder Theorem 3
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 12:27 PM
  5. Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 10th 2006, 08:28 AM

Search Tags


/mathhelpforum @mathhelpforum