3 Use the Euclidean algorithm to express gcd144 89 as a line

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

Solution

Answer:
144 - (89 x 1) = 55
89 - (55 x 1) = 34
55 - (34 x 1) = 21
34 - (21 x 1) = 13
21 - (13 x 1) = 8
13 - (8 x 1) = 5
8 - (5 x 1) = 3
5 - (3 x 1) = 2
3 - (2 x 1) = 1
2 - (1 x 2) = 0

For the values 144 and 89
GCF = 1