# Notes: Important Concept of HCF & LCM for CAT Exam

#### Least Common Multiple( LCM)

A common multiple is one that is a multiple of 2 or more than 2 numbers.

Eg) The common multiples of 2 and 3 are 6,12,18 etc

The Least Common Multiple of 2 numbers is the smallest positive number that is a multiple of both.

In other words, the Least Common Multiple of 2 or more numbers is the smallest number which is divisible by all the given numbers.

Multiples of 2 ? 2,4,6,8…

Multiples of 3? 3,6,9,12…

LCM of 2 and 3 will be 6.

HOW TO FIND OUT LCM

METHOD 1-Prime Factorization Method

1) Factorize all numbers into their prime factors

2) Make a note of all the distinct factors

3) Raise each factor to the maximum power present and multiply them all

Eg 1) To find the LCM of 136,144,168

136 = 23 x17

144 = 24 x 32

168= 23x3x7 Distinct factors are 2, 17, 3 and 7.

Highest power of 2 is 4, of 3 is 2, of 17 is 1 and of 7 is 1. So, LCM = 24 x 32 x17 x7 = 17136

METHOD 2

Suppose we have to calculate the LCM of 4, 5 and 6.

Take the highest number: 6 in this case. Now start with the multiples of 6 and check whether they are the multiples of 4 and 5 or not.

The first common multiple (i.e. the multiple of all 3?4,5, and 6) will be the LCM.

You start with 6, 12, 18, 24, 30, 36, 42, 48, 54, 60 So, 60 is the LCM as it is the first number to be divisible by 4,5 and 6

ILLUSTRATION:

Eg 2) There are some boxes lying in a straight line. Every 6th box contains a muffin, every 8th contains a chocolate and every 9th contains a soft-toy. Which is the first box to have all 3 items?

a) 48 b) 36 c) 432 d) none of these

Solution

Muffins will be contained in boxes- 6, 12, 18, 24, 36….

Chocolates will be contained in boxes- 8,16,24,32….

Soft-toys will be contained in boxes- 9,18,27,36….

The first box which contains all three items, will have to be a multiple of 6, 8 and 9.

Being the first box to contain all three items, it will be the lowest multiple of all 3, which is the LCM.

LCM of 6, 8, 9 is 72. This is the answer.

?Highest Common Factor (HCF)

Greatest Common divisor (GCD), also called HCF, is the largest integer that perfectly divides two or more given numbers.

e.g. the HCF of 18 and 12 is 6.

6 is the largest number that divides both 18 and 12

HOW TO FIND OUT HCF

1) Prime Factorization Method-

? Factorize all numbers into their prime factors

? Make a note of all the distinct factors present in all three numbers

? Raise each factor to the minimum power present and multiply them all

Eg) To find the HCF of 136,144, 168

SStep 1: 136 = 23 x17 144 = 24 x 32 168= 23x3x7

Step 2: Distinct factors present = 2,3,7,17

Step 3: Raising each factor to the minimum present (i.e. 23,30,70 and 170) HCF= 23=8

2) Division Method

To find the HCF of 2 numbers by Division Method, we divide the higher number by the lower number. Then we divide the lower number by the remainder obtained in the previous division. This remainder is divided by the next remainder and so on till the remainder is zero. The last divisor will be the HCF of the two numbers

Eg) to find the HCF of 12 and 15

15/12|R = 3 12/3|R=0

Thus, the HCF= 3

HCF AND LCM OF FRACTIONS

HCF of fractions = _HCF of numerators__ LCM of denominators

LCM of fractions = _LCM of numerators__ HCF of denominators

LCM x HCF = Product of two numbers (this can be applied only for 2 numbers)

Eg 1) HCF of 12 and 24 = 12. LCM of 12 and 24= 24 HCF x LCM = 12×24 = product of the two numbers

This formula can be applied to any number of numbers only if all the numbers are relatively prime

Eg 2) HCF of 4,5 and 6 = 1. LCM of 4,5 and 6 = 120 HCF x LCM= 120×1 = 120 = Product of the numbers

Eg 3) The circumference of the wheels of a vintage car are 7/3 and 13/4 m respectively.A mark is made on each of these wheels at their point of contact with the ground.Find the distance traveled by the car before which the part of the wheels with the marks is again on the ground at the same time next time.

a) 85 m b) 183 m c) 91m d) none of these

Solution:

Option (c)

LCM of 7/3 and 13/4 gives the answer = LCM of numerators/ HCF of denominators = 91/1= 91

Properties of HCF and LCM

1) The HCF of two or more numbers is lesser than or equal to the smallest of those numbers

2) The LCM of two or more numbers is greater than or equal to the greatest of those numbers

3) If a number X always leaves a remainder R when divided by the numbers A,B,C.. ,then X= LCM(or a multiple of LCM) of A,B,C…+R

