Least Common Multiple Puzzle

Date: 03/24/2003 at 13:41:28
From: Jenny
Subject: Division

What is the smallest number divisible by 1,2,3,4,5,6,8,9,10 that is 
not 3600?

Date: 03/25/2003 at 15:47:46
From: Doctor Ian
Subject: Re: Division

Hi Jenny,

Let's look at a smaller version of the problem:

  What's the smallest number divisible by 2, 3, 4, 5, 6?

It's easy to come up with _a_ number that is divisible by all of them.
Just multiply all of them together.

  2 * 3 * 4 * 5 * 6 = 720

But is this the _smallest_ number? Well, note that if something is
divisible by 4, it must be divisible by 2 as well; so we don't really
need the 2 in our list of factors:

  3 * 4 * 5 * 6 = 360

Also, if something is divisible by 6, it must be divisible by 3 as
well; so we don't really need the 3 in our list of factors:

  4 * 5 * 6 = 120

Are we done yet?  Let's see.  We have

  (2 * 2) * 5 * (2 * 3) = 120

We could get rid of one of those 2's, 

  (2) * 5 * (2 * 3) = 60

Now it's still divisible by 2, 3, 4, 5, and 6, so I haven't given
anything up. But if I remove any other factors, I'll lose divisibility 
by at least one of those numbers. 

So 60 _is_ the smallest number that is divisible by 2, 3, 4, 5, and 6.  

Now, that was kind of a pain, wasn't it?  Is there an easier way?

Suppose we start by writing all the factors that we want to go into
our number, and breaking them into prime factors:

  2 =>  2^1
  3 =>        3^1
  4 =>  2^2
  5 =>               5^1
  6 =>  2^1   3^1

Now, the number we seek will have to look like

  __ = 2^? * 3^? * 5^?

Does that make sense?  Okay, but what exponents need to replace the
'?' marks? The highest one for each prime factor. Do you see why? 
So we can construct our number this way:

  2 =>  2^1
  3 =>        3^1
  4 =>  2^2
  5 =>               5^1
  6 =>  2^1   3^1
        -----------------
        2^2   3^1    5^1        <--- highest exponents

and our number is 

  2^2 * 3^1 * 5^1 = 60

which is what we came up with before. Only this is a lot less work. 

Now, suppose that someone says: "Okay, but what's the smallest number
like this that isn't 60?"  

Well, let's think about that. 60 is divisible by all my numbers, 
right? So if I multiply 60 by _any_ integer, the result will _still_
be divisible by all my numbers, right? That won't change anything. 

So what's the smallest integer I can do that with? Its 2. So the 
smallest number divisible by 2, 3, 4, 5, and 6, that isn't 60, is 

  2 * 60 = 120

Does this make sense? If so, then you should be able to solve your
original problem, because it's really just the same, with more 
factors.  

By the way, there is a name for the smallest number that is divisible
by a collection of numbers. It's called the Least Common Multiple, or
LCM. Usually, you see it in connection with pairs of numbers, e.g.,
the LCM of 6 and 8 is 24.  But the concept applies to collections of
any size.  

I hope this helps!

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