Greatest Common Factor

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.

Now consider this.

Factors of $\hspace{0.2em} 12 \hspace{0.2em}$ - $\hspace{0.2em} {\color{Red} 1} \hspace{0.2em}$, $\hspace{0.2em} {\color{Red} 2} \hspace{0.2em}$, $\hspace{0.2em} {\color{Red} 3} \hspace{0.2em}$, $\hspace{0.2em} 4 \hspace{0.2em}$, $\hspace{0.2em} {\color{Red} 6} \hspace{0.2em}$, and $\hspace{0.2em} 12 \hspace{0.2em}$

Factors of $\hspace{0.2em} 18 \hspace{0.2em}$ - $\hspace{0.2em} {\color{Red} 1} \hspace{0.2em}$, $\hspace{0.2em} {\color{Red} 2} \hspace{0.2em}$, $\hspace{0.2em} {\color{Red} 3} \hspace{0.2em}$, $\hspace{0.2em} {\color{Red} 6} \hspace{0.2em}$, $\hspace{0.2em} 9 \hspace{0.2em}$, and $\hspace{0.2em} 18 \hspace{0.2em}$

And because $\hspace{0.2em} 6 \hspace{0.2em}$ is the largest of those common factors, it is the greatest common factor of $\hspace{0.2em} 12 \hspace{0.2em}$ and $\hspace{0.2em} 18 \hspace{0.2em}$.

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

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. $\hspace{0.2em} 12 \hspace{0.2em}$ is the GCF.

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.

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, $\hspace{0.2em} 2 \hspace{0.2em}$ is a common factor and if we divide the numbers by $\hspace{0.2em} 2 \hspace{0.2em}$, we get $\hspace{0.2em} 18 \hspace{0.2em}$, $\hspace{0.2em} 27 \hspace{0.2em}$, and $\hspace{0.2em} 36 \hspace{0.2em}$.

Step 3.  Repeat step $\hspace{0.2em} 2 \hspace{0.2em}$ with the new row. Keep repeating as long as you can find common factors for the numbers in the row.

Now, $\hspace{0.2em} 2 \hspace{0.2em}$, $\hspace{0.2em} 3 \hspace{0.2em}$, and $\hspace{0.2em} 4 \hspace{0.2em}$ 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.

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.

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.

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.

Solution

Here, the smallest number is $\hspace{0.2em} 16 \hspace{0.2em}$. So we go over its factors one by one (from the top) and check if the factor also divides into $\hspace{0.2em} 20 \hspace{0.2em}$ and $\hspace{0.2em} 28 \hspace{0.2em}$ evenly.

And $\hspace{0.2em} 4 \hspace{0.2em}$ is the first factor to pass the test. So, $\hspace{0.2em} 4 \hspace{0.2em}$ 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.

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 $\hspace{0.2em} 0 \hspace{0.2em}$, the divisor is the GCF of the two numbers (those you picked in step $\hspace{0.2em} 1 \hspace{0.2em}$).

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 $\hspace{0.2em} 18 \hspace{0.2em}$ and $\hspace{0.2em} 48 \hspace{0.2em}$, and $\hspace{0.2em} 6 \hspace{0.2em}$ is the divisor that leaves no remainder. So, $\hspace{0.2em} 6 \hspace{0.2em}$ is the GCF of $\hspace{0.2em} 18 \hspace{0.2em}$ and $\hspace{0.2em} 48 \hspace{0.2em}$.

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 $\hspace{0.2em} 2 \hspace{0.2em}$ with the next of the given numbers.

Here, we have $\hspace{0.2em} 6 \hspace{0.2em}$ (GCF from above) and $\hspace{0.2em} 57 \hspace{0.2em}$ (the next and the only remaining number).

Keep repeating steps $\hspace{0.2em} 2 \hspace{0.2em}$ and $\hspace{0.2em} 3 \hspace{0.2em}$ 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, $\hspace{0.2em} 3 \hspace{0.2em}$ is the GCF of $\hspace{0.2em} 18 \hspace{0.2em}$, $\hspace{0.2em} 48 \hspace{0.2em}$, and $\hspace{0.2em} 57 \hspace{0.2em}$.

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.

Footnotes