How is unique factorization of integers related to computing greatest common divisors?

Question

Source: Discrete Mathematics with Applications, Susanna S. Epp.

What does the unique factorization of integers have to do with gcd $2^{10}$ of ($10^{20}, 6^{30}$) in Example 4.8.5.b? Contrary to 4.8.5.b, the author doesn't mention the unique factorization of integers in the solution of Example 4.8.5.a.

Answer 1

It's really the same method in both cases...for small numbers you can generally read off the factors without much fuss. Here they are just noting that $72=2^3\times 3^2$ and $63=3^2\times 7$.

For large numbers this can be a lot harder. Happily for your second example, the fact that the numbers are written as powers of small numbers make the factoring easy. For general large numbers this is usually a very hard problem. In those cases we can get the gcd via the Euclidean algorithm, without fully factoring the original numbers.

Answer 2

One can apply the same technique to solving (a), by writing the arguments as $$2^3 \cdot 3^2 \quad \textrm{and} \quad 3^2 \cdot 7 .$$ Then, by inspection the g.c.d. is $3^2 = 9$.

The consequence of unique factorization here divisibility by each prime is independent of divisibility by another prime. So, for each prime $p_i$, we need ask only for the largest power $p_i^{a_i}$ that divides both numbers, and then we can then conclude that the g.c.d. is $\prod_i p_i^{a_i}$.