HCF & LCM

Scenario

When Swiggy batch-assigns orders to a delivery partner taking exactly 15 mins per drop, and another taking 20 mins, they sync up again precisely at the LCM of those times.

Mental model

HCF chops things into equal maximum pieces; LCM syncs repeating cycles.

Highest Common Factor finds the largest measuring stick that perfectly divides multiple quantities. Lowest Common Multiple finds the earliest future moment when independent periodic events align.

Formula

HCF(a, b) x LCM(a, b) = a x b (valid for exactly two numbers only). HCF by prime factorisation: take LOWEST power of COMMON prime factors. LCM by prime factorisation: take HIGHEST power of ALL prime factors. HCF of fractions = HCF(Numerators) / LCM(Denominators). LCM of fractions = LCM(Numerators) / HCF(Denominators). Remainder trick: to find HCF(a, b) where a > b, subtract remainder repeatedly (Euclidean algorithm): HCF(a, b) = HCF(b, a mod b).

The product rule ONLY works for two numbers. For word problems: if equal groups are asked, think HCF. If simultaneous events / periodic syncing are asked, think LCM. If dividing with remainders, subtract the remainder first then find HCF.

Pattern discovery

Compare HCF * LCM with the product of the two numbers.

• HCF(12, 18) = 6. LCM(12, 18) = 36.
• 12 x 18 = 216
• 6 x 36 = 216

What do you notice about HCF x LCM vs the product of the two numbers?

Rule: The product of two numbers always equals the product of their HCF and LCM. HCF captures the common prime factors; LCM captures all prime factors at highest powers.

Worked example

Problem: Find the HCF and LCM of 36 and 60 using prime factorisation.

1. Prime factorise: 36 = 2^2 x 3^2. 60 = 2^2 x 3 x 5.
2. HCF: take LOWEST powers of COMMON primes. Common primes: 2 and 3. HCF = 2^2 x 3^1 = 4 x 3 = 12.
3. LCM: take HIGHEST powers of ALL primes. All primes: 2, 3, 5. LCM = 2^2 x 3^2 x 5 = 4 x 9 x 5 = 180.
4. Sanity-check using product rule: HCF x LCM = 12 x 180 = 2160. Product: 36 x 60 = 2160. Matches.

Answer: HCF = 12, LCM = 180.

Problem: Find the greatest number that divides 70, 100, and 130 leaving remainder 10 in each case.

1. If remainder is 10 each time, subtract: 70 - 10 = 60, 100 - 10 = 90, 130 - 10 = 120.
2. We need HCF(60, 90, 120). Prime factorise: 60 = 2^2 x 3 x 5. 90 = 2 x 3^2 x 5. 120 = 2^3 x 3 x 5.
3. HCF = 2^1 x 3^1 x 5^1 = 30.
4. Sanity-check: 60/30=2, 90/30=3, 120/30=4 - all divide evenly. So 30 divides 70, 100, 130 with remainder 10.

Answer: The greatest such number is 30.

Shortcuts

• Prime Factorization Speed Run: For HCF, take the LOWEST power of common prime factors. For LCM, take the HIGHEST power of ALL prime factors. (a = 2^3 x 3^2, b = 2^2 x 3^3. HCF = 2^2 x 3^2 = 36. LCM = 2^3 x 3^3 = 216.)
• Difference Trick for HCF: The HCF of two numbers must be a factor of their difference. (HCF of 81 and 108. Difference is 27. Factors of 27: 27, 9, 3, 1. Since 81 and 108 are both divisible by 27, HCF = 27.)

Common mistakes

• Applying Product Rule to 3 Numbers: HCF x LCM = Product ONLY works for exactly two numbers. For three numbers a, b, c, HCF(a,b,c) x LCM(a,b,c) does not equal a x b x c.
• Confusing Greatest with HCF in word problems: If a question asks for the 'greatest number' that perfectly divides multiple values, that is HCF. If it asks when multiple periodic events next coincide, that is LCM.

Glossary

syncs

Making multiple events happen at the exact same time.

periodic

Happening repeatedly at regular intervals.

coincide

To happen at the exact same time or place.

Recall questions

• What is the HCF of two co-prime numbers?
• How do you find the LCM of fractions?
• If HCF(a,b) is 5 and a x b is 150, what is LCM(a,b)?

Questions & answers

Three bells toll at intervals of 12, 15, and 18 minutes. If they start tolling together at 9:00 AM, when will they toll together again?

12:00 PM

Approach: Find LCM of 12, 15, 18. LCM = 180 minutes = 3 hours. 9:00 AM + 3 hours = 12:00 PM.

Find the greatest number which on dividing 1657 and 2037 leaves remainders 6 and 5 respectively.

127

Approach: Subtract remainders: 1657-6=1651, 2037-5=2032. Find HCF(1651, 2032). Difference = 381 = 3 x 127. Check: 127 divides both 1651 (=13x127) and 2032 (=16x127). HCF = 127.

Continue learning

Previous: Number System & Divisibility

Return to Aptitude Roadmap