Question

Use the extended Euclidean algorithm to express gcd(144,89) as a linear combination of 144 and 89.

Short answer

gcd(144,89) = 1

Linear combinations$34.144+\left(-55\right).89=1$

Step-by-step solution

Step: 1

By using extended Euclidean algorithm

144 is not a prime, it is a composite number.

But 89 is a prime number it can be broken down to other prime factors.

Step: 2

gcd(144,89) = 1

Linear combinations$34.144+\left(-55\right).89=1$