Extended euclidean algorithm and Chinese Remainder theorem

[Mkorr]

Homework Statement

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.

The Attempt at a Solution

First I calculate the modulo M: M = m₁*m₂*m₃ = 7*6*5 = 210.

Then I calculate the individual M_i:

M₁ = 210 / 7 = 30
M₂ = 210 / 6 = 35
M₃ = 210 / 5 = 42

The new congruences I have to solve become:

30x₁ $\cong$ 1 mod 7 (1)
35x₂ $\cong$ 1 mod 6 (2)
42x₃ $\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 = b₁M₁x₁ + b₂M₂x₂ + b₃M₃x₃

(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))?

 

[kurt.physics]

I'm sorry if this question is too vague or if it's inappropriate but I have been working on this problem for the past few days and I can't figure out how to get from the linear combination to a solution.Thanks in advance for any help.