Can you take it from here?
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.
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.
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.