# Greatest Common Factors

Quick Navigation Video Lectures Examples
In Math . . .

a is a common factor of b and c if a is a factor of both b and c. a is the greatest common factor of the two numbers if there are no common factors greater than a.

We'll write "the greatest common factor of a and b" as gcf(a, b).

In English . . .

Both phrases mean exactly what they seem to say: A number is a common factor of two other numbers if it's a factor of both of them. So, for example, 2 is a common factor of 12 and 18 but 4 isn't a common factor since it's a factor of 12 only. A little experimentation will show you that 3 and 6 are the only other factors that 12 and 18 have in common. Because 6 is the biggest of the common factors, it would be the greatest common factor of 12 and 18.

## Quick Tip - Which One Did You Find?

At this point, I think it's worth repeating that factors are always smaller than the original number and multiples are always larger.

In our previous example, finding the greatest common factor was relatively straightforward since the numbers were small. It was easy enough to write out all the factors and pick the largest common one from the two lists. For larger numbers that approach would be impractical. Here's a procedure that will let you find the greatest common factor even for large numbers.

1. Write out the prime factorizations of both numbers.
2. List all the factors that they have in common.
3. If a factor appears more than once, add it to your list the smaller number of times.
4. Multiply the numbers in your list together and the result will be the greatest common factor.

If you're comfortable working with exponents they can make the last step of the procedure a little clearer.

1. Write out the prime factorizations of both numbers using exponents.
2. List all the factors that they have in common.
3. Give each factor the smallest exponent from the two factorizations.
4. Multiply the resulting numbers together.

# Videos

### Lectures

The next step up from thinking about the factors of a single number is looking for the common factors of two or more numbers. In this lecture, we'll look at an algorithm or procedure for finding the greatest common factor of two numbers that's more efficient than just writing them all out for both numbers.

### Individual Examples

In this example, we're going to look at a basic example of how to use the prime factorization method for finding the the greatest common factor of two numbers.
In this example, we'll see a special case of the greatest common factor algorithm where the two numbers are what's called "relatively prime".
In this example, we're going to see how to extend our prime factorization algorithm to situations where want to find the greatest common factor of more than two numbers.

# Example 1

Find the greatest common factor of 12 and 18.

 1. Write the prime factorizations of each number. 18 = 2 · 3 · · 312 = 2 · 3 · 3 2. List all the factors that they have in common. 2, 3 3. Because 18 has only one 2 and 12 has only one 3, our greatest common factor will have one of each of those numbers. gcf(12, 18) = 2 · 3 = 6

# Example 3

Find the greatest common factor of 100 and 80.

We'll work this one out using the exponent method.

 1. Write the prime factorizations of each number. 100 = 22 · 5280 = 24 · 5 2. List all the factors that they have in common. 2, 5 3. The smallest exponent of the 2's in the two factorizations is 2 and the smallest exponent of the 5's is 1 so we'll add those two the numbers in our list. 22, 51 If we multiply those numbers together, we'll get our greatest common factor. gcf(12, 18) = 22 · 5 = 20

# Example 2

Find the greatest common factor of 18 and 36.

 1. Write the prime factorizations of each number. 18 = 2 · 3 · 336 = 2 · 2 · 3 · 3 2. List all the factors that they have in common. 2, 3 3. Because 18 has only one 2 our greatest common factor will have only one 2. On the other hand, both numbers have two 3's so our greatest common factor will also have two of them. gcf(18, 36) = 2 · 3 · 3 = 18

# Example 4

Find the gcf(495, 945)

Here's another method for finding the greatest common factor that's a little more visual. I'm going to start by writing out the prime factorizations with the common factors lined up.

 495 = 3 · 3 · 5 · 11 945 = 3 · 3 · 3 · 5 · 7 gcf(495, 945) = 3 · 3 · 5 gcf(495, 945) = 45

To find the greatest common factor, I just took the numbers from each column that appeared in both of the rows and multiplied them together.