Proof Regarding LCMDate: 12/05/2001 at 20:49:28 From: James kingsbery Subject: Proof regarding LCM Independently of other sources I came up with the idea that given integers a and b, a*b = GCF(a,b) * LCM(a,b). I have searched the Internet and have found a couple of sources, including this site, that confirm my idea, but I cannot flesh out a proof, nor have I been able to find one. Is there a proof of this equation? Thanks! Date: 12/06/2001 at 10:11:10 From: Doctor Paul Subject: Re: Proof regarding LCM First we need to notice a preliminary fact about lcm(a,b) and gcd(a,b). 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 Notice that in general two numbers won't have the same number of primes in their prime factorization. So what we're going to do is allow some of the exponents to be zero to ensure that each number is written as the product of L prime powers. An example (below) will make this more clear. Then gcd(a,b) = the product (big Pi symbol), i = 1..L, of p_i^(min{a_i,b_i}) 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 (notice I take the minimum of the two exponents each time) Similarly, lcm(a,b) = the product (big Pi symbol), i = 1..L, of p_i^ (max{a_i,b_i}) In our example, a = 2^3 * 3^1 * 5^0 b = 2^0 * 3^1 * 5^1 so lcm(a,b) = 2^3 * 3^1 * 5*1 = 15 * 8 = 120 Now we can prove the statement: Recall we had 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 Then: lcm(a,b) * gcd(a,b) = Product, i = 1..L, of p_i^(min{a_i,b_i}) * p_i^(max{a_i,b_i}) which is equal to: Product, i = 1..L, of p_i^[(min{a_i,b_i}) + (max{a_i,b_i})] Now notice that min{m,n} + max{m,n} = m+n (can you verify this?) for all real numbers m and n. So we can write the above product as: Product, i = 1..L, of p_i^(a_i + b_i) which is equal to: Product, i = 1..L, of p_i^a_i * p_i^b_i which is equal to ab. So we have established that fact that lcm(a,b) * gcd(a,b) = ab 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- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/