Euclidean Algorithm/Examples/56 and 72/Integer Combination
< Euclidean Algorithm | Examples | 56 and 72
Jump to navigation
Jump to search
Examples of Use of Euclidean Algorithm
$8$ can be expressed as an integer combination of $56$ and $72$:
- $8 = 4 \times 56 - 3 \times 72$
Proof
From Euclidean Algorithm: $56$ and $72$ we have:
\(\text {(1)}: \quad\) | \(\ds 72\) | \(=\) | \(\ds 1 \times 56 + 16\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds 56\) | \(=\) | \(\ds 3 \times 16 + 8\) | |||||||||||
\(\text {(3)}: \quad\) | \(\ds 16\) | \(=\) | \(\ds 2 \times 8\) |
and so:
- $\gcd \set {56, 72} = 8$
Then we have:
\(\ds 8\) | \(=\) | \(\ds 56 - 3 \times 16\) | from $(2)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 56 - 3 \times \paren {72 - 1 \times 56}\) | from $(1)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 4 \times 56 - 3 \times 72\) | 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{(a)}$