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: 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