GCD from Prime Decomposition/Examples/121 and 66
Jump to navigation
Jump to search
Example of Use of GCD from Prime Decomposition
The greatest common divisor of $121$ and $66$ is:
- $\gcd \set {121, 66} = 11$
Proof
\(\ds 121\) | \(=\) | \(\ds 11^2\) | ||||||||||||
\(\ds 66\) | \(=\) | \(\ds 2 \times 3 \times 11\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds 121\) | \(=\) | \(\ds 2^0 \times 3^0 \times 11^2\) | |||||||||||
\(\ds 66\) | \(=\) | \(\ds 2^1 \times 3^1 \times 11^1\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \gcd \set {121, 66}\) | \(=\) | \(\ds 2^0 \times 3^0 \times 11^1\) | |||||||||||
\(\ds \) | \(=\) | \(\ds 11\) |
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(a)}$