GCD from Prime Decomposition/Examples/51 and 87

From ProofWiki
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