# Number theory GCD relatively prime question

1. Feb 27, 2015

### PsychonautQQ

1. The problem statement, all variables and given/known data
let m|d, n|d and gcd(m,n) = 1. show mn|d

2. Relevant equations
gcd(m,n) = d = mx + ny for x and y in integers

3. The attempt at a solution
d = mr
d = ns
1 = mx + ny
1 = (d/r)x + (d/s)y
I don't know, a bit lost, just moving stuff around and not making any real progress. Any tips?

2. Feb 27, 2015

### Dick

Have you tried thinking about some of these problems in terms of the prime factorizations of m, n and d?

3. Feb 27, 2015

### jbunniii

So far so good. These three equations are all you need. Hint for the next step: try multiplying the last equation by $d$.

4. Feb 27, 2015

### PsychonautQQ

I have not tried thinking about this way. If n|d and m|d, we know that m and n each contain at least one prime that is also in the prime factorization of d. However, this does not mean we can conclude that mn|d does it? What if the only common prime in the factorization of m, n, and d is p, that would mean mn contains p^2 which wouldn't divide d's lone p.

Am I missing something?

5. Feb 27, 2015

### Dick

The idea is that if gcd(m,n)=1 then m and n have no prime factor in common. Do you see how the proof would go from there? Proving it with jbunniii's hint is actually easier to write down. I just find it easier to think in terms of prime factors.

6. Feb 27, 2015

### PsychonautQQ

Yeah, I solved it with regards to jbunnii's hint, wish I would have seen it myself >.<. Right, gcd(m,n) = 1 so they each have a unique prime that divides d, so nm|d. Thanks man, I I appreciate ya'll being so patient with me.