Results 1 to 3 of 3

Math Help - Getting stuck on the CRT

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    79

    Question Getting stuck on the CRT

    Ok, here's the problem.
    x 2 (mod 5)
    x 1 (mod 7)
    x 3 (mod 11)

    Here is what I have so far..

    M=5x7x11=385

    M1=385/5=77
    m2=385/7=55
    M3=385/11=35

    x=(a1xM1xy1)+(a2xM2xy2)+(a3xM3xy3)

    77y1 1 (mod 5)
    55y2 1 (mod 7)
    35y3 1 (mod 11)

    The issue I am having is getting the correct numbers for y1,y2,y3. What I am doing is using the Extended Euclidean Algorithm, but I'm not getting the numbers that are shown in my book, so I'm thinking that using the Extended Euclidean Algorithm isn't the proper way to figure out what the y's are. SO for example..I know that the solution to 77y1 1 (mod 5) is 3(mod 5), I just don't know where the 3 is coming from.

    I hope this has all made sense, I explained this as clearly as possible!! Thanks for the help!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    make the numbers smaller

    Everything looks right, but your numbers are too big. For instance,

    77 = 2(5), so you're looking for y s.t. 2y=1(5). Clearly this is 3.

    Similarly,

    55 = 6 (7), so you're looking for 6y = 1 (7) and y = 6.

    Can you keep going?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    79
    qmech, that made perfect sense. I understand it now, thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Stuck
    Posted in the Algebra Forum
    Replies: 6
    Last Post: January 21st 2010, 11:09 AM
  2. stuck with sin^4(x)
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 24th 2009, 04:56 PM
  3. Stuck on a Log :(
    Posted in the Algebra Forum
    Replies: 9
    Last Post: January 21st 2008, 12:10 PM
  4. somebody help me plz im so stuck
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: September 30th 2007, 11:43 AM
  5. Stuck, Stuck, Stuck - Need Help Urgently
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 17th 2005, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum