Session 6: Highest Common Factor (H.C.F.) – Definition, Methods, Steps, Interactives and Examples

What is a Common Factor?

In the lesson ‘Factors’, we learnt that a factor is a number that divides another number completely without any remainder. In this section, we will look at factors that are common among the factors of two or more numbers. These factors are known as common factors.  

Example: 8 can divide 16 without leaving any remainder.

                 8 can divide 24 without leaving any remainder.

                 8 can divide 48 without leaving any remainder.

Here, 8 is a divisor and a factor of 16, 24 and 48. So, 8 is a common factor of these three numbers.

1) Find the common factors of 12 and 16.

First, find all the factors of 12 and 16 and write them in a list in the order of least to greatest to make sure that every factor is covered. 

One way to check if all the factors are listed is to use the rainbow method. Draw a line from one part of a factor pair to the other. The resulting image should resemble a rainbow.

Next, identify the common factors that appear in both lists.

The common factors for 12 and 16 are 1, 2 and 4.

Steps to find Common Factors

To find common factors, we follow the following steps: 

Step 1: List down all the factors of the given numbers in separate rows.

Step 2: Circle all the factors that are common in the given numbers. 

Step 3: Write down all the common factors in a separate row.

Highest Common Factor (H.C.F.)

When two or more numbers have more than one common factor, the greatest among them is called their highest common factor (H.C.F.). In other words, the H.C.F. of two or more numbers is the greatest number that divides all the given numbers. 

Consider two numbers, 20 and 48.

First, find all the factors of 20 and 48 and write them in a list in the order of least to greatest.

Thus, the common factors for 20 and 48 are 1, 2 and 4. Among these factors, 4 is the greatest factor. Thus, the H.C.F. of 20 and 48 is 4. It is written as H.C.F.(20,48)=4.

Note: The highest common factor (H.C.F.) of two or more numbers is a unique number,

• which is a factor of each of the two numbers, i.e., the common factor of all the numbers, and
• which is the greatest among the common factors of these numbers.

The highest common factor ( H.C.F. ) is also called the greatest common divisor (G.C.D.) or the greatest common measure (G.C.M.). 

Note: The H.C.F. of two co-prime numbers is always 1.

Methods to Find H.C.F.

The five commonly used methods for finding the H.C.F. of two or more numbers are:

• Listing Method
• Factor Tree Method (Prime factorization)
• Division Method (Prime factorization)
• Common Division Method
• Long Division Method

Finding H.C.F. by the Listing Method

In this method, first, we list out the factors of each given number and find the factors that are common in those numbers. Then, among the common factors, we identify the highest common factor. Let’s understand this method using an example.

2) Find the H.C.F. of 24 and 40. 

First, find all the factors of 24 and 40 and write them in a list in the order of least to greatest.

 

1, 2, 4 and 8 are common factors, but 8 is the greatest of the four.

So, H.C.F.(24,40)=8.

Steps to Find H.C.F. using the Listing Method

To find the H.C.F. of two or more numbers using lists, we follow the following steps:

Step 1: List down all the factors of the given numbers in separate rows.

Step 2: Circle all the factors that are common in the given numbers.

Step 3: Identify the greatest number in the list of common factors. This number is the required H.C.F.

Finding H.C.F. by the Factor Tree Method (Prime Factorization)

In this method, we find the prime factorization of each number using the factor tree method and find the prime factors that are common in those numbers. Then, we find the H.C.F. of those numbers by finding the product of the common prime factors of the given numbers. Let’s understand this method using an example.

3) Find the H.C.F. of 20 and 30.

Identify the common factors. The numbers 20 and 30 have the factors 2 and 5 in common.

Next, multiply the common factors to find the H.C.F. There is no need to multiply if there is only one common factor.

2×5=10
Hence, H.C.F.(20,30)=10.

Steps to Find H.C.F. using the Factor Tree Method (Prime Factorisation)

