Least Common Multiple PuzzleDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/