Finding Least Common Multiple by Using Prime Factors

Date: 11/05/2003 at 21:27:31
From: Jimmy
Subject: least common multiples

Can you explain how the prime factorization of a pair of numbers can
help you find the least common multiple of those numbers?

Date: 11/06/2003 at 00:38:19
From: Doctor Riz
Subject: Re: least common multiples

Hi Jimmy -

Thanks for writing.  You've asked an interesting question, so let me 
see if I can help you make sense of it.

Suppose you want to find the Least Common Multiple (LCM) of 6 and 10.
If we start by factoring them into primes, we get this:

   6: 2 * 3
  10: 2 * 5

Now the challenge is to find the smallest possible set of prime 
factors that contains all the factors of each original number.  

In other words, we need a 2 and a 3 from the 6.  So far we have 2 * 3.  
But we don't need to include another 2 from the 10 since we already 
have the 2 from the 6.  All we need to add to our set is the 5, so now 
we have 2 * 3 * 5.  As a check, can you find 2 * 3 in our set of 2 * 3
* 5?  How about 2 * 5?  Yes, both original factor sets are included
and there is nothing extra.  So, our LCM is 2 * 3 * 5 or 30.

Let's try another one.  Suppose you are looking for the LCM of 8, 10 
and 12.  Start by factoring each one out:

   8: 2 * 2 * 2
  10: 2 * 5
  12: 2 * 2 * 3

Now let's put together the smallest set that contains each of those 
three sets.  We start with three 2's from the 8.  That gives us:

  2 * 2 * 2

For the 10, we certainly don't need another 2 since we already have 
three of them, but we do need to add in a 5.  Now we have:

  2 * 2 * 2 * 5

For the 12, we don't need to do anything with the two 2's because we 
already have three of them, but we do need to toss in the 3.  Now we 
have:

  2 * 2 * 2 * 5 * 3

Again, can you find each of the three smaller factor sets within that 
bigger one?  Yes, so we're in business.  The LCM is 2 * 2 * 2 * 5 * 3
or 120.

By the way, there is one more thing that's nice about this method.  
Suppose you are using it to find the lowest common denominator (LCD)
for three fractions with denominators of 8, 10 and 12.  You go through
the same steps and wind up with 120.  

But now it's time to rename each fraction so it has a denominator of 
120.  By looking at the original factor sets versus the common one,
you can easily see what each fraction needs to be multiplied by to
turn it into a denominator of 120.

For example, since our LCD is 2 * 2 * 2 * 5 * 3 and the fraction with
a denominator of 8 already has the 2 * 2 * 2, that one needs to be 
multiplied by 3 * 5 or 15 to turn it into 120.  The 10 already has the
2 * 5, so it needs to be multiplied by 2 * 2 * 3 or 12 to make 120. 
Since the 12 already has 2 * 2 * 3, it's missing another 2 and the 5,
so it gets multiplied by 2 * 5 or 10 to turn it into 120.  You can see
how that can save a little time.

Hope that makes sense.  Here are some more comments on finding the LCM 
from our archives:

  Finding Least Common Multiple (LCM) by Factoring
    http://mathforum.org/library/drmath/view/58569.html 

Write back if you're still confused or have other questions.

- Doctor Riz, The Math Forum
  http://mathforum.org/dr.math/