Home » Blog » Concepts of HCF for CAT Exam with Solved Examples

Concepts of HCF for CAT Exam with Solved Examples

Sunday, August 2nd, 2020

---

Highest Common Factor (HCF) is the largest factor of two or more numbers. The same can be defined algebraically as “ HCF of two or more algebraical expressions is the expression of highest dimension which divides each of them without remainder. HCF is also called GCD (Greatest Common Divisor).

HCF can be found either by Factorization method or Long Division Method. However, these two methods are not feasible when we have to find HCF of more than 3 numbers and the numbers are also large. In that case, we can find the differences between the numbers and they can find the HCF of differences.

Let’s understand it by a question:

1. Find the HCF of the numbers 1728, 1408, 1856, 1344.

Sol: Now to find the HCF by the above methods, you will require much calculation which is not advisable in context of time.

So, firstly find all the differences i.e. (1728-1408) = 320

(1856-1408) = 448

(1408-1344)= 64

(1856-1728) = 128

Clearly, it can be seen that the differences can’t be less than 64 so it is not necessary to find the other differences.

Now, the HCF of the above difference is easy to find and i.e 64.

You can check that 64 divides all the numbers, Hence HCF is 64.

Note: If 64 would not have to divide any of the numbers, then we would check by the factors of 64.

Various Models of Highest Common Factor (HCF)

• HCF Model1:

In this model, we have to identify the largest number that exactly divides the given dividends (which are obtained by subtracting the respective remainders from the original numbers).

“ The largest number with which the numbers p, q, or r are divided giving remainders of s, t, and u respectively will be the HCF of the three numbers (p-s), (q-t) and (r-u).”

Let us understand this model with an example.

Ques: Find the largest number with which when 72 and 119 are divided respective remainders of 3 and 4 are left.

Sol: Since 72 when divided by the number gives a remainder of 3, it means 72-3 i.e. 69 is exactly divisible by that number. Similarly, 119-4=115 is also exactly divisible by that number.

This means we have to find the HCF of 69 and 115 which is equals to 23.

• HCF Model 2:

In this model, the problem will be as follows:

“ Find the largest number with which if we divide the numbers p, q, and r, the respective remainders are same.”

Take the difference between any two pairs of the three given numbers. Let us say we take the two differences (p-q) and (p-r). The HCF of these numbers will be the required number.

Here the required number =HCF of (p-q) and (p-r)= HCF of (p-q) and (q-r)= HCF of (q-r) and (p-r).

Let us take an example and look at this model.

Ques: Find the largest number with which when 555, 1275, and 1635 are divided, the remainders are the same.

Sol: As mentioned above, take the differences between any two pairs of the three given numbers.

1275-555=720

1635-555=1080. The required number is the HCF of the two differences, i.e. HCF of 720 and 1080 which is 360.

Solved Examples on Highest Common Factor

1. How many pairs of positive integers exist such that their HCF + LCM = 91?

Sol: Let us x = h * a; y = h * b                (a&b are co-prime)
So, LCM of (x, y) = h * a * b

Therefore, h+h*a*b=91 or h(ab + 1) = 91

Now, 91 can be written as 1 * 91 or 7 * 13

Case I: HCF=1 & LCM=91

There are 4 pairs of numbers like this (2, 45), (9, 10), (1, 90) and (5, 18)

Case II: We can have HCF as 7, ab + 1 = 13 => ab = 12 => 1 * 12 or 4 * 3

The pairs would be:  (7, 84) or (21, 28)

Case III: HCF = 13, ab + 1 = 7 => ab = 6

(a, b) can be either (1, 6) or (2, 3)
The pairs possible are (13, 78) and (26, 39)

Hence, total available pairs are: 4+2+2 = 8

8 is the answer.

2. How many pairs of positive integers x, y exist such that HCF of x, y = 35 and sum of x and y = 1085?

Sol:  We can write x = 35a; y = 35b

x + y = 1085 => 35(a + b) = 1085. => (a + b) = 31.

We need to find pairs of co-prime integers that add up to 31.

Since 31 is prime. All pairs of integers that add up to 31 will be co-prime to each other.

There are totally 15 pairs that satisfy this condition.

The answer is 15.

3. Sum of two numbers x, y = 1050. What is the maximum value of the HCF between x and y?

Sol: We have given the sum of two numbers and we have to find the maximum HCF.

The HCF would be maximum when both the numbers are maximum and yield 1050 on doing sum.

So, we will divide the number in the ratio of 1: 1 i.e. we can have x = 525 and y = 525

It is not written that the numbers should be distinct. However, in the case of distinct numbers we will divide the number in the ratio 2:1 or vice versa. In that case x = 350, y = 700, HCF = 350.

The question is “What is the maximum value of the HCF between x and y?”

Hence the answer is “525”

4. There are 2 numbers such that a > b, HCF (a, b) = h and LCM (a, b) = l. What is the LCM of a – b and b?

Sol: Given a > b, HCF = h, LCM = l
From the above we can say, HCF of (a – b, b) = h

LCM x HCF = Product of 2 numbers
(a – b)b = h x LCM
LCM = (a – b) b / h

The question is “What is the LCM of a – b and b?”
Hence the answer is “(a – b) b / h”

LCM and HCF of Fractions:

For finding the LCM and HCF of Fractions, first reduce each fraction to its simplest form i.e. cancel out any common factors between numerator and denominator and then apply the formula from the following:

4 logs of woods of lengths 5 1/4 m, 1 13/15 m, 3 1/2 m and 4 9/10 m are cut into small pieces, all of which have equal length. Each piece of wood is as lengthy as possible. Each cut piece is given to a set of 2 carpenters to work on something. How many carpenters are there in all to work?

Sol: HCF of fractions

HCF (5 1/4 , 1 13/15 , 3 1/2 , 4 9/10 )

= HCF (21/4 , 28/15 , 7/2 ,49/10)

= HCF (21,28,7,49)/LCM(4,15,2,10)

= 7/60

Hence, total number of pieces

= 21/4 * 60 /7 + 28/15 * 60/7 + 7/2 * 60/7 + 49/10 * 60/7

= 45 + 16 + 30 + 42

= 133

The question is “How many carpenters are there in all to work?”

Hence the answer is “266”

Hope this post helped you figure out the concept of Highest Common Factor for CAT. Please have a look at our post related to Lowest Common Multiple (LCM) for CAT.

Other posts related to Quantitative Aptitude – Number Systems

Divisibility Rules for CAT Quantitative Aptitude Preparation
Determining the second last digit and the last two digits
Baisc Idea of Remainders
Factor Theory
How to Find Number of Trailing Zeros in a Factorial or Product
Dealing With Factorials

CAT Questions related to Quantitative Aptitude – Number Systems

All questions from CAT Exam Quantitative Aptitude – Number Systems
Quantitative Aptitude – Number Systems – Q1: If the product of three consecutive positive integers is 15600 then the sum of the squares of these integers is
Quantitative Aptitude – Number Systems – Q2: If a, b, c are three positive integers such that a and b are in the ratio 3 : 4 while b and c are in the ratio 2:1, then which one of the following is a possible value of (a + b + c)?
Quantitative Aptitude – Number Systems – Q3: The numbers 1, 2,…,9 are arranged in a 3 X 3 square grid in such a way that each number occurs once and the entries along each column, each row, and each of the two diagonals add up to the same value.

---