# Extended Euclidean Algorithm - need help understanding 1 step

• Mar 30th 2009, 08:14 PM
Grillakis
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)
• Mar 30th 2009, 11:36 PM
clic-clac
Quote:

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.
• Mar 31st 2009, 09:16 AM
Grillakis
Quote:

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
• Mar 31st 2009, 09:20 AM
Grillakis
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
• Mar 31st 2009, 10:17 AM
clic-clac
$-2(50-1.35)=-2.50+2.35$ Do you agree?
Now if you add $35,$ you obtain what you want.
• Mar 31st 2009, 04:39 PM
Grillakis
Quote:

Originally Posted by clic-clac
$-2(50-1.35)=-2.50+2.35$ Do you agree?
Now if you add $35,$ 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.
• Mar 31st 2009, 05:44 PM
Grillakis
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 (Clapping)