Associated Topics || Dr. Math Home || Search Dr. Math

Layers of Least Common Multiples

```Date: 10/13/2012 at 23:08:46
From: zoe
Subject: Least Common Multiple

Hi!

I recently learned how to find the least common multiple (LCM) of two or
more numbers using "the upside-down birthday cake method."

For example, if you were looking for the LCM of the numbers 14 and 18, you
would draw an "L" or upside down division "house" with a long base, and
put the 14 and 18 on the base. Then you put a common factor outside the
"L," and underneath each of the numbers, you write the other factor. (This
is much easier to show than explain; my apologies.) When you arrive at a
layer where there are no more common factors (besides one), you multiply
the numbers outside the "L" on the left with the numbers in the
bottom-most layer.

Why does this work? I'm trying to understand the why/how aspect.

I know it's breaking the numbers down into common factors...?

```

```
Date: 10/14/2012 at 10:36:33
From: Doctor Ian
Subject: Re: Least Common Multiple

Hi Zoe,

I think you mean something like this; using a slightly more interesting
pair of numbers,

12     18
_________________
2' |    6      9           <- 12 = 2*6,  18 = 2*9
3' |    2'     3'          <-  6 = 3*2,   9 = 3*3
^
|________________________  Multiply the terms marked with a '
to get the LCM.

Is that right?

If so, maybe it's easiest to see what's going on if you think about the
more normal way of doing this, which is to break both numbers into prime
factors:

12 = 2 * 2 * 3
18 = 2     * 3 * 3

The least common multiple will be the one that shares all the prime
factors. In this case, it's 36:

These are not shared; they are
the ones that end up at the
_____________________ bottom in the "cake" method.
|       |
v       v
12  = 2 * 2 * 3
18  = 2     * 3 * 3
LCM = 2 * 2 * 3 * 3
^       ^
|_______|_________________ These are shared; they are
the ones that end up to the
left in the "cake" method.

(Do you see why collecting factors like this gives us the smallest number
that can be divided by both 12 and 18? If we remove any of those prime
factors, we'd be missing at least one prime factor from one of the
numbers. If we add any more prime factors, we'll have a number that is
larger than we need.)

What you were doing was a little harder, since you have to keep
identifying common factors -- but it amounts to the same thing:

12 = 2 * (2 * 3)
18 = 2 * (3 * 3)           Identify the first common factor

12 = 2 * 3 * (2)
18 = 2 * 3 * (3)           Identify another one

12 = (2 * 3) * (2)
18 = (2 * 3) * (3)         No more common factors.
The product we've pulled out
contains the shared prime factors,
and the remaining ones are not
shared.

However, pick two numbers with less obvious prime factors -- for example,

1938    3534
___________________
2 |    969    1767
3 |    323     589

It might be tempting to quit at this point, thinking that this is
the LCM:

2 * 3 * 323 * 589 = 1,141,482

Now compare that to using the prime factor method:

1938 = 2 * 3 * 17 * 19
3534 = 2 * 3      * 19 * 31
LCM  = 2 * 3 * 17 * 19 * 31

This way, it's easy to see that the LCM is actually

2 * 3 * 17 * 19 * 31 = 60,078

This is still large, but significantly smaller.

So the nice thing about the prime factor method is that there's no way to
quit too early. Also, it directly relates the idea of prime factors to the
idea of "least common multiple," and doesn't require you to memorize a
made-up method for calculating that without really understanding what
you're doing.  :^D

Does this help?

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 10/14/2012 at 11:30:05
From: zoe
Subject: Thank you (Least Common Multiple)

Thank you very much!

I guess I understand slightly better... My only immediate thought is that
in making prime factor trees (if that was the method to find the prime
factors of each), couldn't one make the same mistake in prematurely
believing one has enumerated all the prime factors? In short, the "danger"
of stopping short still seems possible.

It's so frustrating to not have the deeper understanding :(

```

```
Date: 10/15/2012 at 09:56:59
From: Doctor Ian
Subject: Re: Thank you (Least Common Multiple)

Hi Zoe,

Stopping short could happen, but if you're used to finding prime
factorizations -- which is something that you do in lots of different
contexts -- then it seems less likely. And you can use things like tables
of primes to check whether you're down to primes or not. For finding
common factors of two numbers, on the other hand, there's nothing
comparable. So I think the two "dangers" are slightly different in nature.

I agree it's frustrating to lack deeper understanding, and we shouldn't
stop until we have it. On that note, I'm not sure what you're not
understanding at this point! Do you understand why, when we have prime
factorizations for two numbers, e.g., ...

12 = 2 * 2 * 3
18 =     2 * 3 * 3

... we can collect those in different ways to find the greatest common
factor (GCF) and the LCM?

12 = 2 * 2 * 3
18 =     2 * 3 * 3

GCF =     2 * 3

LCM = 2 * 2 * 3 * 3

In some sense, the "deepest" you can go here in terms of explanation is
the Fundamental Theorem of Arithmetic, which says that every integer
greater than 1 has exactly one prime factorization, and every prime
factorization corresponds to exactly one number. Are you familiar with
that?

Think of prime factors as a kind of x-ray: they let you see the internal
structures of numbers. For example, I could have a bunch of numbers:

51
391
731
816

These might not seem to have anything in common -- but when I look at
their "x-rays," I can see that they all share one multiple in common:

51 =                 3 * 17
391 =                     17 * 23
731 =                     17      * 43
816 = 2 * 2 * 2 * 2 * 3 * 17

Also, the same kind of reasoning that you do with prime factors, e.g.,
reducing fractions, ...

'   '
12   2 * 2 * 3             2      2
-- = ----------------- = ----- = --
90       2 * 3 * 3 * 5   3 * 5   15
'   '
... is what you do with variable expressions, e.g.,

'   '   '   '   '
x^4 y^3   x * x * x * x * y * y * y
------- = -----------------------------------------
x^2 y^7           x * x * y * y * y * y * y * y * y
'   '   '   '   '

x * x
= -------------
y * y * y * y

x^2
= ---
y^4

- Doctor Ian, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 10/15/2012 at 10:49:37
From: zoe
Subject: Thank you (Least Common Multiple)

Yes! That did it! Thank you!!

I was not familiar with the Fundamental Theorem of Arithmetic, but it
clicked as soon as you compared it to an x-ray and looking at what the

Thanks, again :)
```
Associated Topics:
Middle School Factoring Numbers

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