LCD, LCMDate: 08/16/97 at 23:56:41 From: Sharon Brown Subject: LCD, LCM What is the easiest way to find the least common denominator and least common multiple of two numbers? Date: 08/21/97 at 17:00:30 From: Doctor Rob Subject: Re: LCD, LCM If the numbers are small, the easiest way is to factor them into prime powers. Then the greatest common denominator (GCD) has all the primes appearing in either of the factorizations raised to the lesser power between the two, and the least common denominator (LCM) is similar but using the greater power. Example: The two numbers are 180 and 54. 180 = 2^2*3^2*5^1, and 54 = 2^1*3^3*5^0. The GCD is 2^1*3^2*5^0 = 18, because the smaller of the exponents of 2 is 1, the smaller of the exponents of 3 is 2, and the smaller of the exponents of 5 is 0. The LCM is 2^2*3^3*5^1 = 540, because the larger of the exponents of 2 is 2, the larger of the exponents of 3 is 3, and the larger of the exponents of 5 is 1. If the numbers are large, so that factoring them is hard, the best way to find the GCD is using Euclid's Algorithm. From the larger one, subtract the biggest multiple of the smaller one you can without getting a negative answer. Replace the larger number with the answer you got. Repeat this until the last number computed is zero, and the GCD is the next-to-last number computed. Example: What is the GCD of 347236 and 297228? 347236 - 1*297228 = 50008 297228 - 5* 50008 = 47188 50008 - 1* 47188 = 2820 47188 - 16* 2820 = 2068 2820 - 1* 2068 = 752 2068 - 2* 752 = 564 752 - 1* 564 = 188 564 - 3* 188 = 0 The GCD is 188. Be sure to check your work by dividing to make sure that the GCD really does divide the two numbers: 347236/188 = 1847, and 297228/188 = 1581. Once you have the GCD, the LCM is the product of the two numbers divided by the GCD. Thus in the example, the LCM of 347236 and 297228 is 347236*297228/188 = 549090936. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/