Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
What
is highest common factor (HCF) and least common multiple (LCM)? How do you
calculate HCF and LCM of two or more numbers? Are you looking for problems on
HCF and LCM? This chapter will answer all these questions. HIGHEST COMMON FACTOR (HCF) The largest number that divides
two or more given numbers is called the highest common factor (HCF) of those
numbers. There are two methods to find HCF of the given numbers: Prime Factorization Method When a number is written as the product of prime numbers, the factorization is called the prime factorization of that number. For example, 72 = 2 × 2 × 2 × 3 × 3 = 2^{3} × 3^{2} To find the HCF of given
numbers by this method, we perform the prime factorization of all the numbers
and then check for the common prime
factors. For every prime factor common to all the numbers, we choose the least
index of that prime factor among the given number. The HCF is product of all
such prime factors with their respective least indices. EXAMPLE Find the HCF of 72, 288,
and 1080 The
prime factors common to all the numbers are 2 and 3. The lowest indices of 2 and
3 in the given numbers are 3 and 2 respectively. Find the HCF of 36x^{3}y^{2}
and 24x^{4}y. The least index of 2, 3, x and y in the
numbers are 2, 1, 3 and 1 respectively. Division method To find HCF of two numbers by division method, we
divide the higher number by the lower number. Then we divide the lower number
by the first remainder, the first remainder by the second remainder... and so
on, till the remainder is 0. The last divisor is the required HCF. EXAMPLE Find the HCF of 288 and
1080 by the division method. Answer:
Hence, the last
divisor 72 is the HCF of 288 and 1080. CONCEPT OF COPRIME NUMBERS: Two
numbers are coprime to each other if they have no common factor except 1. For
example, 15 and 32, 16 and 5, 8 and 27 are the pairs of coprime numbers. If
the HCF of two numbers N_{1} and N_{2} be H, then, the numbers
left after dividing N_{1} and N_{2} by H are coprime to each other. Therefore, if the HCF of two
numbers be A, the numbers can be written as Ax and Ay, where x and y will be
coprime to each other. SOLVED PROBLEMS ON HCF
Three company of
soldiers containing 120, 192, and 144 soldiers are to be broken down into
smaller groups such that each group contains soldiers from one company only and
all the groups have equal number of soldiers. What is the least number of total
groups formed? Answer:
The least number of groups will be formed when each group has number of
soldiers equal to the HCF. The HCF of 120, 192 and 144 is 24. Therefore, the
numbers of groups formed for the three companies will be 5, 8, and 6, respectively.
Therefore, the least number of total groups formed = 5 + 8 + 6 = 19. The
numbers 2604, 1020 and 4812 when divided by a number N give the same remainder
of 12. Find the highest such number N. Answer: Since all the numbers give a remainder of 12 when divided by N, hence (2604  12), (1020  12) and (4812  12) are all divisible by N. Hence, N is the HCF of 2592, 1008 and 4800. Now 2592 = 2^{5} × 3^{4}, 1008 = 2^{4} × 3^{2} × 7 and 4800 = 2^{6} × 3 × 5^{2}. Hence, the number N = HCF = 2^{4} × 3 = 48. The
numbers 400, 536 and 645, when divided by a number N, give the remainders of
22, 23 and 24 respectively. Find the greatest such number N. Answer: N will be the HCF of (400  22), (536  23) and (645  24). Hence, N will be the HCF of 378, 513 and 621. > N = 27. The HCF
of two numbers is 12 and their sum is 288. How many pairs of such numbers are
possible? Answer: If the HCF if 12, the
numbers can be written as 12x and 12y, where x and y are coprime to each
other. Therefore, 12x + 12y = 288 > x + y =
24. The pair of numbers that are
coprime to each other and sum up to 24 are (1, 23), (5, 19), (7, 17) and (11,
13). Hence, only four pairs of such numbers are possible. The numbers are (12,
276), (60, 228), (84, 204) and (132, 156). The HCF of two numbers is
12 and their product is 31104. How many such numbers are possible? Answer:
Let the numbers be 12x and 12y, where x and y are coprime to each other.
Therefore, 12x × 12y = 31104 > xy = 216. Now we need to find
coprime pairs whose product is 216. 216 =
2^{3} × 3^{3}. Therefore, the coprime pairs will
be (1, 216) and (8, 27). Therefore, only two such numbers are possible. LEAST
COMMON MULTIPLE (LCM) The least common multiple (LCM) of two or more numbers is the
lowest number which is divisible by all the given numbers. To calculate the LCM of two or more numbers, we use the
following two methods: Prime Factorization Method: After
performing the prime factorization of the numbers, i.e. breaking the numbers
into product of prime numbers, we find the highest index, among the given
numbers, of all the prime numbers. The LCM is the product of all these prime
numbers with their respective highest indices. EXAMPLE Find the
LCM of 72, 288 and 1080. Answer: 72 = 2^{3} × 3^{2}, 288 = 2^{5} × 3^{2}, 1080 = 2^{3} × 3^{3} × 5 The
prime numbers present are 2, 3 and 5. The highest indices (powers) of 2, 3 and 5
are 5, 3 and 1, respectively. Hence the LCM = 2^{5} × 3^{3} × 5 = 4320. Find the LCM of 36x^{3}y^{2}
and 24x^{4}y. Answer: 36x^{3}y^{2} = 2^{2} × 3^{2} × x^{3} × y^{2}
24x^{4}y = 2^{3} × 3 × x^{4} × y. Division Method: To find the LCM of 72, 196 and
240, we use the division method in the following way:
L.C.M. of the given numbers = product of divisors and the
remaining numbers PROPERTIES
OF HCF AND LCM Â·
The HCF of two or more numbers is smaller than or
equal to the smallest of those numbers. SOLVED PROBLEMS ON LCM Find the
highest fourdigit number that is divisible by each of the numbers 24, 36, 45
and 60. Hence the highest fourdigit
number divisible by 24, 36, 45 and 60 = 3720. Find the
highest number less than 1800 that is divisible by each of the numbers 2, 3, 4,
5, 6 and 7. Answer: The LCM of 2, 3, 4, 5, 6
and 7 is 420. Hence 420, and every multiple of 420, is divisible by each of
these numbers. Hence, the number 420, 840, 1260, and 1680 are all divisible by
each of these numbers. We can see that 1680 is the highest number less than
1800 which is multiple of 420. Find the
lowest number which gives a remainder of 5 when divided by any of the numbers
6, 7, and 8. Answer: The LCM of 6, 7 and 8 is
168. Hence, 168 is divisible by 6, 7 and 8. Therefore, 168 + 5 = 173 will give
a remainder of 5 when divided by these numbers. What is
the smallest number which when divided by 9, 18, 24 leaves a remainder of 5, 14
and 20 respectively? Answer: The common difference
between the divisor and the remainder is 4 (9  5 = 4,
18  14 = 4, 24  20 = 4).
Now the LCM of 9, 18, and 24 is 72. Now 72  4 = 72  9 + 5 = 72
 18 + 14 = 72  24 + 20.
