• ### Unit 2: GCF and LCM

Photo from Wikipedia

Your aunt has an excellent recipe for a breakfast sandwich that her customers love, but the cafe is all out of eggs and buns. She needs you to run to the grocery store for supplies. Exactly one egg and one bun are required to make each sandwich. Unfortunately, you can only purchase eggs in packages of 12 and buns in packages of eight. If you return with one dozen eggs and one eight-package of buns, four eggs will go unused. If you return with one dozen eggs and two packages of buns, four buns will be left over. What is the smallest number of eggs and buns you can purchase so there are no leftovers of eggs or buns? (Feel free to take out a sheet of paper and work the numbers! It will not take long to see that the answer is 24).

In this brief unit, we explore the concepts of least common multiple (LCM) and greatest common factor (GCF). Our run-of-the-mill questions, such as our egg-and-bun problem, indicate how these concepts are relevant to our everyday lives, but they also show up in lots of other mathematical questions. Here we are talking about sets of whole numbers: in Unit 1, our operations applied to whole numbers, fractions, and every other type of real number. Consequently, notions of least common multiple and greatest common factor belong to the part of mathematics that studies patterns among whole numbers, an area called number theory.

Completing this unit should take you approximately 1 hour.

• ### 2.1: Greatest Common Factor

Before we discuss great or common factors, let's use an example to help define what a factor is all by itself. Take the number 12. We can write $12=3\times 4$, which shows that three divides into 12 with zero remainder (and that four divides into 12 too). We then say that three is a factor of 12 (and that four is a factor of 12 too). We can also write $12=2\times 6$, so two and six are also factors of 12. We can also write $12=(-3)\times (-4)$ so $-3$ and $-4$ are also factors of 12. In fact, all together, we have:

The (positive) factors of 12 are $\pm1, \pm2, \pm3, \pm4, \pm6$, and $\pm 12$

More generally, an integer $n$ is a factor of a number $m$ means that $n\times (another\:integer)=m$. Some numbers have lots of factors, while others are special because they have just a few factors. For example, the only (positive) factors of the number 11 are one and itself. We call a number that has exactly two factors, such as 11, a prime number.

The greatest common factor (GCF) for a collection of whole numbers is the largest positive integer that divides into every number in the collection. Note that when we say divides into, we mean with zero remainder.

For example, let's consider the numbers 12 and eight. We can divide both of those numbers by two: $\frac{12}{2}=6$ and $\frac{8}{2}=4$. But, we can also divide both of those numbers by four: $\frac{12}{4}=3$ and $\frac{8}{4}=2$. We cannot divide both numbers by any other factor. Therefore, the GCF for these numbers is four.

We can also see the fact that GCF(12, 8) = 4 by writing out all of the (positive) factors of each and noting the largest one that they share:

 Number Positive Factors 12 1 2 3 4 12 8 1 2 4 8

Here's another example. Consider the numbers 50, 75, and 100. Can you work out that GCF(50, 75, 100) = 25?

• ### 2.2: Least Common Multiple

Multiples and factors are related concepts. Instead of saying three is a factor of 12, we could write 12 is a multiple of 3. In general, we say that one number $m$ is a multiple of another number $n$ when $m = n \times$ (another integer).

We can arrange the (positive) multiples of three, for example, in a list like this one:

$3=3\times 1$

$6=3\times 2$

$9=3\times 3$

$12=3\times 4$

Note that this list should continue on forever since there are infinitely many multiples of three. You might be familiar with the concept of multiples using a different name, counting by. Counting by threes is simply listing the consecutive multiples of three. Every number will have infinitely many multiples, and sometimes different numbers have overlapping or common multiples. For example, the first four multiples of two are two, four, six, and eight. We can see that six is both a multiple of two and a multiple of three.

The least common multiple (LCM) of a collection of numbers is the smallest (or least) multiple shared by every number in the collection. In the above example, the least common multiple of three and two is six. In other words: LCM(3, 2) = 6.

We can also compute the least common multiples in a table like we did for GCFs, only this time, we write out a few of the multiples of our numbers rather than all of their factors.

For example, let's explore the LCM(12, 8).

 Positive Multiples Number 1 2 3 4 5 6 ... 12 12 24 36 48 60 72 ... 8 8 16 24 32 40 48 ...

We can extend the entries in the table indefinitely since there are an infinite number of (positive) multiples. However, since we are only interested in the least or smallest one, we can stop entering values in the table as soon as we find a common value.

Our table goes on a bit longer than we need to and shows that 48 is a common multiple of 12 and 8. It also shows a smaller common multiple: 24, which is the least common multiple of 12 and 8. This is the answer to our egg-and-buns question from the beginning of this unit: you need to purchase two dozen eggs and three packages of buns.