Overview: HCF & LCM | CSAT Preparation - UPSC PDF Download

An analysis of previous years' papers highlights the significance of this topic, as at least one question is consistently asked from this chapter each year. Questions often involve calculating the LCM and its applications, such as determining the frequency of events occurring together. From an examination perspective, mastering this chapter is essential for aspirants. For instance, one question was asked in 2019, two in 2018, and 1-2 questions annually during the years 2017-2011.
The concept of HCF and LCM for a group of numbers depends on the fundamentals of factors and multiples. This concept of HCF and LCM is also useful for various other topic of basic numeracy. This chapter mainly deals with the calculation of HCF and LCM and their use and implementation in various problems.

Factors

Any composite number N, which can be expressed as
N = x^a × y^b × z^c × ...
where, x , y and z are different prime factors of N and a , b, c are positive integers.
If a given number can be factorised upto its prime numbers, then these factors are called prime factors
e.g.  729 has factors 9 × 9 × 9 but 3 × 3 × 3 × 3 × 3 × 3 are prime factors of 729.
⇒ Total number of factors of N including 1 and number (N) itself
= (a + 1) (b + 1) (c + 1) . . .
e.g. 120 = 2³ × 3¹ × 5¹ 
∴ Number of factors = (3 + 1) (1 + 1) (1 + 1) = 4 × 2 × 2 = 16

Multiples

The number X which can be completely divided by a number N is said to be the multiple of N .
e.g. Multiples of 5 are 10, 15, 20, 25 and 30 etc.

Common Multiple

A common multiple of two numbers is a number which is exactly divisible by each of the given numbers. e.g. 30 is a common multiple of 2, 3, 5 and 6.

Least Common Multiple (LCM)

The least common multiple of two or more given numbers is the least number which is exactly divisible by each one of them. e.g. 42 is the least common multiple of 2, 3 and 7. 84 is also the common multiple of 2, 3, 7 but 42 is the LCM of 2, 3, 7 as it is least among the two.

Methods of Finding LCM

Methods of finding LCM are classified as:
1. By factorisation This method is further illustrated into following steps: 

• Step 1 Find the standard form of the numbers. 
• Step 2 Write out all the prime factors, which are contained in the standard forms of either of the numbers. 
• Step 3 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. 
• Step 4 The product of results of the previous step will be the LCM.

Example: The LCM of 8, 12 and 15 is 
(a) 150 
(b) 100 
(c) 120 
(d) 180
Ans: (c)
Sol: Step 1 Writing down the standard form of numbers
Factors of 8 = 2 × 2 × 2 = 2³
Factors of 12 = 2 × 2 × 3 = 2² × 3¹ 
Factors of 15 = 3 × 5 = 3¹ × 5¹ 
Step 2 Writing down all the prime factors that appear atleast once in any of the numbers 2, 3, 5.
Step 3 Raise each of the prime factors to the highest available power (considering each of the numbers).
∴ LCM = 2³ × 3¹ × 5¹ = 120

2. By division method In this method, the numbers are written together separated by commas and division is started with the least numbers which can atleast divide a number and further it is carried out to obtain the quotient of all number equal to one, then divisors are multiplied to obtain the LCM. The least common multiple of two or more given numbers is the least number which is exactly divisible by each one of them. e.g. 42 is the common multiple of 2, 3 and 7.

• Start division with the least digit and then further proceed to higher digits. 
• Before calculating LCM or HCF, make sure that all numbers are in the same unit.

Applications of LCM

• If some bells ring after different time interval, then time after which they will ring together = LCM of the different time interval. 
• If some boys/men runs around a circular path taking different time, then time after which they meet at a point = LCM of different time taken by them.

Example: Three runners running around a circular track can complete one revolution in 2, 4 and 5.5 h, respectively. When will they meet at starting point? 
(a) 40 h 
(b) 44 h 
(c) 20 h 
(d) 22 h
Ans: (b)
Sol: Time at which they meet at starting point = LCM of 2, 4 and 5.5 = 44 h

Common Factor

A common factor of two or more numbers is a number which divides each of them exactly. e.g. 2 is the common factor of 2, 10 and 18.

Highest Common Factor (HCF)

The highest common factor of two or more numbers is the greatest number which divides each of them exactly. e.g. HCF of the numbers 18 and 24 is 6. It is also known as Greatest Common Divisor (GCD).

Methods of Finding HCF

HCF can be find by following two methods:
1. By long division method To find the HCF by division, divide the largest number by the smaller one. Now, you will get the remainder, divide the divisor by the remainder. Repeat this process until no remainder is left, the last divisor used in this process is the desired highest common factor.
2. By prime factorisation First, write the given numbers into prime factors and then find the product of all the prime factors common to all the numbers. The product of common prime factors with the least powers gives HCF.

Properties of LCM and HCF

Properties of LCM and HCF are define as follows: 

• Property 1 The least number which is exactly divisible by a , b and c is the LCM of a , b and c. 
• Property 2 The greatest number that will divide a , b and c is the HCF of a , b and c. 
• Property 3 HCF of given numbers must be a factor of their LCM.

To Find HCF and LCM of Decimal Numbers and Fractions

First, we make the decimal digits of the given decimal number, by putting same number of zeroes, if necessary. Then, find HCF and LCM ignoring decimals and at last put the decimal according to the given numbers.

(i) HCF of a fraction = HCF of numerators/LCM of denominators
(ii) LCM of a fraction = LCM of numerators/HCF of denominators

HCF and LCM of Polynomials

There are HCF and LCM of polynomials as given below: 

• HCF of polynomials HCF of the polynomials is a common factor in all polynomials.
• LCM of polynomials LCM of polynomials is the least polynomial, which is divisible by each polynomial.

Common Applications of HCF and LCM

• The greatest number which divides the numbers x, y and z leaving remainders a, b and c, respectively = HCF of ( x − a ), ( y − b), ( z − c).
• The greatest number that will divide x, y and z leaving the same remainder in each case, is given by [HCF of ( x − y ), ( y − z ),( z − x ),... ] or [HCF of ( y − x ), ( z − y ), ( z − x ), ... ]
• The least number which when divided by x, y and z leaves the remainder a, b and c, respectively = [LCM of ( x , y , z )] − k
  where, k = (x − a) = ( y − b) = (z − c)
• The least number which when divided by x, y and z leaves the same remainder k in each case, is given by [LCM of ( x , y , z ) + k].