CAT WHATSAPP GROUP
JOIN NOW

 +91 9988656560

The topic of HCF and LCM is an important one if you are preparing for the CAT examination. In this article we will discuss highest common factor or HCF in detail.

Highest Common Factor (HCF): As the name suggest, HCF of the given numbers is the highest number that will divide all the numbers completely. Let us take the numbers 12 and 18 to understand the meaning of HCF.

The factors of 12 are 1, 2, 3, 4, 6 and 12 and the factors of 18 are 1, 2, 3, 6, 9 and 18. The common factors of 12 and 18 are 1, 2, 3 and 6. Now, the highest among these is 6. Therefore, 6 is the highest common factor of 12 and 18 or it is the highest number that will divide 12 and 18 completely.

There are two ways to find the HCF of the given numbers.

(i) By prime factorisation: We can prime factorise the given numbers and then take out the common prime numbers with least powers and multiply them to get the HCF.

E.g., 12 = 22 × 3 and 18 = 2 × 32. Here the power of 2 and 3 that can be taken common is 1 each.

Therefore, the HCF if 12 and 18 = 2 × 3 = 6.

If you have more than two numbers, then you can prime factorise them all and take out the common terms to get the HCF.

(ii) By long division method: In this method, we take two numbers and divide the larger number with the smaller number. If the remainder comes out to be zero, then the smaller number will be the HCF.

If the remainder is non zero then we take this remainder as our next divisor and the previous divisor as our dividend and divide it. Again, if the remainder comes out to be zero then the divisor at this step will be the HCF otherwise if the remainder is again a non-zero number, then we take that number as the next divisor and the previous divisor as the new dividend and divide again. This will continue till we get the remainder zero. The last divisor which will give the remainder zero will be the HCF of the given numbers.

As in the above example, the remainder 6 in the first step becomes the divisor of the second step and the divisor 12 of the first step becomes the dividend of the second step. The divisor 6 gives us the remainder zero, hence it is the HCF of 12 and 18.

If you have three numbers and you want to find the HCF of these numbers by long division method, then first, find the HCF of any two numbers by this method and then find the HCF of the third number with the HCF of the first two numbers and get the final answer.

You can proceed in the same way, if you have more than three numbers.

Co-prime numbers: Co-prime numbers are those numbers whose HCF is one. E.g., let us take the numbers as 16 and 25. We have, 16 = 24 and 25 = 52. There is no factor common to both these numbers except 1. Hence, the HCF of 16 and 25 is 1 and they are co-prime numbers.

Note: The co-prime numbers need not to be prime numbers, but the prime numbers are always co-prime to each other.

We know that the HCF of 12 and 18 is 6 but what will be the HCF of 12 and 24?

As 24 is direct multiple of 12, so HCF will be 12. Now is it possible for HCF to be greater than the given numbers? The answer is simply no. The HCF of the given numbers can never be greater than the given numbers.

Therefore, from the HCF of 12 and 18 and the HCF of 12 and 24, we can conclude that the HCF of the given numbers is always less than the given numbers or it is equal to the smallest number.

1. Find the HCF of 60, 84 and 108.

Sol: Here 60 = 22 × 3 × 5

84 = 22 × 3 × 7

And 108 = 22 × 3 × 9

Now the prime factors with least powers that can be taken common are 22 and 3. Therefore, the HCF of the given numbers is 22 × 3 = 12.

2. Find the greatest number which when divides 226 and 379 leaves remainders 5 and 2 respectively.

Sol: Let the number is N.

As the remainder is 5 when N divides 226, therefore, 221 will be completely divisible by N.

Similarly, 379 leaves remainder 2 when divided by N, therefore, 377 is completely divisible by N.

Hence, the required number will be the HCF of 221 and 377.

Now 221 = 13 × 17 and 377 = 13 × 29.

So, the required number is 13.

3. Find the greatest number which when divides 41, 89 and 181 leaves same remainder in each case.

Sol: In these types of questions, when the same remainder is asked on dividing the numbers, then we take the pairwise difference of the numbers.

In this case, the differences are 89 – 41 = 48, 181 – 89 = 92, 181 – 41 = 140

Now the answer will be the HCF of these differences.

So, the greatest number will be HCF (48, 92, 140) = 4

4. The HCF of two numbers is 23 and their product is 6348. How many such pairs of numbers exist?

Sol: The HCF is 23, so let us take the numbers to be 23a and 23b, where a and b are co-prime.

Now, 23a × 23b = 6348 ⇒ ab = 12.

The possible value of (a, b) are (1, 12), (3, 4)

The corresponding pairs of numbers are 23, 276 and 69, 92. Hence, two pairs of numbers are possible.

5. There are 32 oranges, 216 bananas, 136 apples, 88 pears, 184 guavas which are to be packed in the boxes without mixing the fruits and each box should contain equal numbers of fruits. Find the minimum number of boxes required.

Sol: Her we have 32 oranges, 216 bananas, 136 apples, 88 pears, 184 guavas. As these fruits cannot be mixed together, so every box will have the fruits of the same type. Also, if we want to minimize the boxes, the fruits packed in them should be maximum possible.

Therefore, we need to find the HCF of (32, 216, 136, 88, 184) = 8

Hence, each box should contain 8 fruits.

So, the total number of boxes required = (32 + 216 + 136 + 88 + 184)/8 = 656/8 = 82.

Hope that the basic discussion on HCF is helpful to you in understanding the concept. IN the next article we will discuss the concept of Least Common Multiple (LCM).

Till then, Happy Learning!!!

© Copyright Quantifiers. All Rights Reserved.

Privacy Policy