# 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