Highest Common Factor (HCF) | Definition, Methods with Examples

What is Highest Common Factor?

The Highest Common Factor (HCF) of two or more numbers is the largest number that divides each of the numbers without leaving a remainder. HCF is also known as the Greatest Common Divisor (GCD).

For example, the HCF of 12 and 15 is 3, because 3 is the largest number that divides both 12 and 15 exactly.

How to Find the HCF?

There are three common methods to find the HCF of two or more numbers:

Prime Factorization Method
Listing the Factors Method
Division Method

Prime Factorization Method

This method involves expressing each number as a product of prime factors and then finding the common prime factors.

Steps:

Step 1: Write the prime factorization of each number.

Step 2: Identify the common prime factors.

Step 3: Multiply the common prime factors to find the HCF.

Example 1:

Find the HCF of 24 and 36 using prime factorization.

Prime factors of 24 = 2x2x2×3
Prime factors of 36 = 2x2×3×3

The common prime factors are $2x^{2} \times 3 = 12$ .

So, HCF(24, 36) = 12.

Example 2:

Find the HCF of 84, 126 and 210 using prime factorization.

Prime factors of 84 = 2x2x3x7
Prime factors of 126 = 2x3x3x7
Prime factors of 210 = 2x3x5x7

The common prime factors are $2x 3\times7 =42$ .

So, HCF(84, 126, 210) = 42.

The prime factorization method breaks down the numbers into their prime factors, making it easy to see the common factors and calculate the HCF.

Listing the Factors Method

This is a simple method where you list all the factors of the given numbers and find the largest common factor. This can be done easily for smaller numbers. But, as the number increases, it gets difficult to list all the factors.

Steps:

Step 1: List all the factors of each number.

Step 2: Identify the common factors.

Step 3: The largest common factor is the HCF.

Example 1:

Find the HCF of 20 and 30 by listing factors.

Factors of 20: 1, 2, 4, 5, 10, 20
Factors of 30: 1, 2, 3, 5, 6, 10, 15, 30

The common factors are 1, 2, 5, and 10. The largest common factor is 10.

So, HCF(20, 30) = 10.

Example 2:

Find the HCF of 24, 36, and 60 by listing the factors.

Factors of 24: $1, 2, 3, 4, 6, 8, 12, 24$ $1, 2, 3, 4, 6, 8, 12, 24$
Factors of 36: $1, 2, 3, 4, 6, 9, 12, 18, 36$
Factors of 60: $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$

The common factors of 24, 36, and 60 are $1, 2, 3, 4, 6 and 12.$ The highest common factor is 12.

So, the HCF(24, 36, 60) = 12.

Division Method

The Division Method of finding the HCF (Highest Common Factor) can be performed in two ways: the Long Division Method and the Short Division Method.

Long Division Method

The Long Division Method, also known as the Euclidean Method or Euclidean Algorithm, is a technique based on a mathematical principle discovered by the ancient Greek mathematician Euclid. The method is based on the fact that:

The HCF of two numbers also divides their difference.

The highest common factor (HCF) of two numbers can be found by repeatedly dividing the larger number by the smaller number and then replacing the larger number with the remainder. This process continues until the remainder is zero. The divisor at that point will be the HCF. This method is useful when working with large numbers.

Steps:

Step 1: Divide the larger number by the smaller number.

Step 2: Divide the divisor by the remainder.

Step 3: Repeat this process until the remainder becomes zero.

Step 4: The divisor at this stage will be the HCF.

Example 1:

Find the HCF of 48 and 18 using the division method.

Step 1: $48 \div 18 = 2$ (remainder 12)
Step 2: $18 \div 12 = 1$ (remainder 6)
Step 3: $12 \div 6 = 2$ (remainder 0)

So, HCF(48, 18) = 6

Example 2:

Find the HCF of 252, 105, and 60 using the Long Division Method.

To find the HCF of three numbers using the Long Division Method (Euclidean Method), the steps are as follows:

Find the HCF of any two numbers.
Use the result to find the HCF with the third number.

Step 1: Find the HCF of 252 and 105

Divide 252 by 105: $252 \div 105 = 2$ (remainder = 42)

Divide 105 by 42: $105 \div 42 = 2$ (remainder = 21)

Divide 42 by 21: $42 \div 21 = 2$ (remainder = 0)

Since the remainder is zero, the HCF of 252 and 105 is 21.

Step 2: Find the HCF of 21 and 60:

Divide 60 by 21: $60 \div 21 = 2$

$60 \div 21 = 2$ (remainder = 18)

Divide 21 by 18: $21 \div 18 = 1$ (remainder = 3)

Divide 18 by 3: $18 \div 3 = 6$ (remainder = 0)

Since the remainder is zero, the HCF of 21 and 60 is 3.

Short Division Method

In the Short Division Method, we divide multiple numbers simultaneously by their common prime factors until no more common factors exist. The product of the common prime factors gives us the Highest Common Factor (HCF).

Steps:

Step 1: Divide the numbers by their smallest common prime factor.

Step 2: Continue dividing the results by common prime factors until no more common prime factors remain.

Step 3: Multiply all the prime factors used for division to find the HCF.

Example 1:

Find the HCF of 48 and 18 using the Short Division Method:

Divide both numbers by 2 (smallest common prime factor).
- $48 \div 2 = 24$ , $18 \div 2 = 9$
3 is a common prime factor for 24 and 9. Divide both 24 and 9 by 3.
- 24 $\div3=8, 9\div3=3$
There are no more common prime factors between 8 and 3, so stop.

The divisors used are 2 and 3, so the HCF is 2×3 = 6.

Example 2:

Find the HCF of 56, 98, and 126 using the Short Division Method.

Divide by the smallest common prime factor (all numbers are divisible by 2):
- $56 \div 2 = 28,$ $98 \div 2 = 49,$ $126 \div 2 = 63$
The new set of numbers is 28, 49, and 63. All these numbers are divisible by 7.
- $28\div7 =14, 49$ $\div7 =7, 63$ $\div7 =9$
Check for the next common factor. There is no common prime factor for 14, 7, and 9 (all three numbers are not divisible by the same prime number). Though 14 and 7 have 7 as the common factor, we need a number that’s a common factor for all the given numbers.
Multiply all the divisors. 2×7=14

So, the HCF of 56, 98, and 126 is 14.

Applications of HCF

Simplifying Fractions: The HCF is used to simplify fractions to their lowest terms. For example, to simplify the fraction $\frac{36}{48}$, divide both the numerator and denominator by their HCF (which is 12). This simplifies to.
Arranging Items in Groups: When organizing items into equal-sized groups without leaving any remainder, the HCF helps to determine the largest possible group size. For example, if you have 20 apples and 30 oranges and want to arrange them into the largest possible identical groups, the HCF of 20 and 30 is 10. So, we can make 2 groups of 10 apples each and 3 groups of 10 oranges each.
Tiling or Flooring Problems: The HCF is used to determine the largest possible size of square tiles that can perfectly cover a rectangular floor. If a floor is 18 feet by 24 feet, the HCF of 18 and 24 is 6. So, the largest square tiles that can cover the floor without cutting are 6 feet by 6 feet.
Distributing Items Equally: The HCF is used to equally distribute items among groups. For example, if you have 15 chocolates and 25 candies and want to distribute them equally among the maximum number of children, the HCF of 15 and 25 is 5. So, you can give 5 children 3 chocolates and 5 candies each.

HCF Practice Questions

Find the HCF of 56 and 98 using the division method.
Use prime factorization to find the HCF of 72, 108, and 144.
What is the HCF of 35 and 49?

What is Highest Common Factor?

How to Find the HCF?

Prime Factorization Method

Steps:

Example 1:

Example 2:

Listing the Factors Method

Steps:

Example 1:

Example 2:

Division Method

Long Division Method

Steps:

Example 1:

Example 2:

Short Division Method

Steps:

Example 1:

Example 2:

Applications of HCF

HCF Practice Questions

Quick Links

Contact Info