Euclidean Algorithm/Examples/24 and 138/Proof

Examples of Use of Euclidean Algorithm

The GCD of $24$ and $138$ is found to be:

$\gcd \set {24, 138} = 6$

Proof

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

\(\ds 138\)

\(=\)

\(\ds 5 \times 24 + 18\)

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

\(\ds 24\)

\(=\)

\(\ds 1 \times 18 + 6\)

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

\(\ds 18\)

\(=\)

\(\ds 3 \times 6\)

Thus:

$\gcd \set {24, 138} = 6$

$\blacksquare$