Euclidean Algorithm

[LandR]

Hi,

I'm trying to understand the euclidean (extended) algorithm to solve equations of the form

ax + by = gcd(a,b)

I've found a site with a couple of examples but I'm not following their steps very well...

Can someone explain how you go about it ?

I get that you find the gcd of (a,b) using euclid. e.g. gcd(17, 218) (just a random example.., if this example doesn't work can someone show another example ?) and that I can do this using the table:

(1) 218 = 17 x 12 + 14
(2) 17 = 14 x 1 + 3
(3) 14 = 3 x 4 + 2
(4) 3 = 2 x 1 + 1
(5) 2 = 2 x 1 + 0

So gcd(218, 17) = 1

So if I have the equation

218x + 17y = gcd(218, 17)
218x + 17y = 1

I then work backwards through the table above. starting with line (4) rearranged.

1 = 3 - 1 x 2
1 = 3 - 1 x (14 - (4 x 3)) >> here I sub in line (3) for 2.

It's at this point I have no idea how to proceed.

[maxpower1227]

Hmm.... I've never really seen these problems, but here is what I'm getting

(I am switching notation to 218x - 17y = 1)

218x - 17y = 1

218 - 17*12 = 14
218*5 - 17*(12*5 + 4) = 2
218*5*9 - 17*(12*5*9 + 4*9 + 1) = 1
218*45 - 17*577 = 1

ETA: I'm way off. Better answer coming soon...

[maxpower1227]

1 = 3 - 2*1
1 = (17-14*1) - (14-3*4)*1
1 = (17-(218-17*12)*1) - ((218-17*12)-(17-14*1)*4)*1
1 = (17-(218-17*12)*1) - ((218-17*12)-(17-(218-17*12)*1)*4)*1

1 = (17*13 - 218) - ((218-17*12)-(17*13-218)*4)*1
1 = (17*13 - 218) - ((218-17*12)-(17*52-218*4))
1 = (17*13 - 218) - (218*5 - 17*64)
1 = 17*77 - 218*6

[maxpower1227]

The key seems to be to re-write your key equations as:

(1) 218 - 17 x 12 = 14
(2) 17 - 14 x 1 = 3
(3) 14 - 3 x 4 = 2
(4) 3 - 2 x 1 = 1
(5) 2 - 2 x 1 = 0

and then continually making substitutions until all terms involve only multiples of 218 and 17

[jojonete]

ETA: Argh! just noticed that maxpower1227 had got the answer two posts ago. Ok, consider this as a different explanation of how to take the same steps to get to the same solution.

Originally Posted by maxpower1227

The key seems to be to re-write your key equations as:

(1) 218 - 17 x 12 = 14
(2) 17 - 14 x 1 = 3
(3) 14 - 3 x 4 = 2
(4) 3 - 2 x 1 = 1
(5) 2 - 2 x 1 = 0

and then continually making substitutions until all terms involve only multiples of 218 and 17

Yes, that's it. I've just learnt this by checking wikipedia, and I'll elaborate more to (a) show LandR how it applies to his/her example and (b) make sure myself that it can be done.

First, make it clear the problem we are trying to solve: 218x + 17y = 1

Second, the steps we'll follow: we'll solve all the following equations in order:
[p1] 218x + 17y = 218
[p2] 218x + 17y = 17
[p3] 218x + 17y = 14
[p4] 218x + 17y = 3
[p5] 218x + 17y = 2
[p6] 218x + 17y = 1

Of course, the last equation is the one we're actually interested in.

The two first ones are trivial:
218*1 + 17*0 = 218 [solution to p1]
218*0 + 17*1 = 17 [solution to p2]

Then we pick equation (1) from maxpower1227, and we readily have:
218*1 + 17*(-12) = 14 [solution to p3]

Now we pick equation (2) from maxpower1227:
17*1 + 14*(-1) = 3

Now, this should be 218x+17y=3, and not 17x+14y=3, but hey! in [solution to p3] we have 14 expressed as 218x+17y, so we can change the 14 to the form we need, so:
17*1 + (218*1 + 17*(-12)) * (-1) = 3

Joining all 218's and 17's we get:
218*(-1) + 17*13 = 3 [solution to p4]

Now we just repeat. From (3):
14*1 + 3*(-4) = 2

Substituting [solution to p3] for 14 and [solution to p4] for 3:
(218*1 + 17*(-12))*1 + (218*(-1) + 17*13)*(-4) = 2
218*5 + 17*(-64) = 2 [solution to p5]

Finally, from (4):
3*1 + 2*(-1) = 1

Changing 3 and 2 to their [solution to p4] and [solution to p5] equivalents:
(218*(-1) + 17*13)*1 + (218*5 + 17*(-64))*(-1) = 1
218*(-6) + 17*77 = 1 [solution to p6]

So, the solution to our original problem, 218x + 17y = 1, is:
x = -6
y = 77

He, he, now I'm sure I got it right

[LandR]

Thank you!!!