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
Math Forum Home || Math Library || Quick Reference || Math Forum Search