- #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 = m

_{1}*m

_{2}*m

_{3}= 7*6*5 = 210.

Then I calculate the individual M

_{i}:

M

_{1}= 210 / 7 = 30

M

_{2}= 210 / 6 = 35

M

_{3}= 210 / 5 = 42

The new congruences I have to solve become:

30x

_{1}[itex]\cong[/itex] 1 mod 7 (1)

35x

_{2}[itex] \cong[/itex] 1 mod 6 (2)

42x

_{3}[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 = b

_{1}M

_{1}x

_{1}+ b

_{2}M

_{2}x

_{2}+ b

_{3}M

_{3}x

_{3}

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