# HCF / LCM Concepts by Gaurav Sharma

• LEAST COMMON MULTIPLE ( LCM ): Least common multiple of two or more numbers is the least number which is divisible by each of the numbers ‘or’ LCM of two or more expressions is the expression of the lowest dimension which is divisible by each of them.

HIGHEST COMMON FACTOR ( HCF ): Highest common factor is the largest factor of two or more given numbers ‘or’ HCF of two or more algebraic expressions is the expression of highest dimension which divides each of them without remainder.
HCF is also called GCD (Greatest Common Divisor).

GURUMANTRA:

Product of two numbers = LCM x HCF
LCM ≥ Numbers ≥ HCF
LCM is a multiple of HCF

Product of two numbers is 144 and their HCF is 16, then find their LCM ?

Let the two numbers be x and y
Then, LCM x HCF = xy
LCM = 144/16 = 9
But, LCM ≥ HCF and LCM must be a multiple of HCF.
Hence, such a situation is not possible.

TO FIND LCM & HCF OF FRACTIONS:

First reduce each of the fractions to its lowest form and then apply the appropriate formula:  HCF of fractions = HCF of numerators / LCM of denominators

Find LCM of 1/3 and 2/4

To find LCM of fractions first convert them into lowest formHere, LCM (1/3, 2/4) = LCM (1/3, 1/2) = LCM(1,1) / HCF(3,2) = 1/1 = 1

CONCEPT OF HCF & LCM USING VENN DIAGRAM:

20 = 2^2 x 5^1

30 = 2^1 x 3^1 x 5^1

LCM = 2^2 x 3^1x 5^1

HCF = 2^1 x 5^1

It can be seen that HCF is the intersection of the sets, and LCM is the union of the sets.  Let a and b be two natural numbers and h be their HCF.Then a will be of the form hx and b will be of the form hy, where x and y are co-prime.And LCM ( a, b ) = LCM ( hx, hy ) = hxy

If LCM of first 10 numbers is N, then find the LCM of first 16 numbers.

LCM must include all primes thereafter and any higher power of prime (here 24 = 16).So, answer should be N x 11 x 13 x 2

If the ratio of two numbers is 2:3 and their LCM is 54, then the sum of the two numbers is:

a) 5b) 15c) 45d) 270

Let the two numbers be 2x and 3xSo, HCF( 2x, 3x ) = x and LCM = 54Now, 54 * x = 2x * 3x-- > x = 9Hence the numbers are 18 & 27so sum is: 18 + 27 = 45

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?

a) 4b) 10c) 15d) 16

LCM of ( 2 , 4 , 6 , 8 , 10 , 12 ) = 120 = 2 minutes.So the bells toll together after every 2 minutes.Hence, 15 times in 30 minutes, but also once at the start i.e. at 0 minute. So, the toll 16 times in 30 minutes.

Three number are in the ratio of 3:4:5 and their LCM is 2400. Their HCF is:

a) 40b) 80c) 120d) 200

Let the numbers be 3x, 4x and 5x. Then HCF = x.Then, LCM(3x,4x,5x) = 3 * 4 * 5 * x = 60x-- > 60x = 2400-- > x = 40 = HCF

Find the LCM of 10, -20, -25.

LCM is defined only for positive numbers. In other words, LCM is defined only for positive fractions and natural numbers – positive numbers. In other words, LCM for negative numbers as well as zero is not defined. Hence, no LCM of 10, -20, -25 is possible.

What is the HCF of x^2 - 5x + 6 and x^2 -7x +12

x^2 - 5x + 6 = (x-2)(x-3)x^2 - 7x +12 = (x-3)(x-4)HCF of [(x-2)(x-3)] and [(x-3)(x-4)] cannot be determined as it depends upon the value of x

LCM ( MODEL 1 ):
 If N is a number which when divided by a,b,c leaves remainder r in each case, then N will be of the form N = k x LCM (a, b, c) + r.

Find the third smallest number greater than divisors which when divided by 8,10 and 12 leaves remainder 5 in each case. To find the third smallest number [LCM(8,10,12) x 3] + 5 = [120 x 3] + 5 = 365

