Introduction & Concept: HCF & LCM

# Introduction & Concept: HCF & LCM | CSAT Preparation - UPSC PDF Download

 Table of contents What is Highest Common Factor (H.C.F.)? Methods of finding the HCF What is Least Common Multiple (L.C.M.)? Methods of finding the LCM Relationship between HCF and LCM H.C.F. and L.C.M. of Decimals H.C.F. and L.C.M. of Fractions List of Properties Solved Questions

HCF and LCM is another very important topic from the number system. The concept is not just restricted to the number system but is also helpful in solving some questions from arithmetic which is a very important topic for CAT exam.

In this article, we will take the topic from basics and will try to understand the various types of problems which require HCF and LCM concepts. Many questions on HCF and LCM from CAT exam are solved by applying direct formulas and tricks

## What is Highest Common Factor (H.C.F.)?

The H.C.F. of two or more than two numbers is the greatest number that divides each of them exactly.

• H.C.F is also called as Greatest Common Measure (G.C.M.) or Greatest Common Divisor (G.C.D).
• Every number has some factors, but if two or more numbers taken together can have one or more common factors. Out of those common factors, the greatest among them will be the highest common divisor or highest common factor of those numbers.

Finding the GCD / H.C.F.

• Find the standard form of the numbers E and R.
• Write out all prime factors that are common to the standard forms of the numbers E and R.
• Raise each of the common prime factors listed above to the lesser of the powers in which it appears in the standard forms of the numbers E and R.
• The product of the results of the previous step will be the GCD of E and R.

HCF of 4 and 6 via diagram is shown below:

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.

## Methods of finding the HCF

### (a) Factorization Method

Express each number as the product of primes and take the product of the least powers of common factors to get the H.C.F.

Steps to solve:

• Step 1: Write each number as a product of its prime factors. This method is called here prime factorization.
• Step 2: Now list the common factors of both the numbers
• Step 3: The product of all common prime factors is the HCF ( use the lower power of each common factor).

Example: Evaluate the HCF of 60 and 75.

Solution: Write each number as a product of its prime factors.
2x 3 x 5 = 60
3 x 5= 75
The product of all common prime factors is the HCF.
The common prime factors in this example are 3 & 5.
The lowest power of 3 is 3 and 5 is 5.
So, HCF = 3 x 5 = 15

### (b) Division Method

• Step 1: Take the smaller number as the divisor and the larger number as a dividend.
• Step 2: Perform division. If you get the remainder as 0, then the divisor is the HCF of the given numbers.
• Step 3: If you get a remainder other than 0 then take the remainder as the new divisor and the previous divisor as the new dividend.

Example: Find out the HCF of 36 and 48.
Ans: Step I:Here we need to divide 48 by 36. ie. Dividend = 48 and Divisor = 36
[Divide the larger number by the smaller one].
Step II: Divide the 2 numbers
Step III: When 12 becomes divisor, remainder becomes 0. Therefore, highest common factor = 12.
[The last divisor is the required highest common factor (H.C.F) of the given numbers].

### (c) Prime Factorization(Factor Tree) Method

Prime factorization is the process of breaking down a composite number into its prime factors, which are the prime numbers that multiply together to give the original number.

Steps to solve:

• Step 1: In calculating the HCF by prime factorization, we factorise the numbers into prime numbers, which is known as the prime factors.
• Step 2: Start by dividing the given numbers by 2(the first prime number), go on dividing till you can’t divide the number any further.
• Step 3: Finally, then write the numbers as a product of the prime numbers. The product of these common factors is the highest common factor of the given numbers.

Example: Using prime factorization method, find HCF of 18 and 90
Ans: Prime factorization of 18 is given below:

Prime factorization of 90 is given below:

There are 6 common factors of 18 and 90, that are 1, 2, 3, 6, 9, and 18. Therefore, the greatest common factor of 18 and 90 is 18.

### Shortcut Method for Finding the HCF

