How to find HCF | Highest Common Factor, Definition, Meaning, Solved Problems

The full form of HCF is Highest Common Factor. In mathematics, the Highest Common Factor (HCF) is the largest number that divides two or more numbers without leaving a remainder. The HCF can be calculated for two or more numbers. HCF is also commonly referred to as the Greatest Common Divisor (GCD).

There are several methods for determining the HCF of a given number, including the prime factorization method, division method, and Euclidean algorithm. In this article, we will discuss everything about how to find the HCF of a given number with solved examples. Scroll down to find out more.

Looking to Learn Math? Book a Free Trial Lesson and match with top Math Tutors for concepts, homework help, and test prep.

What is the Highest Common Factor (HCF) in Maths?

The Highest Common Factor (HCF) is the highest number that divides two or more numbers without leaving a remainder.

For example, the HCF of 12 and 18 is 6. Here, 12 is expressed as 2 * 2 * 3, and 18 is expressed as 2 * 3 * 3. If we consider the factors of 12 and 18, we get:

Factors of 12: 1, 2, 3, 4, 6, 12 Factors of 18: 1, 2, 3, 6, 9, 18

The highest common factor for 12 and 18 is 6. Hence, the HCF of 12 and 18 is 6.

HCF is used for the simplification of fractions. When the numerator and denominator of a fraction have a common factor, HCF is used to simplify the fraction by dividing both the numerator and denominator by the common factor.

Properties of HCF

Properties of HCF Before we learn how to find HCF, we should first understand the following properties of HCF:

1. Associative Property of HCF

The associative property of HCF states that the HCF of A and B will be the same as the HCF of B and A.

HCF (A, B) = HCF (B, A)

For example, let’s consider A as 12 and B as 18. We can write 12 as 2 * 2 * 3 and 18 as 2 * 3 * 3. To find the HCF of 12 and 18, we take the common factors of both the numbers, which are 2 and 3. The greatest common factor is the product of these common factors, which is 2 * 3 = 6.

Now, let’s swap A and B, i.e., B as 12 and A as 18. We can write 12 as 2 * 2 * 3 and 18 as 2 * 3 * 3. To find the HCF of 18 and 12, we take the common factors of both the numbers, which are 2 and 3. The greatest common factor is the product of these common factors, which is 2 * 3 = 6.

Thus, we have proved that HCF (12, 18) = HCF (18, 12) = 6.

2. Commutative Property of HCF

Commutative Property of HCF The commutative property of HCF states that the HCF of three or more numbers is the same, regardless of the order in which we take them.

HCF (A, B, C) = HCF (HCF (A, B), C) = HCF (A, HCF (B, C))

For example, let’s consider A as 20, B as 30, and C as 40. Here, 20 can be expressed as 2 * 2 * 5, 30 can be expressed as 2 * 3 * 5, and 40 can be expressed as 2 * 2 * 2 * 5.

So, the common factors of 20, 30, and 40 are 2 and 5.

Now, we will find the product of common factors to get the HCF, which is 2 * 5 = 10.

Similarly, HCF (A, B) = 10, HCF (B, C) = 10, and HCF (A, C) = 10.

Hence, it is proved that HCF (20, 30, 40) = HCF (HCF (20, 30), 40) = HCF (20, HCF (30, 40)) = 10.

3. Distributive Property of HCF

The distributive property of HCF states that:

HCF (dA, dB, dC) = d * HCF (A, B, C)

where A, B, and C are positive integers, and d is any positive integer.

To understand this property, let’s consider an example. Suppose we want to find the HCF of 12, 18, and 30. We can start by finding the prime factors of these numbers:

12 = 2 * 2 * 3 18 = 2 * 3 * 3 30 = 2 * 3 * 5

To find the HCF of these numbers, we need to find the highest common factor of their prime factors. We can do this by selecting the common factors with the lowest exponent, as follows:

HCF (12, 18, 30) = 2 * 3 = 6

Now, let’s apply the distributive property of HCF to simplify this calculation. We can write:

12 = 2 * 2 * 3 = 2^2 * 3^1 18 = 2 * 3 * 3 = 2^1 * 3^2 30 = 2 * 3 * 5 = 2^1 * 3^1 * 5^1

Therefore, using the distributive property of HCF, we have:

HCF (2^2 * 3^1 d, 2^1 * 3^2 d, 2^1 * 3^1 * 5^1 d) = d * HCF (2^2 * 3^1, 2^1 * 3^2, 2^1 * 3^1 * 5^1)

Simplifying the second part of the equation, we find that:

HCF (2^2 * 3^1, 2^1 * 3^2, 2^1 * 3^1 * 5^1) = 2^1 * 3^1 = 6

Substituting this value into the distributive property of HCF, we get:

HCF (2^2 * 3^1 d, 2^1 * 3^2 d, 2^1 * 3^1 * 5^1 d) = d * 6

Hence, we can see that the HCF of 12, 18, and 30 is 6d, where d is any positive integer.

In summary, the distributive property of HCF can be used to simplify calculations involving the HCF of three or more numbers. It states that the HCF of a set of numbers multiplied by a constant is equal to the constant multiplied by the HCF of the numbers.

How to find the HCF?

Similar to finding the LCM, there are also three methods for finding the HCF (highest common factor) of two or more numbers. The methods are:

1. Division Method

1. To find the HCF using the division method, divide the greater number by the smaller number. Then, divide the smaller number by the remainder obtained in the first division. Continue this process of dividing the last divisor by the remainder obtained until the remainder is 0. The last divisor obtained will be the HCF of the given numbers.

