Euclidean Algorithm/Examples/56 and 72/Proof

Examples of Use of Euclidean Algorithm

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

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

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\)

Thus:

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

$\blacksquare$