Apply polynomial time Euclidean algorithm to the given pairs to find their greatest common divisor: a. 144, 89 b. 16, 54

Question

Apply polynomial time Euclidean algorithm to the given pairs to find their greatest common divisor:

a. 144, 89

b. 16, 54

Answer 1

a) 144x89=12816 = LCM GCD=1

b)16x27=432= LCM, GCD=2