Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proof Regarding LCM


Date: 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/   
    
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/