HCF and LCM Concepts Formulas and Problems for CAT Exam

HCF and LCM is another very important topic from the number system. The concept is not just restricted to the number system but is also helpful in solving some questions from arithmetic which is a very important topic for CAT exam.

In this article, we will take the topic from basics and will try to understand the various types of problems which require HCF and LCM concepts. Many questions on HCF and LCM from CAT exam are solved by applying direct formulas and tricks. As and when we come across such questions, we will also take note of those formulas.

Before we understand the concepts, we have to understand what are multiples and factors.

The concept of multiples and factors

If X, Y, and Z are three natural numbers and X x Y = Z, then

• X and Y are called the factors of Z.
• Z is said to be divisible by X and Y.
• Z is said to be a multiple of X and Y.

Example: The set of positive Integers which are factors of 18 is (1, 2, 3, 6, 9, 18).

Proper factors

A factor of a number other than 1 and the number itself is called a proper factor.

Taking the previous example, the set of proper factors of 18 is (2, 3, 6, 9).

Let us also understand the relationship between multiples and factors with divisors and dividends.

Consider a number A which is exactly divisible by B.

That is,

Then, A = B x C, where B is the divisor, and also a factor of A, and A is the dividend and also the multiple of B. Thus, 4 is a factor of 20 and 20 is a multiple of 4.

Having understood what multiples and factors are, now let us try to understand the definition of HCF and LCM

Basic Concepts of H.C.F. and LCM

It is the highest factor common to two or more numbers under consideration. It Is also called GCF or GCD (Greatest Common Factor or Greatest Common Divisor). e.g. HCF of 4 and 8 = 4, HCF of 125 and 200 = 25.

To find the HCF of the given numbers

1. Break the given numbers into their prime factors.
2. The HCF will be the product of all the prime factors common to all the numbers.

Let us learn the process of finding HCF with the help of some solved examples.

Question: Find the HCF of 96, 36 and 18.

Solution:

96 =2x 3x2x2x 2×2

36 = 2 x 3 x 2 x 3

18 = 2 x 3 x 3

Therefore, the HCF of 96, 36 and 18 is the product of the highest number of common factors in the given numbers i.e., 2 x 3 = 6. In other words, 6 is the largest possible integer, which can divide 96, 36 and 18 without leaving any remainder.

Question: Find the HCF of 42 and 70.

Solution:

42 = 3 x 2 x 7

70 = 5 x 2 x 7

Hence, HCF is x 7 = 14.

Question: Find the HCF of numbers 144, 630 and 756

Solution:

144 = 2⁴ x 3²

630 =2×3²x 5 x7

756 = 2² x 3³ x7

Hence, HCF of 144, 630, 756 = 2 x 3² = 18.

Method of finding L.C.M

The Least Common Multiple of two or more numbers is the smallest number which is exactly divisible by all of them. In other words, it is the product of the highest powers of all the prime factors of the given numbers.

To find the LCM of given numbers:

1. Break the given numbers into their prime factors.
2. The LCM will be the product of the highest power of all the factors that occur in the given numbers.

Let us take some solved examples.

Question: Find the LCM of 96, 36 and 18.

Solution:

96 = 2 x 2 x 2 x 2 x 2 x 3 =2⁵x 3¹

36 = 2 x 2 x 3 x 3 = 2² x 3²

18 = 2x 3 x 3= 2¹ x 3²

Therefore, LCM of 96, 36 and 18 is the product of the highest powers of all the prime factors, i.e. 2⁵ x 3²= 32 x 9 = 288.

That is, 288 is the smallest integer which is divisible by 96, 36 and 18 without leaving any remainder.

Question: Find the LCM of 42 and 70

Solution:

42 = 3 x 2 x 7

70 = 5 x 2 x 7

Hence, LCM is 2 x 3 x 5 x 7 = 210.

Apart from the method of prime factorization, there is another method of finding the LCM of given numbers and the method is known as the long division method. This method is quite helpful in getting LCM quickly if there are three or more than three numbers.

LCM by division method