Suppose you were required to find the HCF of 39,78 and 195:

• Logic:  The HCF of these numbers would necessarily have to be a factor (divisor) of the difference between any pair of numbers from the above 3.
The HCF has to be a factor of (78 – 39 = 39) as well as of (195 – 39 = 156) and (195 – 78 = 117). Why? Well, the logic is simple if you were to consider the tables of numbers on the number line.
• For any two numbers on the number line, a common divisor would be one which divides both. However, for any number to be able to divide both the numbers, it can only do so if it is a factor of the difference between the two numbers. Got it?? No??
• Then, Let’s see an illustrative: Say we take the numbers 68 and 119. The difference between them being 51, it is not possible for any number outside the factor list of 51 to divide both 68 and 119. Thus, for example, a number like 4, which divides 68 can never divide any number which is 51 away from 68 because 4 is not a factor of 51. Only factors of 51, i.e. 51,17,3 and 1 ‘could’ divide both these numbers simultaneously.

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?

Solution: 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 2223-2169 = 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)

Question for Introduction & Concept: HCF & LCM
Try yourself:A nursery has 363,429 and 693 plants respectively of 3 distinct varieties. It is desired to place these plants in straight rows of plants of 1 variety only so that the number of rows required is the minimum. What is the size of each row and how many rows would be required? (Try to solve using the shortcut method)?

## What is Least Common Multiple (L.C.M.)?

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

• Find the standard form of the numbers E and R.
• Write out all the prime factors, which are contained in the standard forms of either of the numbers.
• Raise each of the prime factors listed above to the highest of the powers in which it appears in the standard forms of the numbers E and R.
• The product of the results of the previous step will be the LCM of E and R.

LCM of 4 and 6 via diagram is shown below:

Example 3: Find the LCM of 150, 210, 375.

• Step 1: Writing down the standard form of numbers:
⇨ 150 = 5 × 5 × 3 × 2 = 5× 3 × 2
⇨ 210 = 5 × 2 × 7 × 3
⇨ 375 = 5 × 5 × 5 × 3 = 53 × 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.

## Methods of finding the LCM

### (i) Prime Factorization Method

Steps involved:

• Step 1: Find the prime factors of the given numbers by repeated division method.
• Step 2: Write the numbers in their exponent form. Find the product of only those prime factors that have the highest power.
• Step 3: The product of these factors with the highest powers is the LCM of the given numbers.

Example: Find the least common multiple (LCM) of 60 and 90 using prime factorization.

Ans: Let us find the LCM of 60 and 90 using the prime factorization method.

• Step 1: The prime factorization of 60 and 90 are: 60 = 2 × 2 × 3 × 5 and 90 = 2 × 3 × 3 × 5
• Step 2: If we write these prime factors in their exponent form it will be expressed as, 60 = 22 × 31 × 51 and 90 = 21 × 32 × 51
• Step 3: Now, we will find the product of only those factors that have the highest powers among these. This will be, 22 × 32 × 51 = 4 × 9 × 5 = 180

=>LCM(60,90) = 180

### (ii) Division Method (short-cut)

Steps involved:

• Step 1: Arrange the given number in a row.
• Step 2: Divide by a number that divides exactly at least two of the given numbers and carry forward the numbers which are not divisible.
• Step 3: Repeat the above process till no two numbers are divisible by the same number except 1.
• Step 4: The product of the divisors and the undivided numbers is the required L.C.M. of the given numbers.

Question for Introduction & Concept: HCF & LCM
Try yourself:The LCM of two numbers is 936. If their HCF is 4 and one of the numbers is 72, the other is:

Example 4: Find the L.C.M. of 72, 240, 196.

Answer: (i) Using Prime Factorisation method:

⇨ 72 = 2 × 2 × 2 × 3 × 3 = 2× 32
⇨ 240 = 2 × 2 × 2 × 2 × 3 × 5 = 2× 3 × 5
⇨ 196 = 2 × 2 × 7 × 7 = 2× 72

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× 3× 5 × 72 = 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

