Euclidean Algorithm/Examples/272 and 1479
Jump to navigation
Jump to search
Examples of Use of Euclidean Algorithm
The GCD of $272$ and $1479$ is:
- $\gcd \set {272, 1479} = 17$
Proof
\(\text {(1)}: \quad\) | \(\ds 1479\) | \(=\) | \(\ds 5 \times 272 + 119\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds 272\) | \(=\) | \(\ds 2 \times 119 + 34\) | |||||||||||
\(\text {(3)}: \quad\) | \(\ds 119\) | \(=\) | \(\ds 3 \times 34 + 17\) | |||||||||||
\(\text {(4)}: \quad\) | \(\ds 34\) | \(=\) | \(\ds 2 \times 17\) |
Thus:
- $\gcd \set {272, 1479} = 17$
$\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$: $1$