# Extended euclidean algorithm and Chinese Remainder theorem

1. Jun 23, 2013

### Mkorr

1. The problem statement, all variables and given/known data

Solve

x $\cong$ 1 mod 7
x $\cong$ 4 mod 6
x $\cong$ 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 $\cong$ 1 mod 7 (1)
35x2 $\cong$ 1 mod 6 (2)
42x3 $\cong$ 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))?