Home » Math Theory » Factors » Highest Common Factor (HCF)

# Highest Common Factor (HCF)

First things first, let us clear some terminologies before we discuss what Highest Common Factor is.

1. Factor VS Divisor

To see their differences, let’s take a look at the illustrations below.

In the first image, we can see that the divisor (4) can divide the dividend (6), but there is a remainder. Hence, a divisor is any number that can divide the dividend with the possibility of having a remainder.

However, by looking at the second image, 2 (divisor) can divide 6 (dividend) exactly. And as we all know, 2 is a factor of 6. Therefore, a factor is a kind of divisor that can divide the dividend exactly or without remainder.

1. Factor VS Multiple

These terms are commonly interchanged, but they are not the same. Let us examine the table of multiples of 5 below to know why.

From the table of multiples of 5, we can see that factors are numbers being multiplied to get a product. While multiples are products obtained by multiplying factors. Multiples can also be calculated when you skip count with a number.

To exercise your mind with these terms, let us have this activity first.

1. Which of the following are the divisors or 10?

1

2

9

Answer: All of them. You can use all those numbers to divide 10. As for 1 and 2, you can divide 10 and get exact quotients, while you can still have a remainder when you use 9 as the divisor.

1. Which of the following is/are the factor(s) of 10?

5

10

10 = 10 x 1

10 = 5 x 2

1. Which of the following is/are the multiple(s) of 10?

5

10

15

20

Answer: 10 and 20; Remember, multiples are products, not factors. Furthermore, multiples of a number should start from itself, so any number that is lower from it is not considered as its multiple.

10 = 10 x 1

20 = 10 x 2

In a nutshell, a divisor includes all numbers that can divide a number either with a remainder or not. Since a factor is used to multiply a certain number, it can also divide that number evenly or without remainder. Moreover, multiples is a series of products obtained from multiplying factors, which one from each set of factors is the same number.

## Definition of Highest Common Factor

The Highest Common Factor or HCF (also known as the Greatest Common Factor or GCF) is the highest factor that two or more numbers share or have in common. It has a notation of HCF (a, b) = n, where a and b are the numbers that have HCF and n as their HCF. There are different methods to obtain the HCF of two or more numbers. Yes, in many cases, you need to get the HCF of two or more numbers to solve a problem. But do not worry because we are going to stick with the basics first to set the foundation and discuss later the quick ways to find the HCF of certain numbers.

## Methods of Obtaining the Highest Common Factor or HCF

### Method 1: Listing Method

This method is applicable for finding the Highest Common Factor of small numbers. We can do it by listing the factors of each number to find the greatest among them.

Example 1:

HCF {4, 10) = ?

4 = {1, 2, 4}

10 = {1, 2, 5, 10}

We can see from the lists of the factors that they share the same factor of 2. Since it is the only factor, this is the Highest Common Factor by default.

4 = {1, 2, 4}

10 = {1, 2, 5, 10}

HCF (4, 10) = 2

Example 2:

HCF (16, 18) = ?

9 = {1, 3, 9}

18 = {1, 2, 3, 6, 9, 18}

9 and 18 have common factors of 3 and 9. However, 9 is higher than 3. This means that is 9 their Highest Common Factor.

9 = {1, 3, 9}

18 = {1, 2, 3, 6, 9, 18}

HCF (9, 18) = 9

Example 3:

HCF (11, 25) = ?

11 = {1, 11}

25 = {1, 5, 25}

HCF (11, 25) = 1

### Method 2: Prime Factorization Using Factor Tree and Tabular Division

From the word itself, Prime Factorization is a method of getting the factors of a number that are prime numbers. Whether we are using Factor Tree or Tabular Division, our goal is to end up with prime factors, multiply them and declare it as the HCF. The first five prime numbers are 2, 3, 5, 7, and 11.

Note:
1 is not a prime number because by definition, a prime number must have 1 and the number itself (which must be a different number from 1) as factors.

But in the case of 1, the factors of it are 1 and 1 as well. Unlike the smallest prime number, 2, which has factors of 1 and 2 (which is a different number from 1).

For this reason, we are only going to stop splitting the factors until the last factors listed in the factor tree are prime numbers.

Example 1: Using a Factor Tree

15 and 18

To get the prime factors of 15 and 18 let us start with making a factor tree for each one of them to break down their factors.

Then, we can translate the factor trees into equations by only getting the prime factors. This means that for 18, we must not include 9, because it is already split by 3 3.

