HCF / LCM Concepts by Gaurav Sharma

gaurav_sharma last edited by admin
Director, Genius Tutorials, Karnal ( Haryana ) & Delhi  MSc (Mathematics)
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 HCFProduct of two numbers is 144 and their HCF is 16, then find their LCM ?
Let the two numbers be x and y
TO FIND LCM & HCF OF FRACTIONS: First reduce each of the fractions to its lowest form and then apply the appropriate formula:
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.
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.HCF of fractions = HCF of numerators / LCM of denominators
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 2^{4 }= 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 = (x2)(x3)x^2  7x +12 = (x3)(x4)HCF of [(x2)(x3)] and [(x3)(x4)] cannot be determined as it depends upon the value of x LCM ( MODEL 1 ):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 coprime.And LCM ( a, b ) = LCM ( hx, hy ) = hxy
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 r in each case, then N will be 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, c leaves remainder m, n, p respectively when (am) = (bn) = (cp)=r, then N is of the form N=k x LCM(a, b, c)  r If N is a number which when divided by a, b leaves remainder m, n respectively.When (am) # (bn), Then N will be of the form N = k_{1}a + m = k_{2}b + 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 ):
HCF ( MODEL 2 ):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[(ap),(b−q),(c−r)]
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 = N_{1} x LCM(12,15,18 ) + 1 = 180 x N_{1} + 1 = 19 x N_{2}i.e. a multiple of 19 where N_{2} is a constant.The numbers of the form 180 N_{1} + 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 – 1If 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[(ab), (bc)]
So HCF(5^{100} 1, 25^{4}1) = HCF(5^{100}1, 5^{8} 1)= 5^{HCF(100,8 ) } 1 = 5^{4 }–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.HCF(m^{p}1, m^{q}1) = m^{HCF(p,q)} 1 Number of ways of writing a number as product of two coprimes:
If N=a^{x} * b^{y} * c^{z}, then the number of ways of writing N as a product of two coprimes are 2^{(p1)}, 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 coprimes 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 coprimes ( UNORDERED): E(N)/2
Number of ways to represent N as sum of two coprimes ( 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 coprime.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 13^{501} − 1 and 13^{501} + 1 HCF (13^{501} − 1, 13^{501} + 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 coprime 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^{(31)} = 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 coprime and LCM = HxyH(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.