Playing With Numbers

Highest Common Factor (HCF)

Highest Common Factor. The Highest Common Factor (or HCF) of two or more given numbers is the highest (or greatest) of their common factors.

The greatest common factor of two or more numbers is the largest number shared by all the factors.

The highest common factor GCF is the same as

GCF – Greatest Common Factor

GCD – Greatest Common Divisor

HCD – Highest Common Divisor

GCM – Greatest Common Measure

HCM – Highest Common Measure

Methods to find the Highest Common Factor (HCF)

We can calculate the HCF of few given numbers in the following ways.

Method 1 – HCF by Listing Multiples

• Step 1. List the factors of each number of the lists.
• Step 2. Find the greatest number that is on all of the lists.
• Step 3. This number is the HCF.

Example. Find the HCF of 60 and 75.

Solution. Following the above steps, we have

• Factors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 30, 60
• Factors of 75: 1, 3, 5, 15, 25, 75

The common factors of 60 and 75 are 1, 3, 5 and 15. The highest factor that is there in all the lists is 15. Therefore, HCF (60, 75) is 15.

Example. Find the HCF of 24, 36 and 72.

Solution. Following the above steps, we have

• Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
• Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
• Factors of 72: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

The common factors of 24, 36 and 72 are 1, 2, 3, 4, 6 and 12. The highest number that is there in all the lists is 12. Therefore, HCF (24, 36, 72) is 12.

Method 2 – HCF by Prime Factorisation

• Step 1. Write each number as a product of its prime factors.
• Step 2. Now list the common factors of both the numbers.
• Step 3. The product of all common prime factors is the HCF.

Example. Find the HCF of 60 and 90.

Solution. The prime factorisations of 60 and 90 are:

• 60 = 2 × 2 × 3 × 5
• 90 = 2 × 3 × 3 × 5

The common prime factors 2, 3 and 5.

Therefore, HCF (60, 90) = 2 × 3 x 5 = 30.

Example. Find the HCF of 48, 72 and 144.

Solution. The prime factorisations of 48, 72 and 144 are:

• 48 = 2 × 2 × 2 × 2 × 3
• 72 = 2 × 2 × 2 × 3 × 3
• 144 = 2 × 2 × 2 × 2 × 3 × 3

The common prime factors are 2, 2, 2 and 3.

Therefore, HCF (60, 90) = 2 × 2 × 2 × 3 = 24.

Method 3 – HCF by Division Method

• Step 1. Divide the larger number by the smaller number and check the remainder.
• Step 2. Make the remainder of Step 1 as the divisor and the divisor of the above step as the dividend and perform the long division again.
• Step 3. Continue Step 2 till we get the remainder as 0.
• Step 4. The last divisor will be the HCF of those two numbers.

If there are more than two numbers, first we will find the HCF of two of the numbers. Next, we will find the HCF of the third number and the HCF of the first two numbers (and the procedure will continue).

Exercise 1. Find the HCF of the following numbers :

(a) 18, 48 (b) 30, 42 (c) 18, 60 (d) 27, 63 (e) 36, 84 (f) 34, 102 (g) 70, 105, 175 (h) 91, 112, 49 (i) 18, 54, 81 (j) 12, 45, 75

Exercise 2. What is the HCF of two consecutive (a) numbers? (b) even numbers? (c) odd numbers?

Exercise 3. HCF of co-prime numbers 4 and 21 was found as follows by factorisation:

4 = 2 × 2 and 21 = 3 × 7 since there is no common prime factor, so HCF of 4 and 21 is 0. Is the answer correct? If not, what is the correct HCF?