Results 1 to 2 of 2

Math Help - Chinese Remainder Theorem

  1. #1
    Junior Member
    Joined
    Oct 2008
    From
    Dallas, TX
    Posts
    71

    Chinese Remainder Theorem

    I'm trying to find all solutions to this system of congruences:

    x = 1(mod 2) (sorry, I'm using = instead of the logical equivalence)
    x = 2(mod 3)
    x = 3(mod 5)
    x = 4(mod 11)

    2 * 3 * 5 * 11 = 330

    M1 = m / 2 = 165 (3 * 5 * 11)
    M2 = m / 3 = 110 (2 * 5 * 11)
    M3 = m / 5 = 66 (2 * 3 * 11)
    M4 = m /11 = 30 (2 * 3 * 5) (I think this is where my problem is)

    165 = 1(mod 2)
    110 = 1(mod 3)
    66 = 1(mod 5)
    30 = 8(mod 11)

    x = 1 * 165 * 1 + 2 * 110 * 2 + 3 * 66 * 1 + 4 * 30 * 8 = 1763

    1763 = 113(mod 330)

    x = 113 holds up for the first three congruences, but fails on the 4th.

    Could someone please point out where I'm going wrong? I have no problem solving the system with the first three congruences, but every time I add the fourth and try to solve it, I run into problems.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    I have noticed that people who use these mechanical algorithms for problems of this sort often end up with the wrong answer. I'm sure that the formulas work if they are used correctly, but in practice they seem to invite arithmetic mistakes. So I prefer to avoid the formulas and use more common-sense methods.

    In this case, if you can deal with the first three congruences then you know that x\equiv23\!\!\!\pmod{30}, and you want to combine this with x\equiv4\!\!\!\pmod{11}. The first of those congruences looks simpler if you add 7 to both sides, to get x+7\equiv0\!\!\!\pmod{30}. By good fortune, the second congruence also looks simpler if you add 7 to both sides, to get x+7\equiv0\!\!\!\pmod{11}. So x+7 is a multiple of both 11 and 30, and therefore it is a multiple of 330. Therefore x\equiv-7\equiv323\!\!\!\pmod{330}.
    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