HCF - Highest Common Factor

The Highest Common Factor (HCF) of two numbers is the highest possible number which divides both the numbers exactly. HCF of a and b is denoted by HCF (a, b). Let d be the HCF (a, b), then you can't find the common factor of a and b greater than the number d. The highest common factor (HCF) is also called the greatest common divisor (GCD)

There is more than one method to find the HCF of two numbers. One of the quickest ways to find the HCF of two numbers is to use the prime factorization of each number and then the product of the least powers of the common prime factors will be the HCF of those numbers. Explore the world of HCF by going through its various aspects and properties. Find answers to questions like what is the highest common factor for a group of numbers, easy ways to calculate HCF, its relation with LCM, and discover more interesting facts around them. Read on! Let's explore more about HCF

The HCF (Highest Common Factor) of two or more numbers is the highest number among all the common factors of the given numbers or in simple words, the HCF (Highest Common Factor) of two natural numbers x and y is the largest possible number that divides both x and y. Let's understand this definition using two numbers, 18 and 27. The common factors of 18 and 27 are 1, 3, and 9. Among these numbers, 9 is the highest (largest) number. So, the HCF of 18 and 27 is 9. This is written as: HCF (18,27) = 9

HCF Examples

Using the above definition, the HCF of:

•  60 and 40 is 20, i.e, HCF (60,40) = 20
• 100 and 150 is 50, i.e, HCF (150,50) = 50
• 144 and 24 is 24, i.e, HCF (144,24) = 24
• 17 and 89 is 1, i.e, HCF (17,89) = 1

There are many ways to find the highest common factor of the given numbers. Irrespective of the method the answer to the HCF of the numbers would always be the same. There are 3 methods to calculate the HCF of two numbers:

• HCF by listing out the common factors
• HCF by prime factorization
• HCF by division method

Let us discuss each method in detail by understanding the examples.

HCF by Listing out the Common Factors

In this method, we list out the factors of each number and determine the common factors of those numbers. Then, among the common factors, we determine the highest common factor. Let's understand this method using an example.

We will find the HCF of 30 and 42. We will list the factors of 30 and 42. The factors of 30 are 1, 2, 3, 5, 6, 10, 15, and 30 and the factors of 42 are 1, 2, 3, 6, 7, 14, 21, and 42. Clearly, 1, 2, 3, and 6 are the common factors of 30 and 42. But 6 is the common factor and the greatest one. Hence, the HCF of 30 and 42 is 6.

HCF by Prime Factorisation

In this method, we find the prime factorization of each number and find the common prime factors of those numbers. Then, we find the HCF of those numbers by finding the product of the prime factors that are common to each of the given numbers. Let's understand this method using an example.

We will find the HCF of 60 and 90. Let's represent the numbers using the prime factorization.So, we have, 60 = 2 × 2 × 3 × 5 and 90 = 2 × 3 × 3 × 5. Now, HCF of 60 and 90 will the product of common prime factors, which are, 2, 3, and 5. So, HCF of 60 and 90 = 2 × 3 × 5 = 30

HCF by Division Method

In this method, we divide the larger number by the smaller number and check the remainder. Then, we make the remainder of the above step as the divisor and the divisor of the above step as the 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 HCF of those two numbers. Let's understand this method using an example.

Let's find the HCF of 198 and 360 using the division method. Among the given two numbers,360 is the larger number, and 198 is the smaller number. We divide 360 by 198 and check the remainder. Here, the remainder is 162. Make the remainder 162 as the divisor and the divisor 198 as the dividend and perform the long division again. We will continue this process till we get the remainder as 0 and the last divisor will is 18 which is the HCF of 198 and 360.

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 factorization.” However, the method to find the HCF of multiple numbers by division method is different.

HCF of three numbers

To find the HCF of three numbers, follow the steps given below.

• 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 180

Thus, HCF of 126 and 162 = 18. Next, we will find the HCF of the third number, which is 180, and the above HCF 18.

HCF of 126, 162 and 180 = 18

HCF of four numbers

To find the HCF of four numbers, follow the steps given below.

• 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.

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. The factors of 2 are1 and2 and the factors of7 are 1 and 7. We can see that the only common factor of 2 and 7 is 1 and hence, this is the HCF. So, the HCF of prime numbers is always equal to 1.

Now, you already know that the HCF of a and b is the highest common factor of the numbers a and b. Let us have the look at the important properties of HCF:

The properties of HCF are given below.

• HCF of two or more numbers divides each of the numbers without a remainder.
• HCF of two or more numbers is a factor of each of the numbers.
• HCF of two or more numbers is always less than or equal to each of the numbers.
• HCF of two or more prime numbers is 1 always.

Relation Between LCM and HCF

What is the Highest Common Factor?

The HCF (Highest Common Factor) of two numbers is the highest number among all the common factors of the given numbers. For example, HCF of 12 and 36 is 12 because 12 is the highest common factor of 12 and 36

How do you Find the HCF in Math?

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

• HCF by listing out the common factors
• HCF by prime factorization 
• HCF by division method

These methods are explained in detail with examples under the section titled How to find HCF? on this page.

What are the Properties of HCF?

The properties of HCF are:

• HCF of two or more numbers divides each of the numbers without a remainder. 
• HCF of two or more numbers is a factor of each of the numbers.
• HCF of two or more numbers is always less than or equal to each of the numbers.
• HCF of two or more prime numbers is 1 always.

What are the Steps to be Followed to Calculate the HCF of two Numbers using the Long Division Method?

The steps to find the HCF of two numbers using long division are mentioned below:

• Step 1: Divide the larger number by the smaller number and check the remainder.

• Step 2: Make the remainder of the above step as the divisor and the divisor of the above step as the dividend and perform the long division again.

• Step 3: Continue till you get the remainder as 0 and the last divisor will be the HCF of two numbers.

How do I find the Highest Common Factor in Math?

Follow the steps given below to find the HCF of two numbers by Listing the Common Factors.

• Step 1: List the factors of two numbers.
• Step 2: Identify the common factors of two numbers.
• Step 3: HCF of two numbers is equal to the highest factor among the common factors of two numbers.

What is the Difference Between LCM and HCF?

The least common multiple of two or more numbers is the smallest number among all common multiples of the given numbers and the HCF (Highest Common Factor) of two or more numbers is the highest number among all the common factors of the given numbers.

What is the Relationship between HCF and LCM of two Numbers?

Let's assume 'a' and 'b' are the two numbers. Then the formula that gives the relationship between their LCM and HCF is given as LCM (a,b) × HCF (a,b) = a × b