To find the H.C.F. of two or more numbers using the factor tree method, we follow the following steps:

Step 1: Write the prime factorisation of the given numbers using the factor tree method.

Step 2: Identify common prime factors of the given numbers.

Step 3: Multiply each common prime factor to find the required H.C.F.

Finding H.C.F. by the Division method (Prime Factorization)

In this method, we find the prime factorization of each number using the division method and find the common prime factors in those numbers. Then, we find the H.C.F. of those numbers by finding the product of the common prime factors of the given numbers. Let’s understand this method using an example.

4) Find the highest common factor of 84 and 90.

First, write down the prime factorization of each of the numbers.

 

Identify the common factors. The numbers 84 and 90 have factors 2 and 3 in common.

Next, multiply the common factors to find the H.C.F. There is no need to multiply if there is only one common factor.

2×3=6

Hence, H.C.F.(84,90)=6.

Steps to Find H.C.F. using the Division Method

To find the H.C.F. of two or more numbers using the division method, we follow the following steps:

Step 1: Write the prime factorization of the given numbers using the division method.

Step 2: Identify common prime factors of the given numbers.

Step 3: Multiply each common prime factor to find the required H.C.F.

---

Finding H.C.F. by the Common Division method

In this method, we divide the given numbers by a common factor, which should be a prime number. The resultant quotients are again divided by the common factor. We continue this process until no common factor is left.  The required H.C.F is the product of all the common divisors. 

5) Find the H.C.F of 600, 912 and 240.

Since all the three numbers are even, the numbers are divisible by 2. On dividing, we obtain 300, 456 and 120 as the quotients, which are also even. So we divide them by 2. The quotients obtained are 150, 228 and 60, which are further divisible by 2 and 3. After division by 3, the quotients obtained are 25, 38 and 10. Clearly, these three do not have a common factor. Therefore, we stop the division process. 

Hence, H.C.F.(600,912,240)=2×2×2×3=24.

Steps to Find the H.C.F. using the Common Division Method

To find the H.C.F. of two or more numbers using the common division method, we follow the following steps:

Step 1: Identify a common prime factor of the given numbers.

Step 2: Divide the given numbers by the common factor and write the resultant quotients.

Step 3: Obtain a common factor of the resultant quotients. 

Step 4: Divide the resultant quotients by this common factor.

Step 5: Repeat Step 3 and Step 4 until no common factor is left.

Step 6: The product of all the common divisors obtained in the above steps gives the required H.C.F. of the given numbers.

---

Finding H.C.F. by the Long Division method or Continued Division Method

When the numbers whose H.C.F. has to be found are very large, it is time-consuming and tedious to use the prime factorization method. In this case, we use the long division method.

The long division method was proposed by the Greek mathematician Euclid and hence is also known as Euclid’s Algorithm. In this method, we divide the larger number by the smaller number. If the remainder is zero, then the divisor is the H.C.F.; otherwise, we make the remainder the new divisor and the divisor of the above step as the new dividend and perform the long division again. We continue the long division process till we get the remainder as 0, and the last divisor will be the H.C.F. of those two numbers. 

5) Using Euclid’s algorithm, find the H.C.F. of 216 and 1200.

First, we divide 1200 by 216 and find the remainder. 

Since the remainder 120≠0, we make the remainder 120 as the new divisor and the original divisor 216 as the new dividend to get

Since 96≠0, so we now consider the remainder 96 as the new divisor and the divisor 120 as the new dividend to get

Let us now consider the remainder 24 as the new divisor and 96 as the new dividend.

We observe that the remainder at this stage is zero. Therefore, the divisor at this stage, i.e., 24 is the H.C.F. of 216 and 1200.   

Steps to Find H.C.F. using the Long Division Method

To find the H.C.F. of two or more numbers using the long division method, we follow the following steps:

Step 1: Divide the larger number by the smaller number. 