15 = 3 × 5

18 = 2 3 3

Lastly, we can see that 3 is the only factor that 15 and 18 have in common.

15 = 3 × 5

18 = 2 3 3

This means that 3 is the Highest Common Factor of 15 and 18 or HCF (15, 18) = 3.

Example 2: Using a Table

Let us use 15 and 18 again to see the difference of this method from the Factor Tree method. For the Table Method, we need to make a table with two columns putting the number to be factored on the top right.

Then, write the lowest prime factor of 15 on the top left. Here, we have 3.

Then, divide 15 by 3, and write the quotient below 15.

Repeat the process by writing the lowest prime factor of 5 on the left- hand side and calculating their quotient.

Now that we had reached 1, we ran out of prime factors. This means that we can end now the process. We may now translate it into an equation by collecting the prime factors in the first column of the table.

15 = 3 × 5

Let us do the same process for 18.

Then, equate 18 to its prime factors.

18 = 3 x 2 x 3

Going back, here are the prime factors of 15 and 18.

15 = 3 × 5

18 = 3 x 2 x 3

We can also notice here that since 3 is their only common factor, it is also  their Highest Common Factor.

15 = 3 × 5

18 = 3 2 3

HCF (15, 18) = 3

This way of Prime Factorization is more efficient in finding the HCF of large numbers. Let us see the proof in the next example.

Example 3:

HCF (120, 300) = ?

Since 120 and 300 are both even numbers, we can set 2 as their lowest prime factors. So, let us start with dividing both of them by 2, and repeat the process until reaching the quotient of 1.

Now, we can equate each one of them to their prime factors.

120 = 2 x 2 × 2 x 3 x 5

300 = 2 x 2 x 3 x 5 x 5

Note that their common factors are more than one: 2, 3, and 5. For these cases, we must not declare the greatest among them as the Highest Common Factor. So, we cannot declare 5 as the HCF of 120 and 300. Instead, we are going to collect the identical numbers that are opposite from the equations and the remaining common factor.

120 = 2 x 2 × 2 x 3 x 5

300 = 2 x 2 x 3 x 5 x 5

HCF (120, 300) = 2 x 2 x 5 x 3

HCF (120, 300) = 60

### Method 3: Continuous Division

We can also do the Tabular Method by dividing both numbers in the same table. This method is well known as the Continuous Division, a technique that is useful if the pair are multiples of or divisible by the same number.

First, let us have a recap of the first five prime numbers:

2, 3, 5, 7, 11

Since those are the first five, they are also the lowest prime numbers, numbers that we can use as divisors for the pair of numbers. The similarity from the previous method is that we divide each number by their lowest prime factor, but for Continuous Division Method we are going to divide both numbers by their common prime factor.

Let us use 120 and 300 again using the Continuous Division Method.

First, write the three columns putting 120 and 300 to the last two cells on top.

Then, divide the numbers by the prime factor that is also divisible by them. 120 and 300 are both divisible by 2 (prime number), so we are going to use 2 as the first divisor.

Next, write their quotients below their respective dividends. Since 60 and 150 are both even numbers, we can still divide them by 2.

Repeat the process until we ran out of numbers to be divided by the same prime number.

Since 2 and 5 cannot be divided by any same prime number, we may now stop the process.

Then, we are going to multiply all the prime factors we got in the first column.

HCF (120, 300) = 2 x 2 x 3 × 5

HCF (120, 300) = 60

Note: We can also use this method as a shortcut to find the HCF of small numbers. Let us use 15 and 18 again as an example.

15 and 18 have the lowest prime factor of 3. So, we are going to use 3 as the divisor.

Then, calculate their quotients and put them below their respective dividends.

At this point, we can now stop the process because 5 and 6 cannot be divided by the same prime factor. Also, we are left only with one prime factor of 3. This means that 3 is the HCF of 15 and 18.

If we are given pairs of numbers that are multiples of or divisible by the same number, Continuous Division is the best strategy to quickly find their HCF. But for these cases, we can proceed by using the number that all of them are multiples of or divisible by as the first divisor.

Example:

HCF (16, 48) = ?

Since 16 and 48 are both multiples of 16, we are going to use 16 as the first divisor.

Then write the quotients below their respective dividends.

We can notice here that we are already left with numbers that cannot be divided by the same number. This means that we can now stop the process and set the only divisor we have, 16, as the Highest Common Factor of 16 and 48.

Therefore, HCF (16, 48) = 16

