Using the Extended Euclidean Algorithm showing each step as

Using the Extended Euclidean Algorithm (showing each step as you go), compute gcd(2340, 384) and find the integers s and t such that 2340 · s + 384 · t = gcd(2340, 384).

Solution

2340=6*384+36    ,              36 = 2340-6*384

384=36*11-12      ,                12 = 36*11-384=11*2340-67*384

36=3*12+0

Hence

12 =11*2340-67*384

and gcd(2340,384)=12