Euclidean Algorithm/Examples/108 and 243
Jump to navigation
Jump to search
Examples of Use of Euclidean Algorithm
The GCD of $108$ and $243$ is:
- $\gcd \set {108, 243} = 27$
Proof
\(\text {(1)}: \quad\) | \(\ds 243\) | \(=\) | \(\ds 2 \times 108 + 27\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds 108\) | \(=\) | \(\ds 4 \times 27\) |
Thus:
- $\gcd \set {108, 243} = 27$
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-2}$ Divisibility: Exercise $1 \ \text{(d)}$