Results 1 to 4 of 4

Math Help - chinese remainder theorem

  1. #1
    Junior Member
    Joined
    Jun 2009
    Posts
    25

    chinese remainder theorem

    x congruent to 4 (mod 11)
    x congruent to 3 (mod 17)

    M = 11 * 17 = 187
    so M1 = 11, M2 = 17


    i'm trying to find the inverse of M1 and M2 but am unsure how because M1M1' congruent to 1 (mod 11) but M1M1' is a factor of 11 so it will always have a remainder of 0.

    can this be proven?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jun 2009
    Posts
    25
    nm, figured it out.

    11k+4 != 17l+3 so no solutions exist
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by silentbob View Post
    11k+4 != 17l+3 so no solutions exist
    Why not? 11(3)+4\,=\,37\,=\,17(2)+3.

    One way of solving such a problem is to find a particular solution by trial and error. In this case, it’s 37. The general solution is then of the form (particular solution) + (multiple of LCM of moduli). In this case, the general solution is x\,=\,37+187n,\quad n\in\mathbb Z.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by silentbob View Post
    nm, figured it out.

    11k+4 != 17l+3 so no solutions exist
    If GCD(m1,m2) = 1 then a solution exists. That is the first step.

    trying to find the inverse of M1 and M2
    That's a good 2nd step.
    The modular inverse of (m1,m2) and the modular inverse of (m2,m1).

    i'm trying to find the inverse of M1 and M2 but am unsure how because M1M1' congruent to 1 (mod 11) but M1M1' is a factor of 11 so it will always have a remainder of 0.
    I do not know what you are attempting with M1M1? I can't understand it. It seems as if you are trying to say: 11 will be a factor of m1m2 and 17 will be a factor of m1m2. Not sure. Just wondering.

    Best advice: use google to get additional info on the Chinese Remaider Theorem (CRT).
    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