Results 1 to 4 of 4

Math Help - Need help understanding the Chinese Remainder Theorem

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    79

    Question Need help understanding the Chinese Remainder Theorem

    Here is a simple example.

    x 11 (mod 39)
    x 7 (mod 22)

    I would greatly appreciate it if someone could explain how to do this. I know first of all that 39a+22b=1. I believe you are supposed to use Euclid's Algorithm right? I know how to do Euclid's Algorithm I just don't understand how to use it to solve the problem I have shown above. Please explain as much as you can, big test coming up soon!
    Follow Math Help Forum on Facebook and Google+

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

    calculation details

    The typical question is to describe all x's such that
    x = 11 mod (39), and
    x = 7 mod (22)

    Since 22 and 39 are relatively prime, you can find the following 2 relations:
    22*16 = 1 mod 39, and
    39*13 = 1 mod 22.

    Then you make the number:
    n = 11*22*16 + 7*39*13 + k * 22 * 39, with k an arbitrary integer
    Note that:
    n = 11 mod 39, and
    n = 7 mod 22
    so this satisfies what you're looking for.

    Now:
    n = 7421 + k*22*39, or
    n = 7421 mod (22*39), or
    n = 557 mod 858.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by steph3824 View Post
    Here is a simple example.

    x 11 (mod 39)
    x 7 (mod 22)

    I would greatly appreciate it if someone could explain how to do this. I know first of all that 39a+22b=1. I believe you are supposed to use Euclid's Algorithm right? I know how to do Euclid's Algorithm I just don't understand how to use it to solve the problem I have shown above. Please explain as much as you can, big test coming up soon!
    I just asked a similar question in the Discrete section, you might get some additional info from that post. But I will explain what I've learned so far. If someone else has corrections or additions, please correct or enhance what I've said.

    First set up the following variables: multiply your modulos together to get m=(30)(22)=858; set a1=11, a2=7; divide m by each modulo to get M1=858/39=22 and M2=858/22=39; let m1=39 and m2=22

    Now set up the main equation for the CRT
    x=a1*M1*y1 + a2*M2*y2

    All that's left to do is figure out y1 and y2 so set up the following congruences:

    M1*y1 \equiv 1 (mod 39) and
    M2*y2 \equiv 1 (mod 22) which gives

    22*y1 \equiv 1 (mod 39)
    39*y2 \equiv 1 (mod 22)

    After solving these, I get y1 = 16 and y2 = -9

    x = (11)(22)(16) + (7)(39)(-9) = 1415 \equiv 557 (mod 858) so

    x = 557 + 858k, where k is an integer

    test 557 - (22)(25) = 7 and 557 - (39)(14) = 11

    Hope this helps
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2009
    Posts
    79
    These were both very helpful, thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. The chinese remainder theorem.
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: June 12th 2011, 07:52 PM
  2. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 09:20 PM
  3. Chinese remainder theorem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 20th 2009, 12:57 PM
  4. Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 1st 2008, 01:27 AM
  5. Chinese Remainder Theorem
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: November 17th 2006, 04:35 PM

Search Tags


/mathhelpforum @mathhelpforum