Highest Common Factor

If a number can be expressed as the product of two numbers, then each number of the product is a factor of the given number.

For example:

Similarly, \(18\) can be written as the products of the following numbers:

\[\begin{align} 18 &= 1 \times 18 \\ 18 &= 3 \times 6 \end{align}\]

Thus, the factors of \(18\) are \(1,2,3,6,9\) and \(18\).

---

A common factor of two or more numbers is a factor that is common to both of the given numbers.

For example, the common factors of two numbers \(18\) and \(27\) can be found by listing the factors of both numbers.

Thus, the common factors of \(18\) and \(27\) are \(1,3\) and \(9\).

---

• The HCF (Highest Common Factor) of two or more numbers is the highest number among all the common factors of the given numbers.
   
• The HCF (Highest Common Factor) of two natural numbers \(x\) and \(y\) is the largest possible number which divides both \(x\) and \(y\).

From the above example, the common factors of \(18\) and \(27\) are \(1,3\) and \(9\).

Among these numbers, \(9\) is the highest (largest) number.

Thus, the HCF of \(18\) and \(27\) is \(9\).

This is written as:

\[\text{HCF (18,27)} = 9 \]

HCF Examples

Using the above definition, the HCF of:

• \(60\) and \(40\) is \(20\), i.e,
  \[\text { HCF} (60,40) = 20 \]
• \(100\) and \(150\) is \(50\), i.e,
  \[\text { HCF} (150,50) = 50 \]
• \(144\) and \(24\) is \(24\), i.e,
  \[\text { HCF} (144,24) = 24 \]
• \(17\) and \(89\) is \(1\), i.e,
  \[\text { HCF} (17,89) = 1\]

But how to find HCF of two numbers?

There are 3 methods to calculate the HCF of two numbers: 

1. HCF by listing out the common factors
2. HCF by prime factorization 
3. HCF by division method

Let us discuss each method in detail.

The process of finding the HCF of multiple numbers is the same as explained above for the methods “HCF by listing out the common factors” and “HCF by prime factorisation.”

However, the method to find the HCF of multiple numbers by division method is different.

1. To find the HCF of three 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. 

Example:

Find the HCF of \(126, 162\) and \(180\).

Solution:

First, we will find the HCF of the two numbers \(126\) and \(162\).

Thus,

\[\text{HCF of 126 and 162}=18  \,\,\,\,\, \rightarrow (1)\]

Next, we will find the HCF of the third number, which is \(180\), and the above HCF \(18\).

Thus,

\[\text{HCF of 180 and 18}=18  \,\,\,\,\, \rightarrow (2)\]

From (1) and (2),

HCF of \(126, 162\) and \(180\) is \(18\)

2. To find the HCF of four numbers:

• First, we will find the HCF of the two pairs of numbers separately.
• Next, we will find the HCF of the HCFs of the two pairs of numbers.

Example:

Find the HCF of \(72,140,256\) and \(24\).

Solution:

First, we will find the HCF of the first two numbers \(72\) and \(140\).

Thus,

\[\text{HCF of 72 and 140}=4  \,\,\,\,\, \rightarrow (1)\]

Next, we will find the HCF of the last two numbers \(256\) and \(24\).

Thus,

\[\text{HCF of 256 and 24}=8  \,\,\,\,\, \rightarrow (2)\]

Now, we will find the HCF of the HCFs that are in equation (1) and equation (2), i.e., we will find the HCF of \(4\) and \(8\).

Thus,

\[\text{HCF of 4 and 8}=4\]

HCF of \(72,140,256\) and \(24\) is \(4\)

---

We know that a prime number has only two factors, \(1\) and itself.

Let us consider two prime numbers \(2\) and \(7\), and find their HCF by listing their factors.

Factors of \(2\) are \(1, 2\).

Factors of \(7\) are \(1, 7\).

We can see that the only common factor of \(2\) and \(7\) is \(1\) and hence, this is the HCF.

Thus,

HCF of prime numbers = \(1\)

---

The following "Highest Common Factor Calculator" would show the HCF of the numbers that you enter.

Enter the numbers you wish to find the HCF of and click on the Go button:

---

Example 1

 

 

Find the HCF of \(6, 72\) and \(120\) by using the "listing factors" method. 

Solution:

The given numbers are \(6, 72\) and \(120\).

We will find the factors of each of these numbers.

Factors of \(6\) = \(1, 2, 3, 6\)

Factors of \(72\) = \(1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72 \)

Factors of \(120\) = \(1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120\)

Now, circle the common factors.

\(6\) is the only common factor and hence, it is the HCF.

HCF of \(6, 72\) and \(120\) = \(6\)

Example 2

 

 

Find the HCF of \(168, 252\) and \(288\) by the "prime factorisation method."

Solution:

The given numbers are \(168, 252\) and \(288\).

We will find the prime factorisation of each of these numbers.

Thus,

\[ \begin{align}168&=2^{3} \times 3^{1} \times 7^{1}\\[0.3cm]252&=2^{2} \times 3^{2} \times 7^{1}\\[0.3cm]288&=2^{5} \times 3^{2}\end{align} \]

The HCF of these three numbers will be the product of the smallest power of each common prime factor of the three numbers.

Thus,

\[\text{HCF of 168, 252 and 288}  = 2^2 \times 3^1 = 12 \]

Hence,

HCF of \(168, 252\) and \(288\) = 12

Example 3

 

 

Find the HCF of \(9000\) and \(980\) using the "division method."

Solution:

Among the given numbers, \(9000\) is the smallest and \(980\) is the largest.

We will divide the larger number by the smaller number.

Next, we will make the remainder as the divisor and the last divisor as the dividend and divide again.

We will repeat this process until the remainder is \(0\).

Thus,

HCF of \(9000\) and \(980\) = \(20\)