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

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.

• You simply don't need it for 4.8.5.a but you do need it for the argument that "no integer larger than $2^{20}$" divides the two integers in question. Otherwise you cannot immediately rule out the existence of a factorization like (say) $10^{20} = 2^{30} \cdot 5^{15}$ or $6^{30} = 2^{30} \cdot 5^{20}$, and a larger factor could come into the game. Feb 11 '16 at 14:07

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$.
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}$.