Euclidean Algorithm/Examples/24 and 138

Examples of Use of Euclidean Algorithm

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

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

Integer Combination

$6$ can be expressed as an integer combination of $24$ and $138$:

$6 = 6 \times 24 - 1 \times 138$

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