Highest Common Factor (HCF)

What is HCF?

The highest common factor (HCF) of two or more numbers is the greatest of the factors common to them.

There are different methods of finding HCF of two or more numbers. 2 of those methods are;

1. Short division method
2. Prime Factorization Method

Worked Example 1.3.1:

Find the HCF of 

a. 12 and 16

b. 18, 27 and 36

c.
2 × 2 × 3 × 5 × 7
2 × 2 × 2 × 2 × 7

d.
2² × 3³ × 5
2³ × 3² × 5² × 7

Solution

a. 12 and 16

Method 1: (Short Division Method)

Applying this method, we divide each number by common prime factors. The steps are as follows:

• Write the numbers in individual rows.

• Divide the numbers by common prime factors.

• Factorisation stops when we reach prime numbers which cannot be further divided.

• HCF is the product of all the common factors.

Hence, the common factors are 2, and 2.

HCF of 12 and 16 = 2 × 2 = 4

Method 2: Prime Factorization Method

Express each number as a product of its prime factors and multiply their common prime factors.

HCF  =  2 × 2 = 4

b. 18, 27 and 36

Method 1:

HCF =  3 × 3 = 9

Method 2:

18 = 2   ×    3   ×  3
27 = 3   ×    3   ×  3
36 = 2   ×   2   ×  3  ×   3

HCF  = 3 × 3 = 9

c.

2 × 2 × 3 × 5 × 7        
2 × 2 × 2 × 2 × 7

HCF   =   2 × 2

=   4

d.

2² × 3³ × 5
2³  ×  3²  ×  5²  × 7

In this case, the easiest way is to compare powers of the same base. The one with the lowest power is a common factor.

HCF  =   2²   ×  3²   ×  5

=   4 × 9 × 5  =  180

 Note:
2²  and 2³ The index  (power) ‘2’ is  lower than 3
3³ and 3² The index ‘2’ is lower than 3
5¹ and 5² The index ‘1’ is lower than 2
2²   is less than (<)   2³ 
3²  is less than (<)  3³ 
5¹   is less than (<)  5²