- #1
Mkorr
- 48
- 0
Homework Statement
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.
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))?