ILLUSTRATIONS

4 ) Find the highest number less than 2000 which is divisible by all of 4,6,8,10 and 12

Find the LCM of 4,6,8,10 and 12 = 120 A multiple of 120 less than 2000= 1920 thus,

this is the number which is divisible by 4,6,8,10 and 12

5) Find the largest 4 digit number divisible by 45, 50 and 30

45=5×32 50=52×2 30=2x3x5 LCM of 45,50 and 30 =52x2x32 = 450 Largest 4 digit number = 9999 9999/450 leaves a remainder of 99 Thus, 9999-99=9900

9900 is the largest number divisible by 450, and thus; the largest number divisible by 45,50 and 30

6) Find the least 3 digit number which will give a remainder of 6 when divided by 8,9 and 10?

Take the LCM of 8,9 and 10 = 360.

The least number which gives a remainder of 6 when divided by 8,9 and 10 = 360+6=366

7) There is a number N which when divided by 3,5,7 and 9 leaves a remainder of 1, but leaves a remainder of 7 when divided by

8. Find the least such number possible

First find the least number which leaves a remainder of 1 when divided by 3,5,7 and 9

LCM (3,5,7,9)=315. The first number in this sequence=315+1=316

The next number in this sequence will be 316+LCM of (3,5,7,9= 315)= 631

631 leaves a remainder of 1 when divided by 8. Thus the answer is 631

APPLICATION QUESTION- TIME SPEED DISTANCE

LCM finds its applications in Time Speed Distance-Circular Motion, which will be further elaborated in the topic Time Speed Distance. Here we will look at a typical problem based on LCM

8) A is running at a speed of 10 m/s and B is running at a speed of 20 m/s around a circular track of length 500 m in the same direction. After how much time will they be at the starting point together for the first time if they start running at the same time.

Solution

They will meet at the LCM of the time taken by both of them to run around the circle

Time taken by A to run around the circle once= distance/speed = 500/10= 50s

Time taken by B to run around the circle once= distance/speed= 500/20= 25s

LCM= 50, thus they will be together after 50 seconds

APPLICATION QUESTION-TIME AND WORK

LCM finds its applications in Time and Work, which will be further elaborated in the topic Time and Work. Here we will look one typical Time and Work problem based on the concept of LCM

9) A can do a piece of work in 5 days. B can do the same piece of work in 6 days. How long will they take to do the work together?

Let us assume the total units of work = a multiple of both 5 and 6 =LCM(5,6) =30 units

Hence, A does 30/5= 6 units of work per day And B does 30/6= 5 units of work per day

Together they will do 6+5=11 units of work per day

Thus they will take 30/11 = 2 8/11days to do the work together

## Some important l.c.m. and h.c.f. tricks:

1) Product of two numbers = Their h.c.f. * Their l.c.m.
2) h.c.f. of given numbers always divides their l.c.m.

3) h.c.f. of given fractions =     h.c.f. of numerator
l.c.m. of denominator

4) l.c.m. of given fractions =    l.c.m. of numerator
h.c.f. of denominator

5) If d is the h.c.f. of two positive integer a and b, then there exist unique integer m and n, such that
d = am + bn

6) If p is prime and a,b are any integer then ,This implies   P or P
ab                         a      b

7) h.c.f. of a given number always divides its l.c.m.

## Most important points about l.c.m. and h.c.f. problems :

1) Largest number which divides x,y,z to leave same remainder = h.c.f. of y-x, z-y, z-x.
2) Largest number which divides x,y,z to leave remainder R (i.e. same) = h.c.f of x-R, y-R, z-R.

3) Largest number which divides x,y,z to leave same remainder a,b,c  = h.c.f. of x-a, y-b, z-c.

4) Least number which when divided by x,y,z and leaves a remainder R in each case = ( l.c.m. of x,y,z) + R

## HCF and LCM questions:

Problem 1: Least number which when divided by 35,45,55 and leaves remainder 18,28,38; is?
Solution: i) In this case we will evaluate l.c.m.
ii) Here the difference between every divisor and remainder is same i.e. 17.
Therefore, required number = l.c.m. of (35,45,55)-17 = (3465-17)= 3448.

Problem 2: Least number which when divided by 5,6,7,8 and leaves remainder 3, but when divided by 9, leaves no remainder?
Solution: l.c.m. of 5,6,7,8 = 840
Required number = 840 k + 3
Least value of k for which (840 k + 3) is divided by 9 is 2
Therefore, required number = 840*2 + 3
= 1683

Problem 3: Greater number of 4 digits which is divisible by each one of 12,18,21 and 28 is?
Solution: l.c.m. of 12,18,21,28 = 254
Therefore, required number must be divisible by 254.
Greatest four digit number = 9999
On dividing 9999 by 252, remainder = 171
Therefore, 9999-171 = 9828.

Don't miss out!