Euclidean Algorithm/Examples/56 and 72

Examples of Use of Euclidean Algorithm

The GCD of $56$ and $72$ is found to be:

$\gcd \set {56, 72} = 8$

Integer Combination

$8$ can be expressed as an integer combination of $56$ and $72$:

$8 = 4 \times 56 - 3 \times 72$

Proof

\(\text {(1)}: \quad\)

\(\ds 72\)

\(=\)

\(\ds 1 \times 56 + 16\)

\(\text {(2)}: \quad\)

\(\ds 56\)

\(=\)

\(\ds 3 \times 16 + 8\)

\(\text {(3)}: \quad\)

\(\ds 16\)

\(=\)

\(\ds 2 \times 8\)