Layers of Least Common MultiplesDate: 10/13/2012 at 23:08:46 From: zoe Subject: Least Common Multiple Hi! I recently learned how to find the least common multiple (LCM) of two or more numbers using "the upside-down birthday cake method." For example, if you were looking for the LCM of the numbers 14 and 18, you would draw an "L" or upside down division "house" with a long base, and put the 14 and 18 on the base. Then you put a common factor outside the "L," and underneath each of the numbers, you write the other factor. (This is much easier to show than explain; my apologies.) When you arrive at a layer where there are no more common factors (besides one), you multiply the numbers outside the "L" on the left with the numbers in the bottom-most layer. Why does this work? I'm trying to understand the why/how aspect. I know it's breaking the numbers down into common factors...? Date: 10/14/2012 at 10:36:33 From: Doctor Ian Subject: Re: Least Common Multiple Hi Zoe, I think you mean something like this; using a slightly more interesting pair of numbers, 12 18 _________________ 2' | 6 9 <- 12 = 2*6, 18 = 2*9 3' | 2' 3' <- 6 = 3*2, 9 = 3*3 ^ |________________________ Multiply the terms marked with a ' to get the LCM. Is that right? If so, maybe it's easiest to see what's going on if you think about the more normal way of doing this, which is to break both numbers into prime factors: 12 = 2 * 2 * 3 18 = 2 * 3 * 3 The least common multiple will be the one that shares all the prime factors. In this case, it's 36: These are not shared; they are the ones that end up at the _____________________ bottom in the "cake" method. | | v v 12 = 2 * 2 * 3 18 = 2 * 3 * 3 LCM = 2 * 2 * 3 * 3 ^ ^ |_______|_________________ These are shared; they are the ones that end up to the left in the "cake" method. (Do you see why collecting factors like this gives us the smallest number that can be divided by both 12 and 18? If we remove any of those prime factors, we'd be missing at least one prime factor from one of the numbers. If we add any more prime factors, we'll have a number that is larger than we need.) What you were doing was a little harder, since you have to keep identifying common factors -- but it amounts to the same thing: 12 = 2 * (2 * 3) 18 = 2 * (3 * 3) Identify the first common factor 12 = 2 * 3 * (2) 18 = 2 * 3 * (3) Identify another one 12 = (2 * 3) * (2) 18 = (2 * 3) * (3) No more common factors. The product we've pulled out contains the shared prime factors, and the remaining ones are not shared. However, pick two numbers with less obvious prime factors -- for example, 1938 3534 ___________________ 2 | 969 1767 3 | 323 589 It might be tempting to quit at this point, thinking that this is the LCM: 2 * 3 * 323 * 589 = 1,141,482 Now compare that to using the prime factor method: 1938 = 2 * 3 * 17 * 19 3534 = 2 * 3 * 19 * 31 LCM = 2 * 3 * 17 * 19 * 31 This way, it's easy to see that the LCM is actually 2 * 3 * 17 * 19 * 31 = 60,078 This is still large, but significantly smaller. So the nice thing about the prime factor method is that there's no way to quit too early. Also, it directly relates the idea of prime factors to the idea of "least common multiple," and doesn't require you to memorize a made-up method for calculating that without really understanding what you're doing. :^D Does this help? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ Date: 10/14/2012 at 11:30:05 From: zoe Subject: Thank you (Least Common Multiple) Thank you very much! I guess I understand slightly better... My only immediate thought is that in making prime factor trees (if that was the method to find the prime factors of each), couldn't one make the same mistake in prematurely believing one has enumerated all the prime factors? In short, the "danger" of stopping short still seems possible. It's so frustrating to not have the deeper understanding :( Date: 10/15/2012 at 09:56:59 From: Doctor Ian Subject: Re: Thank you (Least Common Multiple) Hi Zoe, Stopping short could happen, but if you're used to finding prime factorizations -- which is something that you do in lots of different contexts -- then it seems less likely. And you can use things like tables of primes to check whether you're down to primes or not. For finding common factors of two numbers, on the other hand, there's nothing comparable. So I think the two "dangers" are slightly different in nature. I agree it's frustrating to lack deeper understanding, and we shouldn't stop until we have it. On that note, I'm not sure what you're not understanding at this point! Do you understand why, when we have prime factorizations for two numbers, e.g., ... 12 = 2 * 2 * 3 18 = 2 * 3 * 3 ... we can collect those in different ways to find the greatest common factor (GCF) and the LCM? 12 = 2 * 2 * 3 18 = 2 * 3 * 3 GCF = 2 * 3 LCM = 2 * 2 * 3 * 3 In some sense, the "deepest" you can go here in terms of explanation is the Fundamental Theorem of Arithmetic, which says that every integer greater than 1 has exactly one prime factorization, and every prime factorization corresponds to exactly one number. Are you familiar with that? Think of prime factors as a kind of x-ray: they let you see the internal structures of numbers. For example, I could have a bunch of numbers: 51 391 731 816 These might not seem to have anything in common -- but when I look at their "x-rays," I can see that they all share one multiple in common: 51 = 3 * 17 391 = 17 * 23 731 = 17 * 43 816 = 2 * 2 * 2 * 2 * 3 * 17 Also, the same kind of reasoning that you do with prime factors, e.g., reducing fractions, ... ' ' 12 2 * 2 * 3 2 2 -- = ----------------- = ----- = -- 90 2 * 3 * 3 * 5 3 * 5 15 ' ' ... is what you do with variable expressions, e.g., ' ' ' ' ' x^4 y^3 x * x * x * x * y * y * y ------- = ----------------------------------------- x^2 y^7 x * x * y * y * y * y * y * y * y ' ' ' ' ' x * x = ------------- y * y * y * y x^2 = --- y^4 Is there anything about this that still seems mysterious to you? - Doctor Ian, The Math Forum http://mathforum.org/dr.math/ Date: 10/15/2012 at 10:49:37 From: zoe Subject: Thank you (Least Common Multiple) Yes! That did it! Thank you!! I was not familiar with the Fundamental Theorem of Arithmetic, but it clicked as soon as you compared it to an x-ray and looking at what the number is made up of! Thanks, again :) |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/