Using the Euclidean Algorithm find the greatest common divis

Using the Euclidean Algorithm, find the greatest common divisor c of 84 and 126. Then find integers m and n such that 84m + 126n = c

Solution

by the Euclidean Algorithm:

126 - 84*(1) = 42 ...(1)

84 - 42*(2) = 0

So gcd(126, 84) = 42.

and 84m + 126n = 42

compare equation (1), we get m = -1 and n = 1 and c = 42.