### Method 4: Euclidean Algorithm Using Long Division

We can also use Long Division to find the Highest Common Factor of two larger numbers and seems not multiples of the same number at a first sight. We can do this by dividing the larger number by the smaller number. Next, use the remainder as the new divisor to divide the preceding divisor. Then, repeat the process until there is no remainder. The last divisor is the Highest Common Factor of the pair of numbers.

Example:

HCF (105, 189) = ?

Since the last divisor that we got is 21, we can say that the Highest Common Factor of 105 and 189 is 21 or HCF (105, 189) = 21.

Note: Since we talked about different strategies on how to find the Highest Common Factor of a pair of numbers, the best technique still is whatever you are comfortable with. You may notice that even though we used the same examples using different methods, we can still obtain the same HCF.

## Getting the Highest Common Factor of Three or Four Numbers

To efficiently find the Highest Common Factors of three numbers, we can use both Continuous Division Method and Euclidean Algorithm using Long Division.

Example 1: HCF (27, 45, 81)

1. Using Continuous Division

27, 45, are, 81 are both multiples of 9. So, we are going to use 9 as their divisor.

Then, divide the numbers by 9 and put the quotients beneath their respective                    dividends.

3, 5, and 27 cannot be divided by the same prime factor, so we may now end the process. Since we only have 9 as the divisor, it means that it is also their Highest Common Factor.

Hence, HCF (27, 45, 81) = 9.

1. Using Long Division

First, choose two numbers to divide. Ideally, choose the numbers that are not a factor of the other. For example, we cannot choose 27 and 81 as the first pair because 27 is a factor of 81 and we might obtain incorrect HCF. So we are going to divide 81 by 45 first.

Now that there is no remainder left, we can now end the process for this pair. Since we have 9 as the last divisor, we are now going to use this as the divisor to divide the remaining number which is 27.

Because we still get 9 as the last divisor, this means that 9 is the HCF of the three numbers.

Therefore, HCF (27, 45, 81) = 9.

We can notice that either way, whether we use Continuous Division or Long Division, we can still get the same answer.

Example 2: HCF (24, 48, 84, 96) = ?

If we need to find the HCF of four numbers, it is efficient to use a quicker technique. Since all of the given numbers are even, we can use Continuous Division.

Then, multiply the prime factors to get the HCF.

HCF (24, 48, 84, 96) = 2 x 2 x 3

HCF (24, 48, 84, 96) = 12

## Applications of Highest Common Factor

There are lots of real-life situations where we can use finding the Highest Common Factor of numbers. But the common denominator of these cases is having a goal of distributing things evenly to a different set of numbers.

Example:

Mrs. Gomez needs to choose students from three sections with 12, 24, and 30 students to represent their sections for a school activity. She does not want to depend on how large or small the population of each section is. Rather, she wants to be fair by choosing the same or the common number of students from each section. How many students will she choose from each section?

Solution:

We need to find the HCF of the three numbers, 12, 24, and 30 to find the highest common number that Mrs. Gomez will pull out from each section.

12, 24, and 30 are divisible by 6, so it is fine to proceed with using it as the first divisor.

Since the quotients cannot be divided by any same factors anymore, we can declare 6 as the HCF. Therefore, Mrs. Gomez should choose 6 students from each section to make a fair count.

Activity

Directions: Find the HCF of the following pair or group of numbers. Use the method or strategy you are most comfortable with or you find suitable for the case of the numbers.

Solutions:

## Summary

• A factor is a kind of divisor that divides a number exactly. Moreover, a factor is different from multiple, because multiples are products of factors.
• The Highest Common Factor is the highest factor that can divide a pair or group of numbers equally or without remainder.
• There are different ways to obtain the HCF or GCF of numbers:
• Listing Method
• Prime Factorization
• Factor Tree
• Tabular Division
• Continuous Division
• Euclidean Algorithm Using Long Division
• In real-life situations, you can use the principle of HCF on finding the common number or amount you want to obtain from a set of different numbers.

We spend a lot of time researching and compiling the information on this site. If you find this useful in your research, please use the tool below to properly link to or reference Helping with Math as the source. We appreciate your support!

• "Highest Common Factor (HCF)". Helping with Math. Accessed on September 13, 2024. https://helpingwithmath.com/highest-common-factor-hcf/.

• "Highest Common Factor (HCF)". Helping with Math, https://helpingwithmath.com/highest-common-factor-hcf/. Accessed 13 September, 2024.