# Number theory GCD relatively prime question

## Homework Statement

let m|d, n|d and gcd(m,n) = 1. show mn|d

## Homework Equations

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

## 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?

Related Calculus and Beyond Homework Help News on Phys.org
Dick
Homework Helper

## Homework Statement

let m|d, n|d and gcd(m,n) = 1. show mn|d

## Homework Equations

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

## 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?
Have you tried thinking about some of these problems in terms of the prime factorizations of m, n and d?

• PsychonautQQ
jbunniii
Homework Helper
Gold Member
d = mr
d = ns
1 = mx + ny
So far so good. These three equations are all you need. Hint for the next step: try multiplying the last equation by ##d##.

• PsychonautQQ
Have you tried thinking about some of these problems in terms of the prime factorizations of m, n and d?
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?

Dick
Homework Helper
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?
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.

• 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.