HCF and LCM

HCF and LCM appear directly and as hidden steps (bells, remainders, LCM-based work rates) in nearly every placement paper. HCF (GCD) is the largest number dividing all the given numbers; LCM is the smallest number divisible by all of them.

Methods and key relations

Prime factorisation: HCF = product of the LOWEST powers of common primes; LCM = product of the HIGHEST powers of all primes.
Example: 12 = 2²×3, 18 = 2×3². HCF = 2×3 = 6, LCM = 2²×3² = 36.

Euclid's algorithm: HCF(a,b) = HCF(b, a mod b), repeated until remainder 0.

Relation	Formula
Two numbers	HCF × LCM = product of the two numbers
HCF of fractions	HCF(numerators) / LCM(denominators)
LCM of fractions	LCM(numerators) / HCF(denominators)
Bells/lights together	LCM of the intervals
Largest tile / measure	HCF of the dimensions

Check: 12 and 18 → HCF 6, LCM 36, and 6 × 36 = 216 = 12 × 18. ✓

Exam Tricks & Tips

• 🎯 HCF × LCM = product works for exactly TWO numbers, not three.
• 🎯 "Rings/tolls together" → LCM; "largest that divides / greatest measure" → HCF.
• 🎯 Number that leaves the same remainder r on division by a, b, c = k·LCM(a,b,c) + r.
• 🎯 Greatest number dividing a, b, c leaving remainders p, q, s = HCF(a−p, b−q, c−s).
• 🎯 LCM of fractions = LCM(numerators)/HCF(denominators); e.g. LCM of 1/2 and 3/4 = 3/2.
• ❌ Don't compute LCM of fractions by taking LCM of numerators over LCM of denominators — the denominator uses HCF.

Expected exam pattern: bells/traffic-lights meeting, largest tile to pave a floor, smallest number leaving fixed remainders. 1 to 2 questions, ~50 seconds each.

Quick recap: Prime-factorise, take lowest powers for HCF and highest for LCM; remember HCF×LCM = product (two numbers), and LCM = "together" while HCF = "largest divides".

Q1. Define HCF and LCM.
A1. HCF is the largest number dividing all the given numbers; LCM is the smallest number divisible by all of them.

Q2. HCF from prime factors?
A2. Product of the lowest powers of the common primes.

Q3. LCM from prime factors?
A3. Product of the highest powers of all primes present.

Q4. HCF and LCM of 12 and 18?
A4. HCF = 6, LCM = 36.

Q5. Relation between HCF, LCM and two numbers?
A5. HCF × LCM = product of the two numbers.

Q6. If two numbers are 24 and 36, and HCF is 12, find the LCM.
A6. LCM = (24 × 36) / 12 = 72.

Q7. Bells ring every 6, 8 and 12 minutes; when do they next ring together?
A7. After LCM(6, 8, 12) = 24 minutes.

Q8. Largest tile to exactly pave a 6 m by 9 m floor?
A8. HCF(600 cm, 900 cm) = 300 cm side.

Q9. LCM of the fractions 1/2 and 3/4?
A9. LCM(1,3) / HCF(2,4) = 3/2.

Q10. HCF of fractions 2/3 and 4/9?
A10. HCF(2,4) / LCM(3,9) = 2/9.

Q11. Euclid's algorithm in one line?
A11. HCF(a, b) = HCF(b, a mod b), repeated until the remainder is 0.

Q12. Smallest number leaving remainder 3 on division by 5, 6 and 8?
A12. LCM(5,6,8) + 3 = 120 + 3 = 123.

HCF and LCM look like school revision, but placement setters dress them up as "largest tile", "bells ringing together" and "minimum students" word problems. Knowing which one the wording demands — and computing it in one line — is the whole skill.

What this topic tests: computing HCF/LCM fast via prime factorisation, choosing HCF vs LCM from the story, and using the identity that links them.

The method

Beginner — the definitions that decide everything

• HCF (GCD): the largest number dividing all given numbers. Use it when you want the biggest common size or to split into equal groups.
• LCM: the smallest number that all given numbers divide. Use it when things repeat and must coincide ("again together", "minimum length").

Prime-factorisation recipe: HCF = product of lowest powers of common primes; LCM = product of highest powers of all primes.
72 = 2³·3², 120 = 2³·3·5 → HCF = 2³·3 = 24, LCM = 2³·3²·5 = 360.

Intermediate — the Euclidean algorithm (fast HCF)

For two awkward numbers, repeatedly replace the pair by (smaller, remainder):
HCF(1071, 462): 1071 mod 462 = 147; 462 mod 147 = 21; 147 mod 21 = 0 → HCF = 21. This beats factorising large numbers.

Advanced — the master identity and fractions

For two numbers, HCF × LCM = product of the numbers. So given any three of {a, b, HCF, LCM} you get the fourth.

• HCF of fractions = HCF(numerators) / LCM(denominators).
• LCM of fractions = LCM(numerators) / HCF(denominators).
• "Numbers in ratio 3:4 with HCF 5" means the numbers are 15 and 20 (multiply ratio terms by the HCF).

Worked example

The traffic lights change every 48, 72 and 108 seconds. If they change together at 8:00:00, when next? "Together again" → LCM. 48 = 2⁴·3, 72 = 2³·3², 108 = 2²·3³. LCM = 2⁴·3³ = 16·27 = 432 s = 7 min 12 s. Next at 8:07:12.

Where it appears

TCS NQT and Infosys arithmetic sections; Amazon/Accenture warm-up rounds; classic "bells", "tiling a floor", "stacking books", "runners on a track meeting at the start" problems.

Speed tricks and shortcuts

• Story cue: "biggest/each/equal groups → HCF; again/together/minimum length → LCM."
• To LCM three numbers fast, LCM them two at a time.
• "Largest number dividing a, b, c leaving the same remainder" = HCF of the differences (a−b, b−c).
• "Least number leaving remainder r with each divisor" = LCM(divisors) + r.

Key formulas

• HCF × LCM = product of the two numbers (for two numbers only).
• HCF = product of lowest powers of common primes; LCM = product of highest powers of all primes.
• HCF of fractions = HCF(numerators)/LCM(denominators); LCM of fractions = LCM(numerators)/HCF(denominators).
• Largest number dividing a, b, c leaving same remainder r: HCF(a−b, b−c, c−a).
• Smallest number leaving remainder r with each divisor: LCM(divisors) + r.
• Co-prime numbers ⇒ HCF = 1, LCM = product.

Usage: use HCF×LCM = product to find the missing quantity when three of four are known.

Worked Example

Problem: Find the greatest number that divides 2011 and 2623, leaving remainders 9 and 5 respectively.

Solution: If a number d divides 2011 leaving remainder 9, then d divides 2011 − 9 = 2002 exactly. Likewise d divides 2623 − 5 = 2618 exactly. So the required number is the HCF of 2002 and 2618.

Prime-factorise both:

• 2002 = 2 × 7 × 11 × 13
• 2618 = 2 × 7 × 11 × 17

Common factors: 2, 7, 11. So HCF = 2 × 7 × 11 = 154.

Verify: 2002 ÷ 154 = 13 and 2618 ÷ 154 = 17, both exact. Also the divisor must be larger than every remainder (154 > 9 and 154 > 5), so the answer is consistent.

Answer: 154.