Euclidean Algorithm/Examples/306 and 657
Jump to navigation
Jump to search
Examples of Use of Euclidean Algorithm
The GCD of $306$ and $657$ is:
- $\gcd \set {306, 657} = 9$
Proof
\(\text {(1)}: \quad\) | \(\ds 657\) | \(=\) | \(\ds 2 \times 306 + 45\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds 306\) | \(=\) | \(\ds 6 \times 45 + 36\) | |||||||||||
\(\text {(3)}: \quad\) | \(\ds 45\) | \(=\) | \(\ds 1 \times 36 + 9\) | |||||||||||
\(\text {(4)}: \quad\) | \(\ds 36\) | \(=\) | \(\ds 4 \times 9\) |
Thus:
- $\gcd \set {306, 657} = 9$
$\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$