# Thread: GCD and extended euclidean algorithm

1. ## 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.

2. $\displaystyle 93=1*57+36\rightarrow 36=93-1*57$

$\displaystyle 57=1*36+21\rightarrow 21=57-1*36$

$\displaystyle 36=1*21+15\rightarrow 15=36-1*21$

$\displaystyle 21=1*15+6\rightarrow 6=21-1*15$

$\displaystyle 15=2*6+3\rightarrow 3=15-2*6$

$\displaystyle 6=2*3+0$

Can you take it from here?

3. 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.

4. $\displaysyle 3=15-2*6=15-2*(21-1*15)=15-2*21+2*15=15*3-2*21=3*(36-1*21)-2*21=\cdots$

5. 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.

6. 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, $3 = 15 - 2*6$ but above this we have $6 = 21-1*15$. By substitution, we obtain $3 = 15 - 2*(21-1*15)$. Then we simplify and continue to substitute.

7. 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.

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.