LCM ( MODEL 2 ): If N is a number which when divided by a, b, c leaves remainder m, n, p respectively when (a-m) = (b-n) = (c-p)=r, then N is of the form N=k x LCM(a, b, c) - r

What is the least possible number which when divided by 18, 35 or 42 it leaves remainders as 2, 19 and 26 respectively?

To find the least possible number which when divided by 18, 35 or 42 leaves remainders as 2, 19 and 26 respectively, here the difference between the remainders and the divisors is 16 so number will be of the formLCM (18, 35, 42) - 16 = 630 − 16 = 614

LCM ( MODEL 3):

 If N is a number which when divided by a, b leaves remainder m, n respectively.When (a-m) # (b-n), Then N will be of the form N = k1a + m = k2b + n

Find the smallest number greater than its divisors which when divided by 9 and 11 leaves remainders 5 and 2 respectively

The smallest number greater than its divisors which when divided by 9 and 11 leaves remainders 5 and 2 respectively, will be of the form 9k + 5 and 11p + 2. So, the smallest such number is 68

The L.C.M. of two numbers is 48. The numbers are in the ratio 2:3. Then sum of the number is:a) 28b) 32c) 40d) 64

Let the numbers be 2x and 3x.Then, LCM (2x, 3x) = 6x. So, 6x = 48 or x = 8. The numbers are 16 and 24.Hence, required sum = (16 + 24) = 40.

A=997!B = 1001 x 1002 x 1003 x 1004 x 1005 x 1006Find LCM of A and B

Since all the numbers in B are composite, all of them are already included in A.So LCM(A,B ) = A = 997!

The least multiple of 7, which leaves a remainder of 4, when divided by 6, 9, 15 and 18 is:a) 74b) 94c) 184d) 364

LCM(6,9,15,18 ) = 90Let the required number be 90k + 4, which is a multiple of 7.Hence, least value of k for which 90k + 4 is divisible by 7 is k = 4.Therefore, required number = 90 x 4 + 4 = 364

A, B and C start at the same time in the same direction to run around a circular stadium. A completes a round in 252 seconds, B in 308 seconds and c in 198 seconds, all starting at the same point. After what time will they again at the starting point?a) 26 minutes and 18 secondsb )42 minutes and 36 secondsc) 45 minutesd) 46 minutes and 12 seconds

LCM(252, 308, 198 ) = 2772So, A, B and C will again meet at the starting point in 2772 sec. i.e., 46 min. 12 sec.

HCF ( MODEL 1 ):

 If is N the largest possible number with which when a, b, c are divided leaves a remainder of p, q, r respectively, then N=HCF[(a-p),(b−q),(c−r)]

HCF ( MODEL 2 ):

 If N is the largest possible number with which if we divide a, b, c then the remainders are the same.Take the difference between any two pairs out of the three given numbers and find their HCF.N = HCF[(a-b), (b-c)]

Let N be the greatest number that will divide 1305, 4665 and 6905, leaving the same remainder in each case. Then sum of the digits in N is:

a) 4b) 5c) 6d) 8

N = HCF [4665 - 1305, 6905 - 4665, 6905 - 1305]

N = HCF [3360, 2240, 5600] = 1120

Sum of digits in N = ( 1 + 1 + 2 + 0 ) = 4

The greatest number which on dividing 1657 and 2037 leaves remainders 6 and 5 respectively, is:

a) 123b) 127c) 235d) 305

Required number = HCF[(1657 - 6), (2037 - 5)]= HCF[1651, 2032] = 127Therefore, option b) is correct.

Minimum how many similar tiles of square shape are required to furnish the floor of a room with the length of 462 cm and breadth of 360 cm ?

Let the minimum number of identical square tiles , of side x cm be NN = Area of rectangular floor / x^2 = 360/x * 462/xAs the room must be perfectly covered with square tiles, x must be a factor of both 360 and 462. Hencex = HCF( 360, 462 ) = 6N = 77 * 60 = 4620

Raju has a certain number ( less than 1000 ) of chocolates with him. If he distributes then equally among a group of 12 or 15 or 18 children, he would be left with 1 chocolate in each case. If he distributes the chocolates equally among 19 children he would be left with no chocolates. How many chocolates does Raju have?a) 52b) 181c) 551d) 361

