Euclidean Algorithm/Examples/12378 and 3054
Jump to navigation
Jump to search
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