Write the numbers, separated by commas. Then divide them by prime factors in ascending order (e.g., 2, 3, 5, 7, etc.) one at a time. Then, after each division, write ‘ the quotient of each number that gets completely divided by the divisor (the prime number) below it. Leave the undivided numbers as they are. Continue doing this till you get prime factors as quotients in each column, The product of all the prime factors (divisors and quotients) will be the LCM.

Question: Find the LCM of 8, 12, 15 and 21

Solution:

Hence, LCM is 2x 2x 2x3x 5x 7= 840.

Important:

1. HCF of A, B and C is the highest divisor which can exactly divide A, B, and C.

2. LCM of A, B and C is the lowest dividend which is exactly divisible by A, B, and C.

There is one very important relationship, given below, between two numbers and their HCF and LCM. Many problems have appeared in various competitive exams based on this relationship.

Question: LCM and HCF of two numbers are 2079 and 27 respectively. If one of the numbers is 189, find the other number.

Solution: The other number will be=

Hence, the required number =

Question: Two numbers are in the ratio 3: 5 and their LCM is 1500. Find the HCF of the numbers.

Solution:

Let the two number be 3X and 5X.
Hence their HCF = X using the formula given above, we get LCM = 3×5×X=15X

Or, 15X=1500 => X=100.

Therefore, the HCF of the numbers is 100

HCF and LCM of fractions

We can use the following direct formula.

HCF of fractions =

Similarly, LCM of fractions =

Question: Find the HCF and LCM of the two fractions 6/9, 12/15.

Solution:

The numerators are 6 and 12, their HCF = 6 and LCM =12

The denominators are 9 and 15, their LCM = 45 and HCF=3

Hence, the required HCF = and the LCM = 12/3=4.

HCF and LCM of polynomials

We apply the same method of factorization for finding the HCF and LCM of two or more polynomial expressions.

Let us understand the working with an example:

Question: the HCF of two polynomials is (x + 3), and their LCM is . If one of the polynomials is , then find the other polynomial.

Solution:

On factorizing,

Similarly,

From the question, HCF of the two polynomials = (x+3).

Let the other polynomial be P(x)

We can apply the formula for two numbers and their HCF and LCM. Here in case of numbers, it will be polynomial expressions. That is, the product of two polynomials will be equal to the product of their HCF and LCM.

Hence, P(x) = (x-1)(x-2) =

Let us see some word problems in which we use the concepts of HCF and LCM to solve them:

Tolling of bells at the same time

Question: Six bells commence tolling together and toll at intervals of 2, 4, 6, 8 10 and 12 seconds respectively. In 30 minutes, how many times do they toll together?

Solution:

In this question, we have to find the least number which is divisible by 2, 4, 6, 8 10 and 12. and that number has to be the LCM of the given six numbers.

LCM (2, 4, 6, 8, 10, 12) = 120.

That means the first time all six Bells toll together is 120 seconds or 2 minutes.

Therefore, in 30 minutes they will toll =30/2=15 times.

Question: There are two clocks, one beat 96 times in 5 minute and the other beat 48 times in 7 minutes. If they beat together exactly at 10 am when do they next beat together?

Solution:

The time for each beat is 5/96 minutes and 7/48 minutes, or 5/96 minutes and 14/96 minutes.

The LCM of numerators = 70

The HCF of denominators = 90

Therefore, the LCM of the fraction =

Hence, they will next beat together at 35/48 minutes past 10 am.

Finding the greatest or the largest common length

Question: Three pieces of string with lengths  , 6 cm and are cut into pieces that are all equal in length. The greatest length these pieces can have is

Solution:

The greatest length will be the HCF of these three numbers. By applying the method of finding the HCF of the fractions, we will get the HCF = .

Application of LCM in Time and Work Problems

We frequently use the LCM method as a trick to solve problems on Time and Work. Here is one such elementary example.

Question: Rakesh and Brijesh alone can do a work in 12 days and 15 days respectively. In how many days they can complete the work if they work together?

Solution:

