1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory GCD relatively prime question

  1. Feb 27, 2015 #1
    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. jcsd
  3. Feb 27, 2015 #2


    User Avatar
    Science Advisor
    Homework Helper

    Have you tried thinking about some of these problems in terms of the prime factorizations of m, n and d?
  4. Feb 27, 2015 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    So far so good. These three equations are all you need. Hint for the next step: try multiplying the last equation by ##d##.
  5. Feb 27, 2015 #4
    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?
  6. Feb 27, 2015 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
  7. Feb 27, 2015 #6
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted