Question?

InTeReStInG

The solution for this problem is confusing,
"If we have a certain prime that is a factor of two numbers, n and m, and supposing the number n contains "fewer" of this prime in its factorization, then the greatest common divisor cannot have any more of this prime than are in n, or else it wouldn't divide n. The answer is then choice i.)" Especially the part in bold.

quacker88

@neatlobster Hope this makes more sense:

Let's call the prime \(p\). Since \(p\) is a factor of both \(m\) and \(n\), I'm going to write \(m\) and \(n\) as following:

\(m = p^a \cdot \text{something} \)
\(n = p^b \cdot \text{something} \)

This means that \(p\) divides into \(m\) \(a\) times, and \(p\) divides into \(n\) \(b\) times.

Now, let's look at \(\gcd(m,n)\). The \(\gcd\) must be factors of both \(m\) and \(n\), which means that the \(\gcd\) must be able to divide into both \(m\) and \(n\).

If \(a<b\), this means that the \(\gcd\) cannot contain more than \(p^a\) in its factorization, because if it had any more \(p\) than \(p^a\), it would no longer be able to divide into \(m\).

Likewise, If \(b<a\), this means that the \(\gcd\) cannot contain more than \(p^b\) in its factorization, because if it had any more \(p\) than \(p^b\), it would no longer be able to divide into \(n\).

Hence, whichever of \(m\) and \(n\) has the less amount of \(p\), the \(\gcd\) can only have that much \(p\).

I know this is a lot, let me know if you have any more questions. Hope this helps!

debbie

@quacker88 Thank you