Concept: LCM & HCF
CONTENTS
A Factor of a given number completely divides it. Example: Factors of 6 are 1, 2, 3 and 6.
i.e., 6 is completely divisible by 1 or 2 or 3 or 6.
A Multiple of a given number is such that the number completely divides the multiple. Example: Multiples of 6 are 6, 12, 18 and 24.
i.e., 6 completely divides 6 or 12 or 18 or 24.
- A given Natural number will always have finite factors.
- A given Natural number will always have infinite multiples.
- A given Natural number is always a factor as well as a multiple of itself.
If a number 'N' is divided by 'd' giving quotient 'q' and remainder 'r', then we can form an equation:
N = d × q + r
Here,
N = Dividend
d = divisor
q = quotient
r = remainder
The Lowest Common Multiple (LCM) of 2 or more numbers is the lowest number which is divisible by all the given numbers.
Example: Let us take two numbers 4 and 6.
Multiples of 4 are 4, 8, 12, 16, 20 and so on
Multiples of 6 are 6, 12, 18, 24 and so on
We can see that the lowest common multiple is 12, i.e., 12 is the lowest number which is completely divisible by both 4 and 6.
We can calculate LCM of any given numbers by prime factorising then and taking the highest power available of all distinct prime numbers.
Example: Find LCM of 10, 12 and 15.
Solution:
Let us prime factorise 10, 12 and 15.
10 = 2 × 5
12 = 22 × 5
15 = 3 × 5
The distinct prime factors for given numbers are 2, 3 and 5
Highest power of these prime numbers i.e., 2, 3 and 5 in the given numbers is 2, 1 and 1.
∴ LCM(10, 12 and 15) = 22 × 31 × 51 = 60
Example: Find LCM of 36, 48 and 64.
Solution:
Let us prime factorise 36, 48 and 64.
36 = 22 × 32
48 = 24 × 3
64 = 26
The distinct prime factors for given numbers are 2 and 3
Highest power of these prime numbers i.e., 2 and 3 in the given numbers is 6 and 2.
∴ LCM(36, 48 and 64) = 26 × 32 = 576
A number which when divided by a, b or c leaves the same remainder r = LCM(a, b, c) × k + r
Example: Find the smallest 2-digit number which when divided by 2, 3 or 5 leaves remainder of 1.
Solution:
Let smallest such number is N.
N when divided by 2 leaves remainder of 1.
∴ N = 2 × a + 1
⇒ N - 1 = 2 × a ...(1)
N when divided by 3 leaves remainder of 1.
∴ N = 3 × b + 1
⇒ N - 1 = 3 × b ...(2)
N when divided by 5 leaves remainder of 1.
∴ N = 5 × c + 1
⇒ N - 1 = 5 × c ...(3)
From (1), (2) and (3) we can say that N - 1 is a multiple of 2, 3 and 5.
∴ N - 1 will be a multiple of LCM(2, 3, 5)
⇒ N - 1 = LCM(2, 3, 5) × k
⇒N = LCM(2, 3, 5) × k + 1
⇒ N = 30k + 1
For N to be smallest 2-digit number we put k = 1, hence N = 31.
The greatest number which when divided by a, b or c leaves remainders p, q and r respectively such that (a - p) = (b - q) = (c - r) = d (say)
then, N = LCM(a, b, c) × k - d
Example: Find the smallest 2-digit number which when divided by 2, 3 or 5 leaves remainder of 1, 2 and 4 respectively.
Solution:
Let smallest such number is N.
Here, divisors are 2, 3 and 5 while remainders are 1, 2 and 4 respectively such that
2 - 1 = 3 - 2 = 5 - 4 = 1 (d)
N when divided by 2 leaves remainder of 1.
∴ N = 2 × a + 1
⇒ N - 1 = 2 × a
Adding 2 (divisor) both sides we get
N + 1 = 2(a + 1) ...(1)
N when divided by 3 leaves remainder of 2.
∴ N = 3 × b + 2
⇒ N - 2 = 3 × b
Adding 3 (divisor) both sides we get
N + 1 = 3(b + 1) ...(2)
N when divided by 5 leaves remainder of 4.
∴ N = 5 × c + 4
⇒ N - 4 = 5 × c
Adding 5 (divisor) both sides we get
N + 1 = 5(c + 1) ...(3)
From (1), (2) and (3) we can say that N + 1 is a multiple of 2, 3 and 5.
∴ N + 1 will be a multiple of LCM(2, 3, 5)
⇒ N + 1 = LCM(2, 3, 5) × k
⇒ N = LCM(2, 3, 5) × k - 1 (d)
⇒ N = 30k - 1
For N to be smallest 2-digit number we put k = 1, hence N = 29.
The greatest number which when divided by a or b leaves remainder p and q respectively such that (a - p) ≠ (b - q)
then, N = LCM(a, b) × k + n
where, n is the smallest such number which needs to found out by a little hit and trial method.
Example: Find the highest 2-digit number which when divided by 3 or 5 leaves remainder of 1 and 4 respectively.
Solution:
Let smallest such number is n.
Here, divisors are 2 and 5 while remainders are 1 and 4 respectively such that
3 - 1 ≠ 5 - 4
n when divided by 5 leaves remainder of 4.
∴ n = 5 × a + 4
⇒ n can be 4, 9, 14, 19, 24, 29, ... etc.
Now smallest value of n which when divided by 3 gives remainder 1 is 4.
Now we can generalise, any number which when divided by 3 or 5 and gives remainders as 1 or 4 respectively (N) = LCM(3, 5) × k + 4 = 15k + 4
For N to be highest 2-digit number (N) = 15k + 4 < 100
15k < 96
k < 6.4
Highest possible value of k = 6
Highest 2-digit value of N = 15 × 6 + 4 = 94
Example: Find the smallest 3-digit number which when divided by 12 or 15 leaves remainder of 2 and 8 respectively.
Solution:
Let smallest such number is n.
Here, divisors are 12 and 15 while remainders are 2 and 8 respectively such that
12 - 2 ≠ 15 - 8
n when divided by 15 leaves remainder of 8.
∴ n = 15 × a + 8
⇒ n can be 8, 23, 38, 53, 68, 83, ... etc.
Now smallest value of n which when divided by 12 gives remainder 2 is 38.
Now we can generalise, any number which when divided by 12 or 15 and gives remainders as 2 or 8 respectively (N) = LCM(12, 15) × k + 38 = 60k + 38
For N to be smallest 3-digit number (N) = 60k + 38 > 99
⇒ 60k > 61
⇒ k > 1.01
Least possible value of k = 2
Smallest 3-digit value of N = 60 × 2 + 38 = 158
The Highest Common Factor (HCF) or Greatest Common Divison (GCD) of 2 or more numbers is the highest number which can divide all the given numbers.
Example: Let us take two numbers 4 and 6.
Factors of 4 are 1, 2 and 4
Factors of 6 are 1, 2, 3 and 6
We can see that the highest common factor is 2, i.e., 2 is the highest number which can completely divide both 4 and 6.
We can calculate HCF of any given numbers by prime factorising then and taking the smallest power available of only common distinct prime numbers.
Example: Find HCF of 12 and 18.
Solution:
Let us prime factorise 12 and 18.
12 = 22 × 3
18 = 2 × 32
The common distinct prime factors for given numbers are 2 and 3
Smallest power of these prime numbers i.e., 2 and 3 in the given numbers is 1 and 1.
∴ HCF(12 and 18) = 2 × 3 = 6
Example: Find HCF of 36, 48 and 60.
Solution:
Let us prime factorise 36, 48 and 64.
36 = 22 × 32
48 = 24 × 3
60 = 22 × 3 × 5
The common distinct prime factors for given numbers are 2 and 3
Highest power of these prime numbers i.e., 2 and 3 in the given numbers is 2 and 1.
∴ LCM(36, 48 and 60) = 22 × 3 = 12
The greatest number which divides X, Y and Z leaving remainders p, q and r = HCF[(X - p), (Y - q), (Z - r)]
Example: The greatest number which divides 53 and 68 leaving remainders 5 and 8
Solution:
Let the required number be p.
53 when divided by p leaves a remainder of 5
∴ 53 = p × a + 5
⇒ 53 - 5 = p × a
⇒ a = (53 - 5)/p ...(1)
68 when divided by p leaves a remainder of 8
∴ 68 = p × b + 8
⇒ 68 - 8 = p × b
b = (68 - 8)/p ...(2)
From (1) and (2)
Since, a and b are integers, p should completely divided (53 - 5) and (68 - 8) i.e., 48 and 60
Highest possible value of p = HCF(48 and 60) = 12.
Example: The greatest number which divides 327, 223 and 411 leaving remainders 15, 7 and 3
Solution:
Highest possible such number = HCF[(327 - 15), (223 - 7), (411 - 3)] = HCF[312, 216, 408].
312 = 23 × 3 × 13
216 = 23 × 33
408 = 23 × 3 × 17
∴HCF[312, 216, 408] = 23 × 3 = 24
The greatest number which divides X, Y and Z leaving the same remainder = HCF[(X - Y), (Y - Z), (Z - X)]
Example: The greatest number which divides 470, 545 and 410 leaving remainders 5 and 8
Solution:
Let the required number be p.
470 when divided by p leaves a remainder of say r
∴ 470 = p × a + r
⇒ 470 - r = p × a ...(1)
545 when divided by p leaves a remainder of say r
∴ 545 = p × b + r
⇒ 545 - r = p × b ...(2)
410 when divided by p leaves a remainder of say r
∴ 410 = p × c + r
⇒ 410 - r = p × c ...(3)
(1) - (3)
470 - 410 = p(a - c)
a - c = (470 - 410)/p ...(4)
(2) - (3)
545 - 410 = p(b - c)
b - c = (545 - 410)/p ...(5)
(2) - (1)
545 - 470 = p(b - a)
b - a = (545 - 470)/p ...(6)
From (4), (5) and (6)
Highest possible value of p = HCF[(470 - 410), (545 - 410), (545 - 470)] = 15
Example: The greatest number which divides 559, 415 and 343 leaving remainders 5 and 8
Solution:
Let the required number be p.
Highest possible value of p = HCF[(559 - 415), (415 - 343)] = 72
Note: Taking LCM of 2 pairs will give the same answer as taking LCM of all 3 pairs.
- For any number of numbers, LCM is always a multiple of HCF.
Let the LCM of two number 'a' and 'b' be 'L' while their HCF be 'H'.
Now 'a' = as H × x and 'b' = H × y
Since H is the highest common factor between 'a' and 'b', hence x and y will have not common factor i.e., x and y will be co-prime numbers.
Also, LCM of numbers consist of all the factors possible, hence L = H × x × y
∴ L × H = a × b
i.e., Product of two numbers is equal to product of their LCM and HCF
Note: The above relation is true only for two numbers and should not be extended to more than 2 numbers.
Example: Let us take two numbers 24 and 60.
HCF (24, 60) = 12
LCM (24, 60) = 120
Now, 12 × 120 = 1440 while 24 × 60 = 1440
Example: How many pair of numbers exist such that their HCF is 12 and LCM is 72.
Solution:
Let the required numbers be a and b.
Since their HCF is 12, a = 12x and b = 12y where x and y are co-prime numbers.
Now, product of two numbers = product of their HCF and LCM
∴ a × b = LCM × HCF
⇒ 12x × 12y = 12 × 72
⇒ x × y = 6
Now, we need to write 6 as a product of two co-prime numbers.
⇒ 6 = 1 × 6 or 2 × 3
∴ x = 12 and y = 72 or x= 24 and y = 36
⇒ 2 pair of values are possible.