Use the extended Euclidean algorithm to express gcd(144, 89) as a linear combination of 144 and 89.
The extended Euclidean algorithm can be used to express gcd(a, b) as a linear combination with integer coefficients of the integers a and b. We set s0 = 1, s1 = 0, t0 = 0, and t1 = 1 and let sj = sj−2 − qj−1sj−1 and tj = tj−2 − qj−1tj−1 for j = 2, 3, . . . , n, where the qj are the quotients in the divisions used when the Euclidean algorithm finds gcd(a, b), as shown in the text. It can be shown (see [Ro10]) that gcd(a, b) = sna + tnb. The main advantage of the extended Euclidean algorithm is that it uses one pass through the steps of the Euclidean algorithm to find Bézout coefficients of a and b, unlike the method in the text which uses two passes.