GCD from Prime Decomposition/Examples/121 and 66

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