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: Solve ab=gcd(a,b)*lcm(a,b)

  1. Feb 2, 2010 #1
    1. The problem statement, all variables and given/known data
    If a and b are positive integers, then ab=gcd(a,b)*lcm(a,b).


    2. Relevant equations
    I am allowed to use the following propositions which have already been proved:

    (1) If d is a common divisor of a and b, then ab/d is a common multiple of a and b.
    (2) If m is a common multiple of a and b and m divides ab, then ab/m is a common divisor of a and b.

    A hint given:
    set d=gcd(a,b) and m=lcm(a,b). Use (1) to show that ab/d>=m. Use (2) to show that ab/m<=d.


    3. The attempt at a solution
    1. Let a and b be positive integers. Suppose d=gcd(a,b) and m=lcm(a,b).
    2. By (1) ab/d is a common multiple of a and b so ab/d=aL and ab/d=bK
    3. Multiply by m gives mab/d=aLm and mab/d=bKm
    4. ab/d>=m

    I am missing a step between 2 and 3. Any suggestions?
    Thanks,
    Scott
     
  2. jcsd
  3. Feb 2, 2010 #2
    Re: ab=gcd(a,b)*lcm(a,b)

    You have shown that ab/d is in fact a common multiple. Now you need to show that it is the least common multiple of a and b. To do this, write down the definitions of gcd and lcm and apply them to the equation. You can also try for a contradiction (assume that it is not the least common multiple to contradict d=gcd)
     
  4. Feb 2, 2010 #3
    Re: ab=gcd(a,b)*lcm(a,b)

    So we know that (ab/d)|a and (ab/d)|b. Therefore because ab is being divided by the greatest common divisor, it must equal its least common multiple. Therefore ab/d>=m. Correct?

    To show that ab/m<=d we would say that because ab is being divided by its least common multiple it leaves its greatest common divisor. Therfore ab/m<=d.?
     
  5. Feb 2, 2010 #4
    Re: ab=gcd(a,b)*lcm(a,b)

    ...?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook