Highest Common Factor

Highest Common Factor

HCF or the Highest Common Factor of two numbers is the largest number that can divide both the numbers exactly. HCF is also known as Greatest Common Divisor (GCD) or Greatest Common Factor (GCF). Simply put, if ‘c’ is the HCF of ‘a’ and ‘b’, then there is no number greater than ‘c’ which can divide both ‘a’ and ‘b’ without any remainder. For Example, the HCF of 40 and 60 is 20. This means, there is no natural number higher than 20 which can divide both 40 and 60 without leaving a remainder.

There are 3 methods to calculate HCF

1. Calculation of HCF by factorization
2. Calculation of HCF by prime factorization
3. Calculation of HCF by Long division

Calculation by Factorisation:

In this method, we calculate the HCF by listing out the factors of each number and then picking out the common factors of those numbers. The highest of the common factors is the HCF of the numbers.

To better understand it, let us take an example where we calculate the HCF of 45 and 60.

Now, the factors of 45 are  1×45, 3×15 , and5×9.

The factors of 60 are1×60, 2×30, 3×20 , 4×15, 5×12, 6×10.

Of the various factors of 45 and 60. 3, 5, and 15 were the common factors and 15 is the highest common factor of them all. Hence, the HCF of 45 and 60 is 15.

Calculation by prime factorization:

Let us understand the calculation of HCF by prime factorization method by following the below steps and obtaining the HCF of 75 and 90.

Step- 1:

Break down the numbers as the products of only prime factors.

We can break down 75 as 5 X 5 X 3 and 90 as 5 X 3 X 3 X 2.

Step- 2:

Pick out the common factors of both the numbers and multiply them. The resulting number is the HCF.

So, the common factors of 75 and 90 are 5 and 3. The product of 5 and 3 i.e. 15 is the HCF of 75 and 90.

Calculation by Long Division:

In this method, the HCF of two numbers can be calculated by dividing the bigger number by the smaller number. If there is any remainder, then the number which was earlier the divisor will now become the dividend and the remainder will become the divisor. This process is repeated until there is no remainder. When the remainder becomes zero, the last divisor is the HCF of the two numbers.

To better understand, let us take the example below and calculate the HCF of 40 and 90 using the long division method.

40 being the smaller of the two numbers will be the divisor and 90 will be the dividend.

Next, the remainder 10 will be the divisor and 40 will become the dividend.

10 being the last divisor, is the HCF of 40 and 90.

HCF by short division:

A shortcut method to calculate HCF is the short division method. HCF using the short division method can be calculated by following these steps. Let us calculate the HCF of 72 and 108 by using short division.

Step-1:

Arrange the numbers in a horizontal line.

Step-2:

Divide both the numbers using prime numbers. The prime numbers are written on the left and the quotient below. These quotients are divided by another prime number and this process is repeated until either one of them reaches 1 or to a point where there are no other common prime factors.

Step-3

Once we have reached a point where there are no more common prime factors, we shall multiply all the prime factors and the resulting product is the highest common factor.

In the above illustration,  the highest common factor is 3 X 3 X 2 X 2 = 36.

Solved Examples

1. Ramesh purchases three bags of rice with one weighing 80 Kgs, another weighing 65 Kgs and the third one weighing 75 Kgs. What is the maximum value of weight which can measure the weight of the rice an exact number of times?

Solution:

Given that the weight of three bags of rice is 80 Kgs, 65 Kgs, and 75 Kgs.

The maximum value of weight is the HCF (80, 65, 75).

The factors of 80 are  1×80, 2×40 , 4×20 , 5×16 , 8×10.

The factors of 65 are 1×65 and 5×13              

The factors of 75 are1×75, 3×25 , and 5×15

We can see that 5 is the Highest Common Factor.

Hence, the maximum value of weight that can measure the weight of the rice bags without any reminder is 5 Kg.

2. Find the highest common factor of 425 and 800 and 900 using the prime factorization method:

Solution:

The prime factors of 425 are 5 x 5 x 17

The prime factors of 800 are  5 x 5 x 2 x 2 x 2 x 2 x 2

The prime factors of 900 are 2 x 2 x 3 x 3 x 5 x 5

Thus the HCF of 425, 800, and 900 is 5X5 = 25.

3. Find the HCF of 56 and 32 using the long division method

Solution:

8 being the last divisor, is the Highest Common Factor of 32 and 56.

4. Find the Largest number that divides 241 and 313 and leaves a remainder of 7.

Solution:

Since it is given that when the factor divides both 241 and 313, there is a remainder of 7. This means that while 241 and 313 are not completely divisible by the factor, the closest number that is completely divisible by the factor is 7 less than 241 and 313. so, 234 and 306 are completely divisible by the factor. Hence, we should calculate the HCF of 234 and 306.

Prime factors of 234 are 2 X 3 X 3 X 13

Prime factors of 306 are 2 X 3 X 3 X 17

The common prime factors are 3, 3, and 2. The HCF is 3 X 3 X 2 = 18