H.C.F. and L.C.M. 1
H.C.F. and L.C.M.
H.C.F. refers to the highest common factor, also known as G.C.D i.e. Greatest Common Divisor. We did study this topic in our schooling but might be some of you must have forgotten this concept or are unaware of its applications in mathematics. So, let’s try to understand it with an example.
Let us see the factors of two numbers, say 36 and 96.
The factors of 36 are – 1,2,3,4,6,9,12,18 and 36
The factors of 96 are- 1,2,3,4,6,8,12,16,24,32,48 and 96.
The common factors for both these numbers are :- 1,2,3,4,6 and 12.
Now, the highest among these common factors is 12 which is known as the Highest Common Factor.
Mathematically, H.C.F. is the highest number that can completely divide two or more numbers or H.C.F. is the divisor of those numbers.
Calculation of H.C.F.
a. By Prime Factorization Method:
Let us consider two numbers: 108 and 144
108 = 22 *33
144 = 24*32
Now, for finding the H.C.F., we look at the prime numbers common in both the numbers and the smallest of the exponent in any of these numbers is chosen is the exponent of these prime numbers.
In this case, we find 2 and 3 are there in both these numbers. Also the smallest exponent of 2 is 2 and the smallest exponent of 3 is also 2.
Thus, H.C.F (108,144) = 22 * 32
E.g. H.C.F. of 210 and 315
210 = 2*3*5*7
315 = 32* 5 * 7
Here, the prime numbers common in both these numbers are 3,5 and 7. The smallest exponent common for the three prime numbers in both these numbers is 1.
So, H.C.F.(210,315) = 3*5*7 = 105
b. Long Division Method
Let us say we want to find the H.C.F of (108,144)
First find the remainder on dividing 144 by 108
We get 1 as the quotient and 36 as the remainder.
Now, divide 108 by the remainder obtained i.e. 36
Now, the very moment we obtain zero, we end the process and the divisor that yields a zero is the H.C.F.
In this case, 36 is the H.C.F. of 108 and 144.
Let us say we have two numbers 108 and 144. The H.C.F. of these numbers is 36
108 = 36 *3
144 = 36 *4
Now 3 and 4 are co-prime to each other of relatively prime to each other. Co-prime numbers are those which have am H.C.F. of 1.
Thus, if the H.C.F. of two numbers is H, then we can write these numbers in form of Hx and Hy where x and y must be coprime to each other.
Example 1: The sum of two numbers is 126 while their H.C.F. is 9. How many pairs of such numbers are possible?
Solution: As the two numbers have an H.C.F. of 9, we can write these numbers as 9x and 9y
9x +9y = 126 or
x+y = 14
Now as x and y are co-prime to each other, the possible pairs are (1,13),(3,11) and (5,9).
Thus, there are three possible pairs of such numbers.
Example 2 The sum of two numbers a and b is 500. What can be the maximum H.C.F. of a and b?
Solution: Let the H.C.F. of a and b is H
Let a = Hx and b = Hy
Hx + Hy = 500
H(x+y) = 500. Now H will be a factor of 500.
As the minimum value of x and y can be 1 ,1 each. So, the minimum value of x+y is 2
Thus, the maximum H.C.F. of a and b comes out to be 250 and the two numbers are 250 and 250 each.
Example 3: A shopkeeper has six different varieties of pens A,B,C,D,E and F. He has 48 pens of A, 64 of B, 96 of C, 144 of D, 128 of E and 208 of F. He needs to pack them in boxes such that each box has the same variety of pens and the number of pens in each box also remains the same. What is the minimum number of boxes needed by the shopkeeper?
Solution: As the boxes have to be kept minimum and each box must have the same number of pens, we need to find a number that perfectly divides each of these given numbers i.e. to say we need to find the H.C.F. of these numbers and the H.C.F. will represent the number of pens kept in each of these boxes.
H.C.F. (48,64,96,144,128, 208) = 16
Boxes required for variety A = 48/16 = 3
Boxes required for variety A = 64/16 = 4
Boxes required for variety A = 96/16 = 6
Boxes required for variety A = 144/16 = 9
Boxes required for variety A = 128/16 = 8
Boxes required for variety A = 208/16 = 13
Total number of boxes required = 3+4+6+9+8+13 = 43
Example 4: Two numbers a and b are non co-prime and sum of these numbers and their H.C.F. is 77. How many pairs of (a,b) are possible?
Solution: As the numbers are non co-prime, their H.C.F must be greater than 1.
Let the two numbers be Hx and Hy
Hx + Hy +H = 77
H must be a factor of 77, so it can be either 7 or 11 (Can’t be 77 as that would mean x and y are 0 which is not possible)
Case1: H = 7
x + y + 1 = 11
Or x +y = 10
(1,9) (3,7) are the pairs possible in this case.
The numbers become (7,63) and (21,49)
Case 2: H = 11
x +y +1 = 7 or x+y = 6
(1,5) is the only pair possible as x and y must be co-prime.
So, numbers become (11,55)
So, three pairs (7,63),(21,49) and (11,55) are possible.
Lowest Common Multiple (L.C.M.)
The least common multiple or L.C.M. is the smallest number that is the multiple of a set of numbers or the smallest number which is perfectly divisible by a set of numbers.
For eg. Let us say there are three friends- Jiyan , Suneo and Nobita. They visit their friend Doreamon on a regular basis. If Jiyan visits every second day, Suneo every third day and Nobita every fourth day and starting from the 1st of the month, when is the first occasion they will together visit Doraemon?
Now, Jiyan visits Doraemon at every multiple of 2, So, he’ll be at Doraemon’s house at 2nd ,4th ,6th ,8th ,10th ,12th ,14th ,16th ,18th ,20th ,……day
Suneo will at Doraemon’s place at 3rd ,6th ,9th ,12th ,15th ,18th ,……. Day
Nobita will be at Doraemon’s place at 4th ,8th ,12th ,16th ,20th ,24th ,….. day.
Now the common day they will be at the Doraemon’s place is at the 12th day.
12 is the smallest number that is the common multiple of 2,3 and 4. Thus, it is the L.C.M. of 2,3 and 4.
Calculation of L.C.M.
Let us say there are two numbers 48 and 72.
316 = 24 * 3 * 7
72 = 23 * 32
To calculate the L.C.M., look out for prime numbers you can find in any of the numbers, here we can see the prime numbers are 2,3 and 7. Next we will look at the maximum exponent of these prime numbers. Multiply them to get the L.C.M.
Here 4 is the maximum exponent of 2, 2 is the maximum exponent of 3 and 1 is of the prime number 7.
L.C.M. (316,72) = 24*32 * 7 = 1008.
Note : This property is applicable for only two numbers.
Let’s say we have two numbers N1 and N2 and their H.C.F. is ‘H’. Now these numbers can be written in the form of Hx and Hy.
According to the property
L.C.M. * H.C.F. = N1 * N2
L.C.M. * H = Hx * Hy
Or L.C.M. = Hxy
Example 5: The H.C.F.of two numbers is 8 while their L.C.M. is 720. How many pairs of such numbers are possible?
Solution: L.C.M. = Hxy
720 = 8xy or xy = 90
As x and y are co-prime to each other, the possible pairs are (1,90),(2,45)(5,18) and (9,10).
Thus four pairs of such numbers are possible.
Example 6 : The sum of two numbers and their L.C.M. is 42. How many pairs of such numbers are possible?
Solution: Let the numbers be Hx and Hy while their L.C.M. is Hxy where x and y are co-prime to each other.
Given: Hx + Hy + Hxy = 42
H(x+y+xy) = 42
H must be a factor of 42, so H can be 2,3,6,7,14,21
Case1 : Let H = 2
X+y +xy = 21
Adding 1 to both sides of the equation, we get
(x+y+xy+1) = 22 or (x+1)(y+1) = 22
So, (10,1) is the required pair. Thus, number will be (20,2)
Case2 : H = 3
X +y +xy = 14 or (x+1)(y+1) = 15 = 15*1 and 5*3
Here, we don’t get any pair.
Case 3: H = 6
x+y+xy = 7 or (x+1)(y+1) = 8
(3,1) is the required pair and the numbers are (18,6)
Case 4: H = 7
x+y+xy = 6 or (x+1)(y+1) = 7
Here, we don’t get any pair.
Case 5: H = 14
x+y+xy = 3 or (x+1)(y+1) = 4
(1,1) is the required pair and the numbers are (14,14)
Case 6: H = 21
Here, again we don’t get any pair satisfying the condition.
Thus, we only three such pairs i.e. (20,2), (18,6) and (14,14)
Example 7: What is the smallest number which when increased by 5 is completely divisible by 8, 11 and 24? (CAT 1994)
1. 264 2. 259 3.269 4. None of these
Solution: We want to find the smallest number that when increased by 5 will be completely divisible by 8, 11 and 24.
Let that number be N
N+5 = Multiple (8,11,24)
As N is smallest, smallest multiple of (8,11,24) will be their L.C.M. i.e. 264
N + 5 = 264 or N = 259.
There are certain models of L.C.M. and H.C.F. questions that are frequently witnessed in the exams.
Finding a number which when divided by certain divisors yield a common remainder.
Example 8: What is the smallest number which when divided by 3, 5 and 7 gives a remainder of 2?
Solution: The smallest number which is perfectly divisible by 3,5 and 7 is the L.C.M. of (3,5,7) i.e. 105
Now any number of the form 105k+2, will always give a remainder of 2 when divided by 3 or 5 or7.
For the smallest number put k = 0, to get 2.
In general if the divisors are d1,d2 and d3 while the common remainder obtained is r
Then the numbers will be of the form: k (L.C.M. of d1,d2,d3) + r
Example 9: What is the smallest four digit number which when divided by 8,16 and 40 will give a remainder of 3?
Solution: The general form of the number will be N = k (L.C.M. of d1,d2,d3) + r
In this case general form of the number is N = k(LCM of 8,16,40) + 3 = 80k+3
Now we have to find the smallest four digit number of the given form.
80k+3 ≥ 1000 (smallest four digit number)
80k ≥ 997 or k ≥ 12.46
Smallest integral value of k = 13.
Substitute k =13, we get the value of N = 1043.
Example 10 : What is the smallest number which when divided by 8,12 and 9 gives a remainder of 4 but is perfectly divisible by 7?
Solution: First we’ll see the general form of the number giving a remainder of 4 with 8,12 and 9
N = kLCM(8,12,9) + 4
N = 72k + 4
Now, we need to find the smallest number of this form which is perfectly divisible by 7
N = 72k1 + 4 = 7k2
72k1 + 4 = 7k2
As RHS is a multiple of 7, we break the LHS into multiples of 7.
70k1 + 2k1 + 4 = 7k2
So, this implies 2k1+4 must be a multiple of 7 or 2(k1+2) must also be multiple of 7.
Smallest value of k1 that makes 2(k1+2) a multiple of 7 is 5
So, k1 = 5
N = 72*5 + 4 = 364
Thus, the smallest number that leaves a remainder of 4 with 8,12 and 9 and is perfectly divisible by 7 is 364.
Model 2 (Related to HCF):
If the difference between the divisor and the remainder obtained is constant, then it comes under the model 2.
Example11: Find the smallest number which when divided by 4 gives a remainder of 2, with 6 gives a remainder of 4 and with 8 gives a remainder of 6.
Solution: Divisor Remainder Difference
4 2 2
6 4 2
8 6 2
Here the difference between the divisor and the remainder is constant i.e. 2
So, in such cases the general form of the number will be
kLCM(d1,d2,d3) – common difference.
N = kLCM (4,6,8) – 2 = 24k – 2
For the smallest value put k = 1, so N = 22.
Example 12: Find the smallest number which when divided by 7 gives a remainder of 4, with 11 gives a remainder of 8 and with 12 gives a remainder of 9 but is perfectly divisible by 9?
So, the general form the number will be kLCM(7,11&12) – 3
N = 924k – 3
Now, N is also divisible by 9,
N = 924k1 – 3 = 9k2
As the RHS is a multiple of 9, breaking the LHS also into multiples of 9 we get,
102k1 + 6k1 – 3 = 9k2
So, 6k1 -3 must be a multiple of 9. Thus the smallest value of k1 making the expression a multiple of 9 would be 2.
N = 924*2 – 3 = 1845
Model 3 (Related to LCM) :
Here there is no such pattern i.e. no common remainder or the difference between the divisor and the remainder being constant.
Example 13: What is the smallest three digit number which when divided by 6 gives and remainder of 4 and when divided by 11 gives a remainder of 7.
Solution: Let the smallest such number be N
N = 6k1 + 4 = 11k2 + 7
Or 6k1 = 11k2 + 3
As the L.H.S. is a multiple of 6, so breaking the R.H.S. also as a multiple of 6 we get,
6k1 = 6k2 + 5k2 + 3
So, 5k2 + 3 must be a multiple of 6, giving k2 = 3
So, N = 11*3 + 7 = 40
The smallest such number is 40.
In general the number will be kLCM(divisors) + Smallest Number
The general form of N = kLCM(6,11) + 40 = 66k + 40
For finding the smallest three digit number, put k = 1
N = 106
Example 14: Find the smallest number that gives a remainder of 2 when divided by 7, remainder of 4 when divided by 8 and a remainder of 3 when divided by 9.
Solution: Here N = 7k1 + 2 = 8k2 + 4 = 9k3 + 3
Consider the first two equations:
7k1 + 2 = 8k2 + 4
7k1 = 8k2 + 2
As LHS is a multiple of 7, breaking the RHS into multiples of 7 we get
7k1 = 7k2 + k2 + 2
Smallest value of k2 making k2+2, a multiple of 7 is 5.
So, smallest such number giving a remainder of 2 with 7 and 4 with 8 is 8*5 + 4 =44
The general form of the number satisfying above condition = kLCM(7,8) + 44
= 56k + 44 = N
Now consider this above equation with the third equation
56k+44 = 9k3 + 3
Or 9k3 = 56k + 41
As LHS is a multiple of 9, breaking the RHS into multiples of 9 we get
9k3 = 54k + 36 + 2k + 5
The smallest value of k making 2k+5 a multiple of 9 is 2
N = 56*2 + 44 = 156.
Thus, the smallest number giving a remainder of 2 with 7, 4 with 8 and 3 with 9 is 156.
The general form of N will be kLCM(7,8,9) + 156 = 504k + 156
Model 4 (Related to HCF) :
This model is related to finding the divisor instead of the dividend as seen in the earlier three models and involves HCF.