Important Formula: HCF & LCM

Table of Contents
1. HCF and LCM Formula
2. Definitions and Basic Ideas
3. HCF by Prime Factorization Method
4. HCF by Division (Euclidean) Method
5. LCM by Prime Factorization Method
6. LCM by Division (Ladder) Method
7. Questions and Answers of HCF and LCM
8. Additional Properties and Useful Points
View more

HCF and LCM Formula

The product of two positive integers is equal to the product of their highest common factor and their least common multiple.

Relation: Product of two numbers = (HCF of the two numbers) × (LCM of the two numbers)

Definitions and Basic Ideas

Highest Common Factor (HCF) of two or more integers is the largest integer that divides each of them exactly (without remainder).

Least Common Multiple (LCM) of two or more integers is the smallest positive integer that is exactly divisible by each of them.

Note: The formula product = HCF × LCM holds exactly for two integers. It does not generalise as a straightforward equality involving the product of more than two integers without adjustments.

How to find HCF

You may find the HCF of integers by any of these standard methods:

• Prime factorization: Factor each number into primes and take the product of common primes with the lowest powers.
• Division (Euclidean) method: Repeatedly apply division to reduce the pair until the remainder becomes zero; the last non-zero divisor is the HCF.
• Using the product relation: If you know the LCM of two numbers, then HCF = Product of the two numbers / LCM.

How to find LCM

Common methods to compute LCM are:

• Prime factorization: Factor each number into primes and take the product of all primes raised to the highest powers that occur in any factorisation.
• Division (also called the ladder or continued division) method: Divide by common prime factors simultaneously until all quotients are 1; multiply the divisors used.
• Using the product relation: If you know the HCF of two numbers, then LCM = Product of the two numbers / HCF.

HCF by Prime Factorization Method

Procedure:

• Express each number as a product of prime factors.
• Identify prime factors common to all numbers.
• For each common prime, take the lowest power that appears in all factorizations.
• Multiply those common prime powers to get the HCF.

Example: Find HCF(100, 125, 180).
Prime factorisations:
\(100 = 2 \times 2 \times 5 \times 5 = 2^2 \times 5^2\)
\(125 = 5 \times 5 \times 5 = 5^3\)
\(180 = 2 \times 2 \times 3 \times 3 \times 5 = 2^2 \times 3^2 \times 5\)
Common primes: only 5 appears in all three. The minimum power of 5 present in all is \(5^1\).
Therefore, HCF(100, 125, 180) = 5.

HCF by Division (Euclidean) Method

Procedure for two numbers:

• Divide the larger number by the smaller number and obtain the remainder.
• Replace the larger number by the smaller number and the smaller by the remainder.
• Repeat the division until the remainder is zero.
• The last non-zero remainder's divisor is the HCF.

Example: Find HCF of 120 and 180 using the Euclidean algorithm.
\(180 = 120 \times 1 + 60\)
\(120 = 60 \times 2 + 0\)
Remainder becomes zero; the last non-zero divisor is 60.
Therefore, HCF(120, 180) = 60.

LCM by Prime Factorization Method

Procedure:

• Factor each number into primes.
• For each distinct prime that appears in any factorisation, take the highest power of that prime occurring in any one factorisation.
• Multiply these highest powers to obtain the LCM.

Example: Find LCM(25, 35).
Prime factorisations:
\(25 = 5 \times 5 = 5^2\)
\(35 = 5 \times 7 = 5^1 \times 7^1\)
Highest powers: \(5^2\) (from 25) and \(7^1\) (from 35).

Therefore, LCM = \(5^2 \times 7 = 25 \times 7 = 175\).

LCM by Division (Ladder) Method

Procedure (for two or more numbers):

• Write the numbers in a row.
• Divide by a common prime (or any prime dividing at least one of the numbers), write the quotients below.
• Continue dividing the row by primes until all entries become 1.
• Multiply all the divisors used; the product is the LCM.

Example: Find LCM(25, 35) by the division method.
Divide by 5:
5 | 25, 35
Quotients: 5, 7
Divide by 5 again where applicable:
5 | 5, 7
Quotients: 1, 7
Divide by 7:
7 | 1, 7
Quotients: 1, 1
Multiply the divisors used: \(5 \times 5 \times 7 = 175\).
Therefore, LCM(25, 35) = 175.

Questions and Answers of HCF and LCM

Q1: Calculate the highest number that will divide 43, 91 and 183 and leaves the same remainder in each case
(a) 4
(b) 7
(c) 9
(d) 13
Ans: (a)
Here the trick is
Find the Differences between number
Get the HCF (that differences)
We have here 43, 91 and 183
So differences are
183 - 91 = 92,
183 - 43 = 140,
91 - 43 = 48.
Now, HCF (48, 92 and 140)
48 = 2 × 2 × 2 × 2 × 3
92 = 2 × 2 × 23
140 = 2 × 2 × 5 × 7
HCF = 2 × 2 = 4
And 4 is the required number.

Q2: The greatest possible length which can be used to measure exactly the lengths 7 m, 3 m 85 cm, 12 m 95 cm is:
(a) 25 cm
(b) 15 cm
(c) 35 cm
(d) 55 cm
Ans: (c)
Required length = H.C.F. of 700 cm, 385 cm and 1295 cm = 35 cm.

Q3: Which of the following is greatest number of four digits which is divisible by 15, 25, 40 and 75 is:
(a) 9700
(b) 9600
(c) 9800
(d) 9650
Ans: (b)
Greatest number of 4-digits is 9999.
Now , find the L.C.M. of 15, 25, 40 and 75 i.e. 600.
On dividing 9999 by 600, the remainder is 399.
Hence, Required number (9999 - 399) = 9600.
Alternatively,
9999/600 = 16.66500
Ignore the decimal points, required number would be 16 * 600 = 9600

Additional Properties and Useful Points

• If two numbers are coprime (HCF = 1), then their LCM is the product of the numbers.
• HCF of a set of numbers divides any linear combination of those numbers.
• LCM of numbers is always a multiple of each number and never less than the largest number in the set.
• For more than two numbers, compute HCF and LCM pairwise or use prime factorisation across all numbers.

Final remark: Use prime factorisation when factor sizes are small and transparent; use the Euclidean method for large numbers or when handling only two numbers. The division (ladder) method is convenient for three or more numbers to get the LCM quickly.