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