LCM and HCF


LCM or Least common factor:

LCM is defined as the least number which is divisible by all the given divisors.  Take 4,6 as two divisors which divide 12, 24, 36... perfectly with no remainder.  So 12, 24, 36 are called common multiples of 4 and 6.  In other words, 4 and 6 are factors of all these number.  Of all these common multiples, 12 is the least number.  So we can say 12 is Least common multiple of all the given numbers or LCM of 4, 6.

Finding LCM: 

There are two ways to find LCM.  First one is division method, second one is Factorization method.  
1. Division Method: LCM of 15, 18, 27


In division method we have to continue the division until the numbers in the last row become co - primes with each other.  So LCM = 3 x 3 x 5 x 2 x 3 =270

2. Factorization Method: 
Here we can write all the given numbers in their prime factorization format.
15 = 3 x 5
18 = $2 \times {3^2}$
27 = ${3^3}$
Now take all primes number the given numbers and write their maximum powers. So LCM of 15, 18, 27 = $2 \times {3^3} \times 5$ = 270

Formula 1: If r is the remainder in each case when N is divided by x, y, z then the general format of the number is N= K x [LCM (x, y, z)] + r here K is a natural number

Example: A teacher when distributed certain number of chocolates to 4 children, 5 children, 7 children, left with 1 chocolate.  Find the least number of chocolates the teacher brought to the class
Ans:  N = K (LCM (4, 5, 7) + 1 = 140K + 1.  Where K = natural number.  When we substitute K = 1, we get the least number satisfies the condition. So minimum chocolates = 141
 
Formula 2: If ${x_1},{y_1},{z_1}$ are the remainders when N is divided by x, y, z and $x - {x_1} = y - {y_1} = z - {z_1} = a$ then the general format of the number is given by N= K x [LCM (x, y, z)] - a

Example: When certain number of marbles are divided into groups of 4, one marble remained.  When the same number of marbles are divided into groups of 7 and 12 then 4, 9 marbles remained. If the total marbles are less than 10,000 then find the maximum possible number of marbles.
Ans:  In this case the difference between the remainders and divisors is constant.  i.e., 3. so  N = K (LCM (4, 7, 12) -  3 = 84K - 3.  Where K = natural number.  
But we know that 84K - 3 < 10,000 $ \Rightarrow $ 84 x 119  - 3 < 10,000 $ \Rightarrow $ 9996 - 3 = 9993

Highest common factor (HCF)or Greatest common divisor (GCD): 

HCF is the maximum divisor which divides all the given numbers exactly.  Let us say for 16, 24 there are several numbers i.e., 1, 2, 4, 8 divide them exactly. Of all these numbers 8 is maximum number so we could call 8 as HCF

Finding HCF:  
HCF can be found in two ways. Division Method and Factorization method.

Example: Find the HCF of 16, 24
Factorization Method: 
We need to write each number in its prime factorization format and take the prime numbers common to all given numbers and their minimum power.
$16 = {2^4}$,  $24 = {2^3} \times 3$
Now HCF of 16, 24 = ${2^3}$ ( we must not consider 3 because 16 does not contain the prime factor 3)

Division Method: 

Important formulas: 

Formula 3: if a, b, c are the remainders in each case when A, B, C are divided by N then N = HCF (A-a, B-b, C-c)

Example: Find the greatest number, which will divide 260, 281 and 303, leaving 7, 5 and 4 as remainders respectively.  
Ans: We have to find the HCF of (260 - 7, 281 - 5, 303 - 4) = HCF (253, 276, 299) = 23

Formula 4: When A, B, C are divided by N then the remainder is same in each case then N = HCF of any two of (A-B, B-C, C-A)

Example: Find the greatest number by which if we divide 740, 838 and 985, then in each case the remainder is the same.
 Ans: Given number is HCF (838 - 740, 985 - 838) = 49

Important result:
If we divide the given numbers with their HCF, the quotients must be co-primes with each other.  
Let us assume two numbers A, B.   Take A = ah and B = bh where a,b are co-primes with each other and h is the highest common factor of the two numbers. 
Now LCM (A, B) = abh.  (because h is the HCF of two given numbers, when we divide A, B with h, the quotients are coprimes. So LCM is equal to the product of h, a, b).
Now we can observe that A x B = ah x bh = abh x h = LCM (A, B) x HCF (A, B)

This is a very important result.  The product of two numbers is equal to the product of LCM and HCF of the two given numbers.

Solved Examples

1. LCM of $\displaystyle\frac{2}{7},\displaystyle\frac{3}{{14}}{\rm{ and }}\displaystyle\frac{5}{3}{\rm{ is}}$
a. 45
b. 35
c. 30
d. 25
Correct Option: C
Explanation:
$\dfrac{\text{LCM of numerators}}{\text{HCF of denominators}}$ = $\dfrac{\text{LCM of 2, 3, 5}}{{HCF of 7,14, 3}}$ = $\dfrac{{30}}{1} = 30$

2. About the number of pairs which have 16 as their HCF and 136 as their LCM, the conclusion can be
a. only one such pair exists
b. only two such pairs exist
c. many such pairs exist
d. no such pair exists
Correct Option: D
Explanation:
HCF is always a factor of LCM. ie., HCF always divides LCM perfectly.

3. The HCF of two numbers is 12 and their difference is also 12. The numbers are
a. 66, 78
b. 94, 106
c. 70, 82
d. 84, 96
Correct Option: D
Explanation:
The difference of required numbers must be 12 and every number must be divisible by 12. Therefore, they are 84, 96.

4. The HCF of two numbers is 16 and their LCM is 160.  If one of the numbers is 32, then the other number is 
a. 48
b. 80
c. 96
d. 112
Correct Option:b
Explanation:
The number = $\displaystyle\frac{{{\rm{HCF \times LCM}}}}{{{\rm\text{Given number}}}}{\rm{ = }}\displaystyle\frac{{{\rm{16 \times 160}}}}{{{\rm{32}}}}{\rm{ = 80}}$

5. HCF of three numbers is 12. If they are in the ratio 1:2:3, then the numbers are
a. 12,24,36
b. 10,20,30
c. 5,10,15
d. 4,8,12
Correct Option: A
Explanation:
Let the numbers be a, 2a and 3a.
Then, their HCF = a  so a=12
The numbers are 12,24,36

6. 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. 4
b. 10
c. 15
d. 16
Correct Option: D
Explanation:
LCM of 2,4,6, 8,10 and 12 is 120. So, the bells will toll simultaneously after 120 seconds.
i.e.2 minutes. In 30 minutes, they $\left( {\displaystyle\frac{{30}}{2} + 1} \right)$ toll times ie.16 times.

7. The largest natural number which exactly divides the product of any four consecutive natural numbers is :
a. 6
b. 12
c. 24
d. 120
Correct Option: C
Explanation:
The required number can be find out by following way.
$1 \times 2 \times 3 \times 4 = 24$

8. LCM of 87 and 145 is :
a. 870
b. 1305
c. 435
d. 1740
Correct Option: C
Explanation:
87 = 29 x 3
145 = 29 x 5
So LCM = 29 x 3 x 5 = 435

9. The traffic lights at three different road crossing change after every 48 sec; 72 sec; and 108 sec., respectively.  If they all change simultaneously at 8:20:00 hrs, then they will again change simultaneously at
a. 8:27:12 Hrs
b. 8:27:24 Hrs 
c. 8:27:36 Hrs
d. 8:27:48 Hrs
Correct Option: A
Explanation:
The change of interval=(LCM of 48,72,108)sec.=432. So, for every 432 seconds i.e.7 min. 12 sec. the lights will change.  So add 7 min.12 sec.to 8:20:00 Hrs.i.e.8:27:12 Hrs.

10. The greatest number by which if 1657 and 2037 are divided the remainders will be 6 and 5 respectively is
a. 127
b. 235
c. 260
d. 305
Correct Option: A
Explanation:
The needed number is HCF of (1657-6) and (2037-5)=HCF of 1651 & 2032=127.

11.The total number of prime factors of the product ${(8)^{20}} \times {(15)^{24}} \times {(17)^{15}}$ is
a. 59
b. 98
c. 123
d. 4
Correct Option: D
Explanation:
The prime numbers are 2,3,5,17 in the expression.  The expression can be written as ${({2^3})^{^{20}}} \times {(3 \times 5)^{24}} \times {(17)^{15}}$ $\Rightarrow $ ${2^{60}} \times {3^{24}} \times {5^{24}} \times {17^{15}}$
So number of prime factors are 4. i.e., 2, 3, 5, 17

12. The HCF and LCM of two numbers are 44 and 264 respectively. If the first number is divisible by 3, then the first number is
a. 264
b. 132
c. Both a and b
d. 33
Correct Option: C
Explanation:
Let the numbers are ah, bh respectively.  Here h is HCF of two numbers.  (obviously a, b are coprimes i.e., HCF (a, b) = 1)
Given that HCF = h = 44 and LCM = abh = 264
Dividing LCM by HCF we get ab = 6.
ab can be written as 1 x 6, 2 x 3, 3 x 2, 6 x 1.
But given that the first number is divisible by 3. So only two options possible for A. 3 x 44, 6 x 44. So option C is correct

13. What least number must be subtracted from 1294 so that the remainder when divided 9, 11, 13 will leave in each case the same remainder 6 ?
a. 0
b. 1
c. 2
d. 3
Correct Option: B
Explanation:
LCM of 9,11,13 is 1287. Dividing 1294 with 1287, the remainder will be 7, to get remainder 6, 1 is to be deducted from 1294 so that 1293 when divided by 9,11,13 leaves 6 as remainder.

14. The least number which is divisible by 12, 15, 20 and is a perfect square, is
a. 400
b. 900
c. 1600
d. 3600
Correct Option: b
Explanation: 
LCM = 5 × 3 × 22 = 60

To make this number as a perfect square, we have to multiply this number by 5 × 3
The number is 60 × 15= 900
15. The least perfect square number which is divisible by 3,4,5,6 and 8 is
a. 900
b. 1200

c. 2500
d. 3600

Correct Option: D
Explanation: 
LCM = $2 \times 2 \times 2 \times 3 \times 5 = {2^3} \times 3 \times 5$
But the least perfect square is = ${2^3} \times 3 \times 5 \times (2 \times 3 \times 5) = {2^4} \times {3^2} \times {5^2} = 3600$  as the perfect squares have their powers even.

16. Three piece of timber 42 m, 49 m and 63 m long have to be divided into planks of the same length. What is the greatest possible length of each plank?
a. 7 m
b. 14 m
c. 42 m
d. 63 m
Correct Option: A
Explanation:
The maximum possible length = (HCF of 42, 49, 63) = 7

17. The greatest number which can divide 1354, 1866, 2762 leaving the same remainder 10 in each case is :
a. 64
b. 124
c. 156
d. 260
Correct Option: A
Explanation:
The needed number = HCF of 1344, 1856 and 2752=64

Level 2 Questions


1.  Find the value of $\displaystyle\frac{{LCM{\rm{  (1, 2, 3, 4,}}.........{\rm{100)}}}}{{LCM{\rm{  (51, 52, 53, }}......{\rm{100)}}}}$
Solution:
LCM is defined as the product of all the prime numbers with maximum powers in the given numbers. There are 25 primes below 100 and we need to consider all the prime number where they take their maximum power.
LCM of (1, 2, 3, .........100) = ${2^6} \times {3^4} \times {5^2} \times {7^2} \times 11 \times 13.............97$
so LCM of (51, 52, 53, ...........100) = ${2^6} \times {3^4} \times {5^2} \times {7^2} \times 11 \times 13.............97$
For example 2 takes its maximum power 6 in 64. i.e., ${2^6}$.  Similarly 3 takes its maximum power 4 in 81. i.e., ${3^4}$.  so 
Now to find the LCM of (51, 52, 53......100) we need to consider the prime numbers up to 100 as 100 is the maximum number.  Again we can find the maximum power of 2 is 6 in 64. for 3 it is 4 in 81. for 5 it is 2 in 75 or 100...
$\displaystyle\frac{{LCM{\rm{  (1, 2, 3, 4,}}.........{\rm{100)}}}}{{LCM{\rm{  (51, 52, 53, }}......{\rm{100)}}}}$ =  $\displaystyle\frac{{{2^6} \times {3^4} \times {5^2} \times {7^2} \times 11 \times 13.............97}}{{{2^6} \times {3^4} \times {5^2} \times {7^2} \times 11 \times 13.............97}}$= 1

2. Find the number of combinations of (a, b, c) if LCM (a, b) = 1000, LCM (b, c) = 2000, LCM (c, a) = 2000
Solution: 
LCM (a, b) = ${2^3} \times {5^3}$
LCM (b, c) = ${2^4} \times {5^3}$
LCM (c, a) = ${2^4} \times {5^3}$
Let a = ${2^p} \times {5^s}$
b = ${2^q} \times {5^t}$
c = ${2^r} \times {5^u}$
Calculation for powers of 2:
Maximum power of 2 is 4 in LCM (c, a). So r is 4.  and either p or q will take 3 and other will take 0, 1, 2, 3.
r = 4;  p = 3;  q = 0, 1, 2, 3
r = 4;  p = 0, 1, 2;  q = 3,
Total combinations are (4,3,0), (4, 3, 1), (4, 3, 2), (4, 3, 3) and (4, 0, 3), (4, 1, 3), (4, 2, 3). 
Total options for powers of 2 = 7
Calculation for powers of 5:
Maximum power of 5 is 3.  So any 2 of s, t, u have maximum power 3.  and other will take 0, 1, 2, 3
a = 3, b = 3, c  = 0, 1, 2, 3
a = 0, 1, 2; b = 3;  c= 3, 
a = 3; b = 0, 1, 2; c = 3
Total options are 7 x 10 = 70

3. The letters A, B, C, D, E, F and G represent distinct digits chosen from (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) such that A*B*C = B*G*E = D*E*F, where ‘*’ means multiplication.  What does the letter G represent?
Solution:
Assume A*B*C = B*G*E = D*E*F = X then A, B, C, D, E, F, G all divides X exactly.  That means, X is the LCM of all these digits.  LCM of (1, 2, 3, 4, 6, 8, 9) = 72
As A*B*C = B*G*E = D*E*F - - - -  (i), so each expression must posses those numbers whose integral multiple or sub-multiples is/are possessed by the other expressions. Thus 0, 5 & 7 are ruled out.
But 72 = 1 x 8 x 9 = 2 x 4 x 9 = 6 x 4 x 3
Here 4, 9 appeared two times so these values take B, E in some order so G = 2
We can't determine the remaining values uniquely.