LCD, LCM

Date: 08/16/97 at 23:56:41
From: Sharon Brown
Subject: LCD, LCM

What is the easiest way to find the least common denominator and least 
common multiple of two numbers?

Date: 08/21/97 at 17:00:30
From: Doctor Rob
Subject: Re: LCD, LCM

If the numbers are small, the easiest way is to factor them into 
prime powers. Then the greatest common denominator (GCD) has all the 
primes appearing in either of the factorizations raised to the lesser 
power between the two, and the least common denominator (LCM) is 
similar but using the greater power.

Example:  The two numbers are 180 and 54.  180 = 2^2*3^2*5^1, and
54 = 2^1*3^3*5^0.  The GCD is 2^1*3^2*5^0 = 18, because the smaller 
of the exponents of 2 is 1, the smaller of the exponents of 3 is 2, 
and the smaller of the exponents of 5 is 0. 

The LCM is 2^2*3^3*5^1 = 540, because the larger of the exponents 
of 2 is 2, the larger of the exponents of 3 is 3, and the larger of 
the exponents of 5 is 1.

If the numbers are large, so that factoring them is hard, the best way
to find the GCD is using Euclid's Algorithm.  From the larger one,
subtract the biggest multiple of the smaller one you can without 
getting a negative answer. Replace the larger number with the answer 
you got. Repeat this until the last number computed is zero, and the 
GCD is the next-to-last number computed.

Example:  What is the GCD of 347236 and 297228?

347236 -  1*297228 = 50008
297228 -  5* 50008 = 47188
 50008 -  1* 47188 =  2820
 47188 - 16*  2820 =  2068
  2820 -  1*  2068 =   752
  2068 -  2*   752 =   564
   752 -  1*   564 =   188
   564 -  3*   188 =     0

The GCD is 188. Be sure to check your work by dividing to make sure
that the GCD really does divide the two numbers:  347236/188 = 1847,
and 297228/188 = 1581.

Once you have the GCD, the LCM is the product of the two numbers 
divided by the GCD. Thus in the example, the LCM of 347236 and 297228 
is 347236*297228/188 = 549090936.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/