Relationship Between GCF and LCM

Date: 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/