Step 2: If the remainder is zero, then the divisor is the H.C.F.; otherwise, we make the remainder the new divisor and the divisor the new dividend and perform the long division again.  

Step 3: Repeat Step 2 till we get the remainder as 0, and the last divisor will be the H.C.F. of those two numbers.

Highest Common Factor (H.C.F.) – Examples

Example 1

Find the common factors of 6, 14 and 21. 

First, find all the factors of 6, 14 and 21 and write them in a list in the order of least to greatest. 

Clearly, 1 is the only common factor of 6, 14 and 21.

Example 2

Find the H.C.F. of 36 and 54 using the factor tree method. 

First, make a factor tree for each number and identify the common factors. 

The numbers 36 and 54 have the factors 2 and two 3s in common. Next, we multiply the common factors to find the H.C.F. 

2×3×3=18

H.C.F.(36,54)=18.

Example 3

Find the H.C.F. of 120, 320 and 420 using Euclid’s algorithm. 

We first find the H.C.F. of 320 and 420 using Euclid’s algorithm.  

H.C.F.(320,420)=20.

Now, we find the H.C.F. of 20 and 120. 

H.C.F.(20,120)=20.

Hence, the required H.C.F. of 120, 320 and 420 is 20. 

Example 4

Ayeshee is making gift bags. She has 36 pencils and 28 pens. How many gift bags can Ayeshee make if there are the same number of pencils and pens in each bag? Use factor trees to solve this problem. How many pencils and pens will be in each bag?

First, make a factor tree for each number and identify the common factors. 

The common factors are two 2s.

Next, multiply the common factors to find the H.C.F.

2×2=4

Finally, divide the number of pencils and pens by the H.C.F, 4.

Pencils=36÷4=9
Pens=28÷4=7

Ayeshee can make four gift bags that have 9 pencils and 7 pens in each bag.

Example 5

Kiran is making flower arrangements for a friend’s wedding. She has 850 roses and 680 lilies. She wants there to be an equal number of roses and lilies in each vase. What is the most number of arrangements she can make? How many of each flower will they contain?

Kiran has 850 roses and 680 lilies and wants each arrangement to have the same number of flowers. Since each arrangement must have the same number of flowers, therefore, the number of flowers will be the least if the number of arrangements is the H.C.F of 850 and 680. 

Let us find the H.C.F. of 850 and 680 using Euclid’s algorithm.

Since the remainder at this stage is zero, therefore, last divisor 170 is the H.C.F. of 850 and 680. Hence, the number of arrangements is 170. 

Next, find the number of roses and lilies in 170 arrangements. 

Roses: 850÷170=5

Lilies: 680÷170=4

The most number of arrangements Kiran can make will be 170. Each will have 5 roses and 4 lilies.

Example 6

Find the largest number that will divide 139, 175 and 261, leaving remainders 4, 5 and 6 respectively. 

It is given that the required number when divides 139, 175 and 261, the remainder is 4, 5 and 6 respectively. This means that 139−4=135, 175−5=170 and 261−6=255 are completely divisible by the required number. It follows from this that the required number is the largest divisor. 

Let us now find the H.C.F. of 135, 170 and 255 by Euclid’s algorithm. Let us first find the H.C.F. of 170 and 255. 

The remainder at this stage is 0. So, the divisor 85 is the H.C.F. of 255 and 170. 

We use Euclid’s algorithm to find the H.C.F. of 85 and 135.

So the H.C.F. of 135 and 85 is 5. 

Hence, the largest number that will divide 139, 175 and 261 leaving the remainder 4, 5 and 6 respectively, is 5.

 Remember this!

• A factor is a number that divides another number completely without any remainder. 
• A number that is a factor of each of the given numbers is called a common factor. 
• The greatest number, which is a common factor of two or more given numbers, is called their highest common factor (H.C.F.)
• The H.C.F. of any two co-prime numbers is always 1.