GCD from Prime Decomposition/Examples/169 and 273

Example of Use of GCD from Prime Decomposition

The greatest common divisor of $169$ and $273$ is:

$\gcd \set {169, 273} = 13$

Proof

\(\ds 169\)

\(=\)

\(\ds 13^2\)

\(\ds 273\)

\(=\)

\(\ds 3 \times 7 \times 13\)

\(\ds \leadsto \ \ \)

\(\ds 169\)

\(=\)

\(\ds 3^0 \times 7^0 \times 13^2\)

\(\ds 273\)

\(=\)

\(\ds 3^1 \times 7^1 \times 13^1\)

\(\ds \leadsto \ \ \)

\(\ds \gcd \set {169, 273}\)

\(=\)

\(\ds 3^0 \times 7^0 \times 13^1\)

\(\ds \)

\(=\)

\(\ds 13\)

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-4}$ The Fundamental Theorem of Arithmetic: Exercise $6 \ \text{(b)}$