Euclidean Algorithm/Examples/12378 and 3054

Examples of Use of Euclidean Algorithm

The GCD of $12378$ and $3054$ is:

$\gcd \set {12378, 3054} = 6$

Integer Combination

$6$ can be expressed as an integer combination of $12378$ and $3054$:

$6 = 132 \times 12378 - 535 \times 3054$

Proof

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

\(\ds 12378\)

\(=\)

\(\ds 4 \times 3054 + 162\)

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

\(\ds 3054\)

\(=\)

\(\ds 18 \times 162 + 138\)

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

\(\ds 162\)

\(=\)

\(\ds 1 \times 138 + 24\)

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

\(\ds 138\)

\(=\)

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

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

\(\ds 24\)

\(=\)

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

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

\(\ds 18\)

\(=\)

\(\ds 3 \times 6 + 0\)

Thus:

$\gcd \set {12378, 3054} = 6$

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