0
$\begingroup$

enter image description here

enter image description here

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Dr_Be
    Feb 11 '16 at 14:07
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.