Let us assume that the work = LCM (12, 15) = 60 units.

Units of work Rakesh can do in one day = 60/12=5 units

Similarly, units of work Brijesh can do in one day = 60/15 = 4 units.

Therefore, together in one day, they can complete 5+4=9 units of work.

Hence, the total time taken by then to complete the work = 60/9 = 20/3 days.

Problems on circular races

Circular Races Concepts and CAT Problems

Watch circular races concept

Question: Santa and Banta start running simultaneously from the same point on a circular track of length 120 meters at the speed of 10 m/s and 16 m/s respectively. In how much time they will again be together at the starting point?

Solution:

Time taken by Santa to complete one round = 120/10 = 12 sec

Similarly, the time taken by Banta to complete one round = 120/16 = 15/2 sec

Therefore, time after which both will be again at the starting point = LCM (12, 15/2) = 60 sec = 1 min.

Remainders based problems on HCF and LCM

There are generally four types of questions on finding remainders that appear in the exam; these require the concepts of HCF and LCM. Each type has a direct formula. Let us understand these formulas and their working with the help of examples, one on each type.

First formula: The greatest number that will divide A, B, and C, leaving remainders p, q, and r, respectively, is the HCF of (A-p), (B-q), and (C-r).

Question: What is the greatest number which when it divides 77, 48 and 34, leaves remainders 2, 3 and 4 respectively?

Solution:

The greatest number would be the HCF of (77 – 2), (48 – 3) and (34 – 4) =HCF (75, 45 and 30), which is 15.

Second Formula: The lowest number that is divisible by A, B, and C, leaving the same remainder “r” in each case is LCM of (A, B and C) + r.

Question: What is the least number which when divided by 48, 36 and 72 leaves remainder 3 in each case?
Solution:

The least number would be LCM of (48, 36 and 72) + 3. LCM = 144. Hence, the required number is 144 + 3 = 147.

Third formula: The greatest number that will divide p, q and r leaving the same remainder in each case, then required number = HCF of the absolute values of (p-q), (q-r), and (r-p).

Question: Find the greatest number that will divide 65, 81, and 145 leaving the same remainder in each case.

Solution:

Required number = HCF of (81-65), (145-81), and (145-65)

= HCF of 16, 64, and 80 = 16.

Fourth Formula: If we have to find the least number which when divided by a, b, and c, leaves the same remainder p, q, and r respectively, then if it is observed that

(a-p) = (b-q) = (c-r) = k (say), then the required number = (LCM of a, b, and c)-k.

Question: Find the least number which when divided by 6, 7 and 9 leaves the remainder 1, 2 and 4 respectively

Solution:

Here we observe that (6-1)=(7-2)=(9-4)=5.

Therefore, by applying the formula we get the required number = (LCM of 6,7 and 9) -5 = 126-5=121

HCF of the numbers in the form (a^m-1) and (aⁿ-1)

Direct Formula: HCF =

Question: Find the HCF of 2¹²⁰-1 and 2⁵⁰-1

Solution:

HCF of (120, 50) = 10.

On applying the direct formula, we get the required HCF = 2¹⁰-1.

Conclusion

In this article, we have covered the basic concepts, tricks and formula on HCF and LCM. We have covered almost every variety of problems and learned direct formulas to solve them quickly. However, there are still certain advance types of problems which are based on HCF and LCM concepts. But, such questions require advance concepts of factorization. Therefore, we will be taking those problems in a separate article on factorization.

Challenging problem: What is the sum of the digits of the least number which when divided by 6, 7 and 9 leaves remainder 4 in each case but is exactly divisible by 11.

You can try this problem and in case you get the answer, do let us know in the comment section given below.

Other Articles of Number system

• Number system syllabus and preparation tips for CAT exam
• HCF and LCM Concepts
• Number of Factors of a Number
• Concepts of Remainders
• Remainders - Fermat Theorem
• Chinese Remainder Theorem
• 3 Steps to Find Last Two Digit Numbers
• Factorials - Number of Trailing Zeros
• Base System Concepts and Questions