Relationship Between GCF and LCMDate: 05/22/2002 at 15:11:18 From: Drew Hayes Subject: gcf and lcm What is the exact relationship between the gcf or gcd and the lcm of two numbers? Drew Hayes Date: 05/22/2002 at 15:15:02 From: Doctor Paul Subject: Re: gcf and lcm To compute lcm(a,b) and gcd(a,b), first consider the prime factorization of a and b: a = p_1^a_1 * p_2^a_2 * ... * p_L^a_L b = p_1^b_1 * p_2^b_2 * ... * p_L^b_L Note that some of the exponents may be zero if one of the prime factors occurs in only one of a or b. Then gcd(a,b) = Product [p_i^(min(a_i,b_i))] i=1,L So if a = 24 = 2^3 * 3 and if b = 15 = 3 * 5 then write a = 2^3 * 3^1 * 5^0 b = 2^0 * 3^1 * 5^1 gcd(a,b) = 2^0 * 3*1 * 5^0 = 3 taking the minimum of the two exponents each time. Similarly, lcm(a,b) = Product [p_i^(max(a_i,b_i))] i=1,L In our example, a = 2^3 * 3^1 * 5^0 b = 2^0 * 3^1 * 5^1 lcm(a,b) = 2^3 * 3^1 * 5*1 = 15 * 8 = 120 I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum 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/