1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Extended euclidean algorithm and Chinese Remainder theorem

  1. Jun 23, 2013 #1
    1. The problem statement, all variables and given/known data

    Solve

    x [itex]\cong[/itex] 1 mod 7
    x [itex] \cong[/itex] 4 mod 6
    x [itex] \cong [/itex] 3 mod 5

    by (and I have to use this method) using Euclidean algorithm to find the largest common divisor, then the extended euclidean algorithm to find a linear combination, then a solution to each of the three modified congruences and then finally a solution to the system above.

    3. The attempt at a solution

    First I calculate the modulo M: M = m1*m2*m3 = 7*6*5 = 210.

    Then I calculate the individual Mi:

    M1 = 210 / 7 = 30
    M2 = 210 / 6 = 35
    M3 = 210 / 5 = 42

    The new congruences I have to solve become:

    30x1 [itex]\cong[/itex] 1 mod 7 (1)
    35x2 [itex] \cong[/itex] 1 mod 6 (2)
    42x3 [itex] \cong [/itex] 1 mod 5 (3)

    Finding the largest common divisor (7, 30) using Euclidean algorithm for (1):

    30 = 7*4 + 2
    7 = 2*3 + 1
    2 = 1*2 + 0

    Largest common divisor (7, 30) is 1. Using the extended Euclidean algorithm to find a linear combination:

    1 = 7 - 2*3
    1 = 7 - (30 - 7*4) * 3
    1 = 7 - 30 * 3 + 7 * 12
    1 = 13*7 - 30*3

    I have carried out this combination of the Euclidean algorithm and the extended Euclidean algorithm for (2) and (3), getting 6*6 - 1*35 and 17*5 - 2*42 respectively.

    Using one of the linear combinations, one can calculate a solution for the corresponding congruence so I can use 1 = 13*7 - 30*3 to solve (1).

    After I have found a solution for each of (1)-(3), I construct a solution to the system of congruences by using

    x = b1M1x1 + b2M2x2 + b3M3x3

    (where b is the 1, 4 and 3 respectively)

    This constructed solution will be in modulo 210 and will most likely require some reduction.

    Now, my problem is this: how do I get from a linear combination acquired from the extended euclidean algorithm (e. g. 1 = 13*7 - 30*3) to a solution to one of the equations (e. g. (1))?
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Extended euclidean algorithm and Chinese Remainder theorem
Loading...