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
_____________________________________________

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/ 
Associated Topics:
College Number Theory
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/