Thread: Extended euclidean algorighm question

I have some confusions about the procedure of extended EQ

say: gcd(81, 57)=3
here is what I did:

81=1*57+24
57=2*24+9
24=2*9+6
9=1*6+3
6=2*3+0

then I have problems when I do it from way back

3 = 9 -1(6)

From the line before that, I get 6 = 24 - 2(9), so:

3 = 9 - 1(24 - 2(9)) = ??

then I have no idea what to do. my friend give me this = 3(9) - 1(24), and I dont know where this comes from.

here is the solution he gave me, and I dont know where are all those underlined numbers come from, second part after the equal sign, how to substitute those numbers.

From the line before that, we see that 6 = 24 - 2(9), so:
3 = 9 - 1(24 - 2(9)) = 3(9) - 1(24).
From the line before that, we have 9 = 57 - 2(24), so:
3 = 3( 57 - 2(24)) - 1(24) = 3(57) - 7(24).
And, from the line before that 24 = 81 - 1(57), giving us:
3 = 3(57) - 7( 81 - 1(57)) = 10(57) -7(81).

Anyone give me a detailed explain..Thank you. I am struggling.

Lol i could see either then I realized how ridiculously obvious it is... expand the brackets!

3 = 9 - 1(24 - 2(9)) = 9 - 1(24) + 2(9) = 3(9) - 1(24).

Others are the same.

Second one would be,

3 = 3( 57 - 2(24) ) - 1(24) = 3(57) - 3*2(24) - 1(24) = 3(57) - 6(24) - 1(24) = 3(57) - 7(24).

Originally Posted by Deadstar

Lol i could see either then I realized how ridiculously obvious it is... expand the brackets!

3 = 9 - 1(24 - 2(9)) = 9 - 1(24) + 2(9) = 3(9) - 1(24).

Thanks, now I get it. It's just expand it and combine the "like terms".

yeah thats it.

Originally Posted by Deadstar

yeah thats it.

well, I did a couple of problems, and its getting better~