Thread: Extended Euclidean Algorithm - need help understanding 1 step

•
This comes from my notes. At the bottom where it says: 2*(50 - 1*35) = 3*35 - 2*50,
I am not figuring out 3 and the 2 come from in 3*35 - 2*50. I tried multiplying which gives me the 2*50 but the 3*35 I do not understand how they getting that.

This is easier with an example:
Solve 135x + 50y = gcd(135, 50)
135 = 2·50 + 35
50 = 1·35 + 15
35 = 2·15 + 5
15 = 3·5 + 0, so gcd(135, 50) = 5
5 = 35 – 2·15
15 = 50 – 1·35,
so 5 = 35 – 2·(50 – 1·35) = 3·35 – 2·50
35 = 135 – 2·50,
so 5 = 3·(135 – 2·50) – 2·50 = 3·135 – 8·50 (x = 3, y = -8)

5 = 35 – 2·(50 – 1·35) = 3·35 – 2·50

Is this the line you are talking about? There is a 35 in the left side so you get 3.35 on the right.

Originally Posted by clic-clac

Is this the line you are talking about? There is a 35 in the left side so you get 3.35 on the right.

Yes that is the line I am talking about. This right here:

3·35 – 2·50
^
|
|

I just do not know where that 3 is coming from

In other words, how does this:

5 = 35 – 2·(50 – 1·35)

equal this:

3·35 – 2·50

Thats the only thing I am not understanding

Do you agree?
Now if you add you obtain what you want.

Originally Posted by clic-clac

Do you agree?
Now if you add you obtain what you want.

It is not adding up because I am not getting:

3·35 – 2·50

I have to have it in this form.

(I can not get 1 single answer, as you see in the example from post 1)

Because this:

3·35 – 2·50

becomes this:

3·(135 – 2·50) – 2·50


which I know how to do.

I just figured out how they got it.

This is what I see:

35 – 2·(50 – 1·35) = 3·35 – 2·50
35 - 2·(50) + 2·(35)

Clic-Clac, when you told me about the extra 35, I am looking at it like this:

1·(35) - 2·(50) + 2·(35)

Since (35) are common, we add them, giving me:

- 2·(50) + 3·(35)

Thats what I needed to figure out.

Thanks for your help Clic-Clac