Therefore, if we subtract 4 from 72, the resulting number will give remainders
of 5, 14, and 20 with 9, 18, and 24. Hence, the number = 72  4 = 68.
A
number
when divided by 3, 4, 5, and 6 always leaves a remainder of 2, but
leaves no remainder when divided by 7. What is the lowest such number
possible? Answer: the LCM of 3, 4, 5 and 6 is 60. Therefore, the number is of the form 60k + 2, i.e. 62, 122, 182, 242 etc. We can see that 182 is divisible by 7. Therefore, the lowest such number possible = 182. I shall have to end here and leave the rest of it for my CBT Club students. I shall cover some problems based on this in the CBT Club this week.

Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Hi Ankita, Yes you are correct. 3720 is a typo. 9720 is the correct answer. Total Gadha 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Hi TG, this really very useful article.... please give some more questions on HCF and LCM to practice.. Thanks 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Hey friends , what would be the LCM of 3333....3 (written 70times) and 2222....2(written 20 times)? Any clues? 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
is its answer 140 * 6 = 840.. 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
agreed 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
hi solanki, how is it ? Can u explain how u got 140? 
plz solve this...  
lcm of 4.5, .009 and .18? 
Re: plz solve this...  
45/10,9/1000,18/100 LCM= LCM(Num)/HCF(Den) = 90/10 = 9 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
hi ! TG sir

Re: plz solve this...  
hi reema , ur ans is 4.5 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Thanks man!!! this article is just awesome. 
Re: plz solve this...  
@ manendra i feel the answer should be 90/10 i.e. 9 the LCM of numerator would be 90 and the HCF 10 so LCM of the fraction becomes 9. 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Hi TG sir, Please explain how the answer is 140 to the question asked by William? 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Yes Nitish u r rite... Why the need for LCM in this case then? 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Hi Bhavna, See the video: http://totalgadha.com/mod/resource/view.php?id=1147 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Sir, how to calculate the LCM of decimal numbers? Ankit Khandelwal 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
hi kamal thanks for the soln. i have one more query..... 1)x+y=n,(x,y) are pair of co primes,how many such pairs r possible.... 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
Dear TG, How to solve the following? Find the HCF of [(2^100)1 , (2^1201)] 
Re: Highest Commom Factor (HCF) and Least Common Multiple (LCM)  
thank you mr tg sir your post is very useful. 