Use the Euclidean Algorithm to express the greatest common d

Use the Euclidean Algorithm to express the greatest common divisor of 56 and 72 as a linear combination of 56 and 72.

Solution

72=56+16   , 16=72-56

56=16*3+8, 8=56-16*3=4*56-3*72

16=8*2+0

This ends the Euclidean Algorithm and greatest common divisor of 56 and 72 is 8

Hence, 8=4*56-3*72