3 | 3 , 10 , 49

7 | 1 , 10 , 49

7 | 1 , 10 , 1

10 | 1 , 10 , 1

| 1 , 1 , 1

L.C.M. of the given numbers:
= Product of divisors and the remaining numbers
= 2 × 2 × 2 × 3 × 3 × 10 × 49
= 35280

Question for Introduction & Concept: HCF & LCM
Try yourself:Find Greatest Number, which will divide 215,167 and 135 so as to leave the same remainder in each case

Co-primes: Two numbers are said to be co-primes if their H.C.F. is 1.

## Relationship between HCF and LCM

Let us assume a and b are the two numbers, then the formula that expresses the relationship between their LCM and HCF is given as:

 Product of Two numbers = (HCF of the two numbers) x (LCM of the two numbers)GCD (P, Q) × LCM (P, Q) = P × Q

Note: This rule is applicable only for two numbers.

## H.C.F. and L.C.M. of Decimals

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.

• Step I: Convert each of the decimals to like decimals.
• Step II: Remove the decimal point and find the highest common factor and least common multiple as usual.
• Step III: In the answer (highest common factor /least common multiple), put the decimal point as there are a number of decimal places in the like decimals.

Example: Find the HCF and LCM of 3, 2.7, 0.09

• Step-1: Write all the numbers with same number of digits after decimal point.
3.00, 2.70, 0.09
• Step-2: Now count the number of digits after decimal point (value is 2 for above problem) and calculate 10 power of the obtained value. Let the number be n = 102 = 100.
• Step-3: Now remove the decimal point and find the LCM and HCF of the numbers.
LCM(300, 270, 9) and HCF(300, 270, 9).

• 300 = 22 x 31 x 52
270 = 21 x 33 x 51
9 = 20 x 32 x 50
LCM(300, 270, 9) = 22 x 33 x 52 = 2700
HCF(300, 270, 9) = 20 x 31 x 50 = 3
For finding the LCM and HCF, we should write the number in the power of prime numbers as written above. We should ensure that all the numbers should be written as power of prime numbers of same number. Example : 9 can be written as 32 but the other two numbers also contain 2 and 5 as primes. So we can write other two numbers as powers of 0. So 9 can be written as 20 x 32 x 50 and it won’t change the value of the number. Since we have our numbers in form of power of primes, Now the LCM is the number formed as the product of primes with its power is maximum value of the power of the same prime in given numbers.
• LCM = 2 power of max(2, 1, 0) x 3 power of max(1, 3, 2) x 5 power of max(2, 1, 0) = 22 x 33 x 52 = 2700 .
HCF calculation is similar but with only one change. Instead of taking max in power we take min in power.
• HCF = 2 power of min(2, 1, 0) x 3 power of min(1, 3, 2) x 5 power of min(2, 1, 0) = 20 x 31 x 50 = 3
• Step-4: Now divide the obtained answer with our number n in step 2. The value we obtain is our required answer.
LCM(3, 2.7, 9) = 2700/100 = 27
HCF(3, 2.7, 9) = 3/100 = 0.03

Example: Find the H.C.F. and the L.C.M. of 1.20 and 22.5

Solution: Converting each of the following decimals into like decimals we get; 1.20 and 22.50

Now, expressing each of the numbers without the decimals as the product of primes we get

120 = 2 × 2 × 2 × 3 × 5 = 23 × 3 × 5

2250 = 2 × 3 × 3 × 5 × 5 × 5 = 2 × 32 × 53

Now, H.C.F. of 120 and 2250 = 2 × 3 × 5 = 30

Therefore, the H.C.F. of 1.20 and 22.5 = 0.30 (taking 2 decimal places)

L.C.M. of 120 and 2250 = 23 × 32 × 53 = 9000

Therefore, L.C.M. of 1.20 and 22.5 = 90.00 (taking 2 decimal places)

