• Support PF! Buy your school textbooks, materials and every day products Here!

Extended euclidean algorithm and Chinese Remainder theorem

  • Thread starter Mkorr
  • Start date
  • #1
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))?
 

Answers and Replies

Related Threads on Extended euclidean algorithm and Chinese Remainder theorem

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
335
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
0
Views
977
Replies
2
Views
501
Replies
0
Views
2K
Replies
1
Views
2K
Replies
1
Views
536
Top