Euclidean Algorithm/Examples/24 and 138/Integer Combination

Examples of Use of Euclidean Algorithm

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

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

Proof

From Euclidean Algorithm: $24$ and $138$ we have:

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

and so:

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

Then we have:

\(\ds 6\)

\(=\)

\(\ds 24 - 1 \times 18\)

from $(2)$

\(\ds \)

\(=\)

\(\ds 24 - 1 \times \paren {138 - 5 \times 24}\)

from $(1)$

\(\ds \)

\(=\)

\(\ds 6 \times 24 - 1 \times 138\)

simplifying

$\blacksquare$

Sources

• 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.3$ The Euclidean Algorithm: Problems $2.3$: $2 \ \text{(b)}$