Example: Find the H.C.F. and the L.C.M. of 0.48, 0.72 and 0.108

Solution: Converting each of the following decimals into like decimals we get;

0.480, 0.720 and 0.108

Now, expressing each of the numbers without the decimals as the product of primes we get

480 = 2 × 2 × 2 × 2 × 2 × 3 × 5 = 25 × 3 × 5

720 = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 24 × 32 × 5

108 = 2 × 2 × 3 × 3 × 3 = 22 × 33

Now, H.C.F. of 480, 720 and 108 = 22 × 3 = 12

Therefore, the H.C.F. of 0.48, 0.72 and 0.108 = 0.012 (taking 3 decimal places)

L.C.M. of 480, 720 and 108 = 25 × 33 × 5 = 4320

Therefore, L.C.M. of 0.48, 0.72, 0.108 = 4.32 (taking 3 decimal places)

Question for Introduction & Concept: HCF & LCM
Try yourself:What Will Be The Least Possible Number Of The Planks, if three pieces of timber 42 m, 49 m, and 63 m long have to be divided into planks of the same length?

## H.C.F. and L.C.M. of Fractions

To calculate the Highest Common Factor (HCF) and Lowest Common Multiple (LCM) of fractions, find the HCF and LCM of their numerators and denominators separately.

(a) HCF: To calculate the Highest Common Factor (HCF) of fractions, find the HCF of their numerators and denominators individually.

With fractions 3/6 and 5/15, the HCF of the numerators (3 and 5) is 1, and the HCF of the denominators (6 and 15) is 3. Thus, the HCF of the fractions is 1/3.

(b) LCM: To calculate the Lowest Common Multiple (LCM) of fractions, determine the LCM of their numerators and denominators separately.

The LCM of the numerators (3 and 5) is 15, and the LCM of the denominators (6 and 15) is 30. Consequently, the LCM of the fractions is 15/30, which simplifies to 1/2.

## List of Properties

### (i) HCF and LCM Property 1

The product of LCM and HCF of any two given natural numbers is equivalent to the product of the given numbers. LCM × HCF = Product of the Numbers. Suppose A and B are two numbers, then.

LCM (A & B) × HCF (A & B) = A × B

For Example: If 3 and 8 are two numbers.

LCM (3,8) = 24

HCF (3,8) = 1

LCM (3,8) x HCF (3,8) = 24 x 1 = 24

Also, 3 x 8 = 24

Hence, proved.

Note: This property is applicable for only two numbers.

### (ii) HCF and LCM Property 2

HCF of co-prime numbers is 1. Therefore, the LCM of given co-prime numbers is equal to the product of the numbers. LCM of Co-prime Numbers = Product Of The Numbers

For Example: Let us take two coprime numbers, such as 21 and 22.

LCM of 21 and 22 = 462

Product of 21 and 22 = 462

LCM (21, 22) = 21 x 22

### (iii) HCF and LCM Property 3

H.C.F. and L.C.M. of Fractions:

LCM of fractions = LCM of Numerators / HCF of Denominators. HCF of fractions = HCF of Numerators / LCM of Denominators.
For Example: Let us take two fractions 4/9 and 6/21. 4 and 6 are the numerators & 9 and 12 are the denominators

LCM (4, 6) = 12

HCF (4, 6) = 2

LCM (9, 21) = 63

HCF (9, 21) = 3

Now as per the formula, we can write:

LCM (4/9, 6/21) = 12/3 = 4. Then HCF (4/9, 6/21) = 2/63

### (iv) HCF and LCM Property 4

HCF of any two or more numbers is never greater than any of the given numbers.

For Example: HCF of 4 and 8 is 4. Here, one number is 4 itself and another number 8 is greater than HCF (4, 8), i.e.,4.

### (v) HCF and LCM Property 5

LCM of any two or more numbers is never smaller than any of the given numbers.

