Results 1 to 6 of 6

Math Help - chinese remainder theorem

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    85

    chinese remainder theorem

    how would i solve

     x\equiv 2mod3  , x\equiv 5mod8 , x\equiv 11mod13 im getting confused around the mod 13 and finding its inverse would appreciate answer..exam revision!thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by skystar View Post
    how would i solve

     x\equiv 2mod3  , x\equiv 5mod8 , x\equiv 11mod13 im getting confused around the mod 13 and finding its inverse would appreciate answer..exam revision!thanks
    The inverse of 11 mod 13 ?

    Euclidian algorithm :
    13=11+2 \implies 2=13-11

    11=2*5+1 \implies 1=11-2*5=11-(13-11)*5=11*6-13*5


    Therefore, 11*6=13*5+1

    --> 11*6=1 \mod 13

    The inverse of 11 is... ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    x\equiv{2(mod3)}......[1]
    x\equiv{5(mod8)}......[2]
    x\equiv{11(mod13)}........[3]

    From [1], we have x=3t+2

    Sub into [2]:

    3t+2\equiv{5(mod8)}

    3t\equiv{3(mod8)}

    t\equiv{1(mod8)}

    t=8s+1

    Sub into x=3t+2, 3(8s+1)+2=24s+5

    24s+4\equiv{11(mod13)}

    24s-6\equiv{(mod13)}

    \frac{24s-6}{13}

    This must be an integer. That occurs first at s=10

    By resubbing, we get 8(10)+1=82, 3(81)+2=245

    x=245

    We can check this and see it checks on our congruencies

    (245-2)/3=81
    (245-5)/8=30
    (245-11)/13=18

    Make sure I didn't go astray somewhere. Make sure this is the smallest.
    Last edited by galactus; May 29th 2008 at 01:37 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2008
    Posts
    85
    where did 3t+2 come from,,typo on [1]?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    I had 13 instead of 3 in the first one. Should be mod 3. I had mod 13
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Hey, check what I just found. I ran our problem through it and it checks

    That reminds me, the solutions should be written as 245 mod 312. I just posted the smallest.

    Section 7.3: Solving Lots of Congruences
    Last edited by galactus; May 29th 2008 at 03:25 PM.
    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
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: July 31st 2009, 07:34 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 1
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 26th 2007, 08:00 PM
  5. Chinese Remainder Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 17th 2006, 04:35 PM

Search Tags


/mathhelpforum @mathhelpforum