You can follow the following steps to find the HCF using the division method:

• Step 1 : Write all the given numbers for which you have to find the HCF, separated by commas.
• Step 2: Find the greater number among the given numbers.
• Step 3: Find the smaller number among the given numbers.
• Step 4: Divide the greater number by the smaller number and find the remainder.
• Step 5: Divide the smaller number by the remainder obtained in the first division and find the remainder.
• Step 6: Continue this process until the remainder is 0.
• Step 7: The last divisor obtained in the process will be the HCF of the given numbers.

For example, you have to find the HCF of 48 and 64 using the division method.

• Step 1: Numbers to be considered are 48 and 64.
• Step 2: The greater number is 64.
• Step 3: The smaller number is 48.
• Step 4: 64 ÷ 48 = 1 with a remainder of 16
• Step 5: 48 ÷ 16 = 3 with a remainder of 0
• Step 6: Since the remainder is 0, the last divisor obtained in the process is 16.
• Step 7: So, the HCF of 48 and 64 is 16.

2. Prime Factorization Method

To find the HCF of the given numbers using the prime factorization method, follow the steps given below:

• Step 1: Find the prime factors of the given numbers using the repeated division method or factor tree method.
• Step 2: Write the prime factors in their exponent forms.
• Step 3: Identify the common factors from the prime factorization of the given numbers.
• Step 4: Multiply the common factors, with the smallest exponent of each factor.
• Step 5: The final result after multiplication will be the HCF of the given numbers.

For example, you have to find the HCF of 18, 24, and 36 using the prime factorization method.

• Prime factorization of 18 can be expressed as 2 * 3 * 3 = 21 * 32.
• Prime factorization of 24 can be expressed as 2 * 2 * 2 * 3 = 22 * 31 * 1.
• Prime factorization of 36 can be expressed as 2 * 2 * 3 * 3 = 22 * 32.

The common factors among the given numbers are 2 and 3.

So, the HCF of 18, 24, and 36 = 2 * 3 = 6.

3. Factors Method

Factors Method To find the HCF (Highest Common Factor) of the given numbers using the factors method, you can follow the following steps:

• Step 1: Write down the prime factors of each given number.
• Step 2: Identify the common prime factors of all the numbers.
• Step 3: Multiply the common prime factors found in Step 2. The product will be the HCF of the given numbers.

For example, you have to find the HCF of 12 and 18 using the factors method.

• Prime factors of 12 are 2 x 2 x 3 = 2^2 x 3
• Prime factors of 18 are 2 x 3 x 3 = 2 x 3^2

Here, the common prime factors of both numbers are 2 and 3. Multiplying these common prime factors gives 2 x 3 = 6, which is the HCF of 12 and 18.

So, the HCF of 12 and 18 is 6.

Important HCF Formulas

1. Formula for finding the HCF of two integers.

Let A and B be two given integers. So, the HCF of A and B can be calculated using the formula:

HCF (A, B) = HCF (B, A%B),

where A%B is the remainder obtained when A is divided by B using the modulo operator.

2. Formula for finding the HCF of three integers :

Let A, B, and C be three given integers. So, the HCF of A, B, and C can be calculated using the formula:

HCF (A, B, C) = HCF (HCF (A, B), C).

That is, the HCF of three numbers can be calculated by finding the HCF of the first two numbers and then finding the HCF of that result and the third number.

3. Formula for finding the HCF of fractions:

Let a/b and c/d be two given fractions. So, the HCF of the two fractions can be calculated using the formula:

HCF (a/b, c/d) = HCF (a, c) / LCM (b, d),

where LCM is the least common multiple of the denominators of the two fractions.

4. Formula for finding the HCF of more than two numbers:

Let a1, a2, a3, …, an be n given integers. So, the HCF of these n numbers can be calculated using the formula :

HCF (a1, a2, a3, …, an) = HCF (HCF (a1, a2), a3, …, an).

That is, the HCF of n numbers can be calculated by finding the HCF of the first two numbers and then finding the HCF of that result and the third number, and so on, until all n numbers have been included.

Knowing these formulas can be useful in various mathematical calculations, such as simplifying fractions, solving number theory problems, and determining the highest common factor of multiple integers or fractions.

Solved Example Problems

Method: Factors Method (Listing)

Question 1 : Find the HCF of 12 and 18 using the listing factors method.

Solution:

• List the factors of 12: 1, 2, 3, 4, 6, 12
• List the factors of 18: 1, 2, 3, 6, 9, 18
• The common factors of 12 and 18 are: 1, 2, 3, 6
• Therefore, the HCF of 12 and 18 is 6.

Method: Division Method

Question 2 : Find the HCF of 24 and 36 using the division method.

Solution:

• Divide the larger number by the smaller number: 36 ÷ 24 = 1 with a remainder of 12
• Divide the smaller number by the remainder: 24 ÷ 12 = 2
• Divide the remainder by the quotient: 12 ÷ 2 = 6
• Therefore, the HCF of 24 and 36 is 6.

Method: Prime Factorization Method

Question 3: Find the HCF of 15 and 25 using the prime factorization method.

Solution:

• Prime factorize 15: 3 × 5
• Prime factorize 25: 5 × 5
• The common prime factor of 15 and 25 is 5.
• Therefore, the HCF of 15 and 25 is 5.

Looking to Learn Math? Book a Free Trial Lesson and match with top Math Tutors for concepts, homework help, and test prep.

FAQs