Associated Topics || Dr. Math Home || Search Dr. Math

### 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
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/
```
Associated Topics:
Middle School Exponents
Middle School Fractions

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search