LCM and GCF, Combined: Why and HowDate: 12/20/2010 at 15:09:54 From: Michelle Subject: Method for finding LCM and GCF all at once On 03/02/2006, Doctor Peterson answered a question about a method for finding the least common multiple (LCM) and greatest common factor (GCF) at the same time. Basically, you keep taking common factors out until there is nothing else in common. The product of the GCF column ends up being the GCF, and the GCF multiplied by uncommon factors is the LCM. I understand how to use this method but I am still confused as to why the method works for LCM -- it seems like magic instead of math -- and why it does not work when comparing three numbers. I have been trying to come up with my own method for triples, but I have been unsuccessful. Please help soon. I mainly need a good way to explain why the method works. Here's an example with two numbers: GCF / 12 / 20 4 / 3 / 5 According to the method, GCF = 4 LCM = 4 * 3 * 5 = 60 Here's an example with three numbers: GCF / 10 / 4 / 20 2 / 5 / 2 / 10 So, GCF = 2 LCM = 2 * 5 * 2 * 10 = 200 But the LCM for those three numbers is actually 40. How do I fix this? And why does it work for two numbers in the first place? Date: 12/20/2010 at 23:37:26 From: Doctor Peterson Subject: Re: Method for finding LCM and GCF all at once Hi, Michelle. You're talking about One Approach to Finding LCM and GCF at the Same Time http://mathforum.org/library/drmath/view/70339.html I DID explain how the LCM works there; but there are other ways to say it. Let's write the numbers as products of (powers of) primes to see more clearly what is happening. I'll do it in two steps rather than one, to make it somewhat more typical: | 4*3 | 4*5 --+-----+----- 2 | 2*3 | 2*5 2 | 3 | 5 The GCF is the product of the numbers on the left (the divisors), because 12 is 2*2*3 (the GCF times what's left over), and likewise 20 is 2*2*5. Now, how do we find the LCM? We can start with the GCF and multiply by whatever else we need to get each number. In each case, we need to multiply by that left-over number at the bottom of the column. Starting with 4, we have to multiply by 3 to get a multiple of 12; and by 5 to get a multiple of 20. So the smallest possible multiple of both is made by multiplying the GCF by BOTH 3 and 5: 2*2*3*5. In general, two numbers a and b can each be written as multiples of their GCF (say d), so that a = dx and b = dy. Then the product of the factors on the left will be d, and the numbers on the bottom will be x and y. The LCM is dxy, since this is a multiple of both dx and dy, and no smaller multiple will work. | dx | dy --+----+---- d | x | y GCF = d, LCM = dxy I've since learned a way to do this for more than two numbers. All we do is continue dividing after we have run out of common divisors, using factors of some, rather than all, of the numbers. Here is the work for the example I tried on that 2006 conversation that you referenced: | 54 | 90 | 70 --+----+----+---- 2 | 27 | 45 | 35 <-- 2 divides ALL the numbers --+----+----+---- 9 | 3 | 5 | 35 <-- 9 divides TWO of the numbers 5 | 3 | 1 | 7 <-- 5 divides TWO of the numbers Once we are down to only distinct primes in the bottom of the columns -- or, at least, the numbers are pairwise relatively prime -- we have both the GCF (2), from the top part of the left column; and the LCM (2*9*5*3*1*7 = 1890), from the entire left and bottom. For comparison, the usual method gives 54 = 2^1*3^3 90 = 2^1*3^2*5^1 70 = 2^1 *5^1*7^1 -------------------- GCF = 2^1 = 2 LCM = 2^1*3^3*5^1*7^1 = 1890 If you have any further questions, feel free to write back. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/