The Greatest Common Factor
Before we look at what is meant by the Greatest Common Factor (GCF), we must first understand what a factor is.
Factors of a number are integers that divide into the number evenly (leave no remainder). For example, 3 is a factor of 6. Or 5 is a factor of 20.
Now consider this.
Factors of 12 - 1, 2, 3, 4, 6, and 12
Factors of 18 - 1, 2, 3, 6, 9, and 18
And because 6 is the largest of those common factors, it is the greatest common factor of 12 and 18.
The greatest common factor (or GCF) of a group of numbers is the largest number that divides into each of them evenly. In other words, the GCF is the greatest of their common factors.
Note – GCF is also widely known as the highest common factor (HCF) or the greatest common divisor (GCD).
How to Find the Greatest Common Factor?
Now let's look at the different methods you can use to find the greatest common factor.
Prime Factorization Method
Example
Find the GCF of 36, 60, and 72.
Solution
Step 1. Do the prime factorization of each number – split the numbers into their prime factors.
Step 2. Highlight the common factors – treating each repetition of a factor as unique.
Step 3. Multiply the common factors together to get the greatest common factor.
That's it. 12 is the GCF.
Example
Find the GCF of 30, 75, and 105.
Solution
Just like we did in the previous example, we do the prime factorization of the numbers and highlight the common factors.
And then, multiply the common factors to get the GCF.
Ladder Method
This might well be the most popular method of finding the GCF.
Example
Find the GCF of 36, 54, and 72.
Solution
Step 1. Write the numbers in a row and draw an L-shape around them.
Step 2. Try to find a number that can divide evenly into each of the numbers – a common factor. Write it on the left of the L. Then divide the numbers and write the quotients under them.
Here, 2 is a common factor and if we divide the numbers by 2, we get 18, 27, and 36.
Step 3. Repeat step 2 with the new row. Keep repeating as long as you can find common factors for the numbers in the row.
Now, 2, 3, and 4 have no common factors. So, go to the next step.
Step 4. Multiply together the numbers on the left (the factors). The product is the greatest common factor.
GCF=2×3×3=18
Example
Find the GCF of 12, 36, and 60.
Solution
Using the same steps from the previous example, we first make the common factor ladder for the given numbers.
And now we multiply the factors on the left to get the GCF.
GCF=2×2×3=12
Mental Method
I love this method and it is the one I use the most. It's simple and quick, and you can do it without having to use a pen or paper. But yes, it requires you to be comfortable working with numbers in your head.
Here are the steps involved.
Example
Find the GCF of 15, 21, and 30.
Solution
Step 1. Take the smallest of the given numbers. In this example, it is 15.
Step 2. Go through the factors of 15, one by one and starting with the largest. Check if the factor divides evenly into the other numbers – 21 and 30 – as well.
Step 3. The first factor to pass this test would be the required GCF. So, 3 is the GCF of 15, 21, and 30.
Example
Find the GCF of 16, 20, and 28.
Solution
Here, the smallest number is 16. So we go over its factors one by one (from the top) and check if the factor also divides into 20 and 28 evenly.
And 4 is the first factor to pass the test. So, 4 is the GCF of the three numbers.
Euclid’s Division Algorithm
Although not commonly used in classrooms, Euclid's Division Algorithm is an interesting way of finding the HCF (and very efficient for computers!).
Let's see how it works.
Example
Find the GCF of 18, 48, and 57.
Solution
Step 1. Pick the two smallest numbers. (You can pick any two but picking the smallest would be simplest, generally).
Step 2. Divide the larger of the two numbers by the smaller one and get the remainder.
If the remainder is 0, the divisor is the GCF of the two numbers (those you picked in step 1).
If not, the remainder becomes the new divisor and the previous divisor becomes the new dividend. Repeat until you get a zero remainder.
Here, we started with 18 and 48, and 6 is the divisor that leaves no remainder. So, 6 is the GCF of 18 and 48.
But our job is not done yet. We are yet to consider the third number.
Step 3. Take the GCF obtained above and repeat step 2 with the next of the given numbers.
Here, we have 6 (GCF from above) and 57 (the next and the only remaining number).
Keep repeating steps 2 and 3 until you have taken care of all the numbers on the given list. In this example, we have no more numbers left, so we can move to the next step.
Step 4. When you have gone through all the numbers, the last divisor is the GCF.
So here, 3 is the GCF of 18, 48, and 57.
And that brings us to the end of this tutorial on what the greatest common factor is and how to find it. Until next time.
Although factors can be both positive and negative, we consider only the positive factors when talking about the Greatest Common Factor. So, for this tutorial, we use “factors” to mean positive factors only.