Thread: GCD and extended euclidean algorithm

I have the following problem for homework:
Compute gcd(57,93), and find integers s and t such that 57s + 93t = gcd(57,93).

Now I have computed gcd(57,93) = 3 using the Extended Euclidean Algorithm. I am a bit lost on the second part of the question. I was wondering if somebody could help me start or lead me in the right direction as to how to solve the second part.

Can you take it from here?

That is what I used to find the gcd. I don't really know what the second part is asking me to do, or how to do it.

Not to sound ungrateful for you quick responses, but could you explain that a little. I don't really understand what you are doing there.

I am taking the GCD of 3 in the last equation and isolating it on one side of the equation. I then do the same for all the remainders. Then in each equation you will see, for instance, but above this we have . By substitution, we obtain . Then we simplify and continue to substitute.

Okay, thank you very much for the clarification. I continued that and ended up with 3 = 8 X 93 - 13 X 57. Thus making s = -13 and t = 8.

The problem is to solve 57s + 93t = gcd(57,93)= 3. Divide both sides of the equation by 3 to get 19s+ 31t= 1

(1) 19 divides into 31 once with remainder 12. 31- 19= 12

(2) 12 divides into 19 once with remainder 7. 19- 12= 7

(3) 7 divides into 12 once with remainder 5. 12- 7= 5

(4) 5 divides into 7 once with remainder 2. 7- 5= 2

(5) 2 divides into 5 twice with remainder 1: 5- 2(2)= 1

Replace that '2" with 7- 5 from (4): 5- 2(7- 5)0= 3(5)- 2(7)= 1

Replace that "5" with 12- 7 from (3): 3(12- 7)- 2(7)= 3(12)- 5(7)= 1

Replace that "7" with 19- 12 from (2): 3(12)- 5(19- 12)= 8(12)- (5)19= 1

Replace that "12" with 31- 19 from (1): 8(31- 19)- 5(19)= (8)31- (13)(19)= 1

Comparing that with 19s+ 31t= 1 we can take s= -13 and t= 8.

Notice, by the way that is s= -13+ 31k and t= 8- 19k then 19s+ 31t= 19(-13)+ (19)(31)k+ 31(8)- 19(31)k= 1 since the "19(31)k" terms cancel.

Any pair of integers s= -13+ 31k and t= 9- 19k for any integer k, satisfy the equation.