Let the number of chocolates with Raju be P.P = N1 x LCM(12,15,18 ) + 1 = 180 x N1 + 1 = 19 x N2i.e. a multiple of 19 where N2 is a constant.The numbers of the form 180 N1 + 1 less than 1000 are 1, 181, 361, 541, 721 and 901.Of these only 361 is divisible by 19.

Find the H.C.F of 5^100 -1 & 25^4 - 1

(a) 625(b) 624(c) 3024(d) 5^8 - 1(e) 5^2 – 1

 HCF(mp-1, mq-1) = mHCF(p,q) -1

So HCF(5100 -1, 254-1) = HCF(5100-1, 58 -1)= 5HCF(100,8 ) - 1 = 54 –1 = 624

Find the $LCM(2 \pi, \frac{\pi}{4})$

LCM of irrational number cannot be determined. And since $\pi$ is irrational, $LCM(2 \pi, \frac{\pi}{4})$ can’t be determined.

Number of ways of writing a number as product of two co-primes:

 If N=ax * by * cz, then the number of ways of writing N as a product of two co-primes are 2(p-1), where p is the number of primes in the prime factorisation of N

EULER OF A NUMBER:

Euler's number of a particular number is the number of co-primes less than the number.

E(N) is denoted as the Euler number.

 E(N) = N x (1−/a) x (1− 1/b) x (1− 1/c) where a, b, c are the DISTINCT primes in prime factorization of N

Example:

Let N = 36 = 2^2 x 3^2

E(36) = 36 x (1− 1/2) x (1−1/3)

= 36 x (1/2) x (2/3) = 36/3 = 12

 Let N be a natural number and E(N) be the Euler of the number N . Then, Number of ways to represent N as sum of two co-primes ( UNORDERED): E(N)/2 Number of ways to represent N as sum of two co-primes ( ORDERED): E(N)

In how many ways can we write 24 as product of two coprimes?

24 = 2^3 x 3Therefore, number of ways can we write 24 as product of two coprimes = 2^(2−1) = 2

The HCF and LCM of A and B is 18 and 2268 respectively. How many pairs of (A,B ) are possible?a) 4b) 6c) 8d) 10e) 12

Let, HCF(A,B ) = h = 18LCM(A,B ) = hxy = 18xy, where x and y are co-prime.Now, 18xy = 2268-- > xy = 126 =2 x 3^2 x 7 Number of possible solutions = 2^(3 - 1) = 2^2 = 4

L.C.M of first 120 natural numbers is x. Find the L.C.M of first 125 natural numbers in terms of x

Since there are no primes in between 120 and 125. But it do contain an extra 11 and 5.Therefore, L.C.M of first 125 natural numbers = x * 11 * 5 = 55x

Last digit of L.C.M of 13501 − 1 and 13501 + 1

HCF (13501 − 1, 13501 + 1) = 2.Last digit of the product = (3−1) x (3+1)= 2 x 4 = 8So, last digit of the LCM = 8/2 = 4

The LCM of two numbers is 2900% more than the HCF then how many pairs of such numbers exist?

Let HCF of the numbers be h.So the numbers will be of the form hx and hy where x and y are co-prime and LCM = hxyAlso according to the given questionLCM=HCF + 29 x HCF = 30 x HCFSo, hxy = 30h-- > xy = 30 = 2 x 3 x 5So, the number of possible solutions are: 2(3-1) = 4

Two natural numbers when added to their LCM, gives a total of 143. How many such pairs of numbers exists?

Let HCF of the numbers be H, so the numbers will be of the form Hx and Hy, where x and y are co-prime and LCM = Hxy

H(x+y+xy) = 143

143 = 13 x 11

Now, when H=1, we have, (x+1)(y+1) = 144So possible pairs are: (1,71),(2,47), (3,35), (5,23), (7,17), (8,15) = 6When, H=13, we have (x+1)(y+1)=12So possible pairs are: (1,5) and (2,3). so 2.When H=11, we have (x+1)(y+1)=14So possible pairs are: (1,6) so 1Hence the answer is: 6+2+1 = 9.

1

1

1

1

1

27

6

1