For Example: LCM of 4 and 8 is 8 which is not smaller to any of them

## Solved Questions

Example 1: How many pairs of integers (x, y) exist such that the product of x, y and HCF (x, y) = 1080?

1. 8
2. 7
3. 9
4. 12

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 h3(ab) = 1080 = (23)(33)(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 co-prime. We gave 4 pairs of 8 ordered pairs (1, 1080), (8, 135), (27, 40) and (5, 216). (Essentially we are finding co-prime a,b such that a*b = 1080).
2. h = 2, We need to find a number of ways of writing (33) * (5) as a product of two co-prime numbers. This can be done in two ways - 1 and (33) * (5) , (33) 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).

Example 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?

1. 2519
2. 5039
3. 1079
4. 979

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.

Example 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").

Answer: It is vital not to be intimidated by questions that have a lot of variables in them.

• a is a multiple of l and n. Also, HCF (l,n) =1; => a has to be a multiple of ln, similarly, b has to be a multiple of lm and c has to be a multiple of mn.
• We can assume, a = lnx, b = lmy, c = mnz.
Now given that HCF(a, b) = l, that means HCF(nx, my) = 1. This implies HCF(x, y) = 1 and HCF(m, x) = HCF(n, y) = 1.
• Similarly, it can also be shown that HCF(y, z) = HCF(z, x) = 1 and others also.
• So, in general, it can be written any two of the set {l, m, n, x, y, z} are co-prime.
Now LCM(a, b, c) = LCM (lnx, lmy, mnz) = lmnxyz = abc/lmn.
• Quite obviously, it is a reasonable assumption that a question in CAT will not be as tough as the last one here. However, it is a good question to get an idea of the properties of LCM and HCF.
##### Hence the answer is "Cannot be determined"

The document Introduction & Concept: HCF & LCM | CSAT Preparation - UPSC is a part of the UPSC Course CSAT Preparation.
All you need of UPSC at this link: UPSC

## CSAT Preparation

194 videos|156 docs|192 tests

### Up next

 Doc | 7 pages
 Doc | 3 pages
 Video | 70:04 min

## FAQs on Introduction & Concept: HCF & LCM - CSAT Preparation - UPSC

 1. What is the difference between H.C.F. and L.C.M.?
Ans. The Highest Common Factor (H.C.F.) is the largest number that divides two or more numbers without leaving a remainder, while the Least Common Multiple (L.C.M.) is the smallest number that is a multiple of two or more numbers.
 2. How do you find the GCD / H.C.F. of two numbers?
Ans. To find the Greatest Common Divisor (GCD) or Highest Common Factor (H.C.F.) of two numbers, you can use methods such as prime factorization, common division, or Euclidean algorithm.
 3. What is the formula to calculate H.C.F. and L.C.M.?
Ans. The formula to calculate the H.C.F. of two numbers is H.C.F. = Product of prime factors raised to the lowest power common to both numbers. The formula to calculate the L.C.M. of two numbers is L.C.M. = Product of prime factors raised to the highest power in both numbers.
 4. How do you find the H.C.F. and L.C.M. of decimal fractions?
Ans. To find the H.C.F. and L.C.M. of decimal fractions, convert the decimal numbers into fractions by placing the decimal number over the appropriate power of 10, then find the H.C.F. and L.C.M. of the fractions as usual.
 5. How can you compare fractions using H.C.F. and L.C.M.?
Ans. To compare fractions using H.C.F. and L.C.M., find the H.C.F. of the numerators and the L.C.M. of the denominators. If the H.C.F. is 1, the fractions are in lowest terms. If the L.C.M. is the same, the fractions have the same denominator.

## CSAT Preparation

194 videos|156 docs|192 tests

### Up next

 Doc | 7 pages
 Doc | 3 pages
 Video | 70:04 min
 Explore Courses for UPSC exam

### How to Prepare for UPSC

Read our guide to prepare for UPSC which is created by Toppers & the best Teachers
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;