 H.C.F is also called as Greatest Common Measure (G.C.M.) or Greatest Common Divisor (G.C.D).
 The H.C.F. of two or more than two numbers is the greatest number that divides each of them exactly.
Example 1: Find the GCD of 150, 210, 375.
 Step 1: Writing down the standard form of numbers
⇨ 150 = 5 X 5 X 3 X 2
⇨ 210 = 5 X 2 X 7 X 3
⇨ 375 = 5 X 5 X 5 X 3 Step 2: Writing Prime factors common to all the three numbers is 5 X 3.
 Step 3: Hence, the HCF will be 5 X 3 = 15.
(i) Factorization Method (Prime Factorisation Method)
(ii) Division Method
Suppose you were required to find the HCF of 39,78 and 195:
Example 2: The sides of a hexagonal field are 216, 423, 1215, 1422, 2169 and 2223 metres. Find the greatest length of tape that would be able to exactly measure each of these sides without having to use fractions/parts of the tape?
Before solving this example, remind yourself with the above short trick you read above.
⇨ In this question, we are required to identify the HCF of the numbers 216, 423,1215, 1422, 2169 and 2223.
⇨ In order to do that, we first find the smallest difference between any two of these numbers. It can be seen that the difference between 22232169 = 54.Thus, the required HCF would be a factor of the number 54. The factors of 54 are: 1 × 54, 2 × 27, 3 X 18, 6 X 9
⇨ One of these 8 numbers has to be the HCF of the 6 numbers. 54 cannot be the HCF because the numbers 423 and 2223 being odd numbers would not be divisible by any even number. Thus, we do not need to check any even numbers in the list.
⇨ 27 does not divide 423 and hence cannot be the HCF. 18 can be skipped as it is even.
⇨ Checking for 9: 9 divides 216,423,1215,1422 and 2169.
⇨ Hence, it would become the HCF. (Note: we do not need to check 2223 once we know that 2169 is divisible by 9)
LCM stands for Lowest or Least Common Multiple. The LCM of two or more numbers is the smallest positive integer that is divisible by all the given numbers.
Finding the LCM two numbers E and R
Example 3: Find the LCM of 150, 210, 375.
 Step 1: Writing down the standard form of numbers:
⇨ 150 = 5 × 5 × 3 × 2 = 5^{2 }× 3 × 2
⇨ 210 = 5 × 2 × 7 × 3
⇨ 375 = 5 × 5 × 5 × 3 = 5^{3 }× 3 Step 2: Write down all the prime factors: that appear at least once in any of the numbers: 5, 3, 2, 7.
 Step 3: Raise each of the prime factors to their highest available power (considering each to the numbers).
The LCM = 2 × 3 × 5 × 5 × 5 × 7 = 5250.
(i) Factorization Method
(ii) Division Method (shortcut)
Example 4: Find the L.C.M. of 72, 240, 196.
(i) Using Prime factorisation method:
⇨ 72 = 2 × 2 × 2 × 3 × 3 = 2^{3 }× 3^{2}
⇨ 240 = 2 × 2 × 2 × 2 × 3 × 5 = 2^{4 }× 3 × 5
⇨ 196 = 2 × 2 × 7 × 7 = 2^{2 }× 7^{2}L.C.M. of the given numbers = Product of all the prime factors of each of the given number with greatest index of common prime factors
= 2^{4 }× 3^{2 }× 5 × 7^{2} = 16 × 9 × 5 × 49 = 35280.(ii) Using the Division method:
2  72, 240, 196
2  36, 120, 98
2  18, 60 , 49
3  9 , 30 , 49
L.C.M. of the given numbers:
= Product of divisors and the remaining numbers
= 2 × 2 × 2 × 3 × 3 × 10 × 49
= 35280
Coprimes: Two numbers are said to be coprimes if their H.C.F. is 1.
The formula which involves both HCF and LCM is:
Product of Two numbers = (HCF of the two numbers) x (LCM of the two numbers)
GCD (E, R) × LCM (E, R) = E × R
Note: This rule is applicable only for two numbers
In given numbers, make the same number of decimal places by annexing zeros in some numbers, if necessary. Considering these numbers without a decimal point, find H.C.F. or L.C.M. as the case may be. Now, in the result, mark off as many decimal places as are there in each of the given numbers.
Find the L.C.M. of the denominators of the given fractions. Convert each of the fractions into an equivalent fraction with L.C.M as the denominator, by multiplying both the numerator and denominator by the same number. The resultant fraction with the greatest numerator is the greatest.
Q.1. How many pairs of integers (x, y) exist such that the product of x, y and HCF (x, y) = 1080?
Answer: Option 3
Solution:
We need to find ordered pairs (x, y) such that xy * HCF(x, y) = 1080.
Let x = ha and y = hb where h = HCF(x, y) => HCF(a, b) = 1.
So h^{3}(ab) = 1080 = (2^{3})(3^{3})(5).
We need to write 1080 as a product of a perfect cube and another number.
Four cases:
1. h = 1, ab = 1080 and b are coprime. We gave 4 pairs of 8 ordered pairs (1, 1080), (8, 135), (27, 40) and (5, 216). (Essentially we are finding coprime a,b such that a*b = 1080).
2. h = 2, We need to find a number of ways of writing (3^{3}) * (5) as a product of two coprime numbers. This can be done in two ways  1 and (3^{3}) * (5) , (3^{3}) and (5)
number of pairs = 2, number of ordered pairs = 4
3. h = 3, number of pairs = 2, number of ordered pairs = 4
4. h = 6, number of pairs = 1, number of ordered pairs = 2
Hence total pairs of (x, y) = 9, total number of ordered pairs = 18.
The pairs are (1, 1080), (8, 135), (27, 40), (5, 216), (2, 270), (10, 54), (3, 120), (24, 15) and (6, 30).
Hence the answer is "9"
Q.2. Find the smallest number that leaves a remainder of 4 on division by 5, 5 on division by 6, 6 on division by 7, 7 on division by 8 and 8 on division by 9?
Answer: Option 1
Solution: When a number is divided by 8, a remainder of 7 can be thought of as a remainder of 1. This idea is very useful in a bunch of questions. So, N = 5a  1 or N + 1 = 5a
N = 6b  1 or N + 1 = 6b
N = 7c  1 or N + 1 = 7c
N = 8d  1 or N + 1 = 8d
N = 9e  1 or N + 1 = 9e
N + 1 can be expressed as a multiple of (5, 6, 7, 8, 9)
N + 1 = 5a*6b*7c*8d*9e
Or N = (5a*6b*7c*8d*9e)  1
Smallest value of N will be when we find the smallest common multiple of (5, 6, 7, 8, 9)
or LCM of (5, 6, 7, 8, 9)
N = LCM (5, 6, 7, 8, 9)  1 = 2520  1 = 2519.
Hence the answer is "2519"
Q.3. There are three numbers a,b, c such that HCF (a, b) = l, HCF (b, c) = m and HCF (c, a) = n. HCF (l, m) = HCF (l, n) = HCF (n, m) = 1. Find LCM of a, b, c. (The answer can be "This cannot be determined").
Solution: It is vital not to be intimidated by questions that have a lot of variables in them.
207 videos156 docs192 tests

1. What is the difference between H.C.F. and L.C.M.? 
2. How do you find the H.C.F. of two numbers? 
3. What is the formula for finding the L.C.M. of two numbers? 
4. Can the H.C.F. of two numbers be greater than the numbers themselves? 
5. How do you find the H.C.F. and L.C.M. of decimal fractions? 
207 videos156 docs192 tests


Explore Courses for UPSC exam
