HCF, LCM & Remainder Theorems

HCF, LCM and remainders drive a steady 2–3 CAT QA questions and underpin cyclencity and modular-arithmetic problems. The theory is compact; the payoff is high once you know which tool a question needs.

HCF and LCM essentials

• HCF (GCD) = product of primes to their lowest powers; LCM = primes to their highest powers.
• For two numbers: HCF × LCM = product of the numbers. (So one is found from the other three.)
• Fractions: LCM = LCM(numerators)/HCF(denominators); HCF = HCF(numerators)/LCM(denominators).

Remainder problem types

Type	Answer form
Same remainder r on division by a, b, c	Number = k·LCM(a,b,c) + r
Different remainders, same deficit d	Number = k·LCM − d
"Largest number dividing a,b,c leaving same remainder"	HCF of the differences (a−b), (b−c)
Remainder of a product/power	Multiply/reduce remainders (modular arithmetic)

Method

1. Identify whether the question is HCF-type (grouping, "largest that divides") or LCM-type ("smallest that is divisible", cyclic events meeting).
2. For remainders, spot the pattern: same remainder → LCM + r; same deficit → LCM − d.
3. For "same remainder from a,b,c", take the HCF of pairwise differences.

Exam Tricks & Tips

• 🎯 HCF × LCM = product of the two numbers — the fastest way to get a missing value (two numbers only).
• 🎯 "Bells toll together / lights blink together" = LCM of the intervals; the count in T seconds = T/LCM + 1 (including the start).
• 🎯 Same remainder on a, b, c ⇒ number = LCM·k + r. Pick the smallest by k = 0 or 1 as asked.
• 🎯 Largest divisor leaving equal remainders = HCF of the differences (a−b, b−c) — the remainder cancels in the difference.
• 🎯 Reduce remainders before multiplying: rem(A·B mod n) = rem(rem(A)·rem(B) mod n) — keeps numbers small.
• ❌ Common mistake: using HCF×LCM = product for three or more numbers — that identity holds only for two numbers.

Expected exam pattern

2–3 QA questions: smallest/largest number with given divisibility-remainder conditions, co-prime grouping, "when do events coincide", and remainder of large powers. MCQ + TITA. Frequently overlaps with cyclicity.

Quick recap

HCF = lowest powers, LCM = highest powers; for two numbers HCF×LCM = their product. Remainders: same remainder → LCM·k + r, same deficit → LCM − d, equal-remainder divisor → HCF of differences. Reduce remainders before combining powers/products.

Cover the answer, recall, then check. 12 cards on HCF, LCM and remainders.

Q1. How do you build HCF and LCM from prime factorisations?
A1. HCF = primes to lowest powers; LCM = primes to highest powers.

Q2. The HCF–LCM product identity (two numbers)?
A2. HCF × LCM = product of the two numbers.

Q3. Does HCF×LCM = product work for three numbers?
A3. No — only for exactly two numbers.

Q4. LCM of fractions formula?
A4. LCM(numerators) ÷ HCF(denominators).

Q5. HCF of fractions formula?
A5. HCF(numerators) ÷ LCM(denominators).

Q6. Number leaving the same remainder r on division by a, b, c?
A6. k·LCM(a,b,c) + r.

Q7. "Bells toll together" — which tool?
A7. LCM of the intervals; count in T seconds = T/LCM + 1 (with the start).

Q8. Largest number dividing a, b, c leaving the same remainder?
A8. HCF of the pairwise differences (a−b), (b−c).

Q9. Numbers give different remainders but the same deficit d — form?
A9. k·LCM − d.

Q10. How do you find rem(A·B mod n)?
A10. rem(rem(A)·rem(B) mod n) — reduce each factor first.

Q11. Is HCF a grouping tool or a coincidence tool?
A11. HCF = "largest that divides / grouping"; LCM = "smallest divisible / events coincide".

Q12. The classic HCF–LCM mistake?
A12. Applying HCF×LCM = product to three or more numbers.

HCF, LCM, and remainders are the "real-world" face of Number System — bells ringing together, tiles fitting a floor, numbers leaving a fixed remainder. The confusion students face is which tool when: LCM for "events coinciding / smallest common", HCF for "largest common size / grouping". Remainder problems then layer on modular arithmetic, where CAT's classic patterns (same remainder, remainder theorems) give instant shortcuts.

What this tests

Command of HCF/LCM (computation, relationships, word-problem recognition) and remainder techniques (modular reduction, common-remainder patterns, and standard theorems).

The method

Beginner — compute and relate HCF and LCM

Via prime factorisation: HCF = product of common primes to their lowest powers; LCM = all primes to their highest powers. Key relationship for two numbers: HCF × LCM = product of the two numbers. Recognise the word cues: "largest tile / maximum students per group / greatest common" → HCF; "bells toll together / smallest number divisible by all / laps meeting" → LCM.

Intermediate — the standard remainder word-patterns

• "Number leaving remainder r when divided by a, b, c" → the number = k·LCM(a,b,c) + r. Find the required value in range from this form.
• "Leaves the same remainder r with each" but r unknown → the differences are divisible by the divisor, so the divisor divides the pairwise differences → use HCF of differences.
• "Largest number dividing a, b, c leaving remainders r₁, r₂, r₃" → HCF of (a−r₁), (b−r₂), (c−r₃).

Advanced — the FAST CAT approach: modular arithmetic and remainder theorems

• Reduce before you multiply: to find (large product) mod n, take each factor mod n first. E.g., 17 × 23 mod 5 = 2 × 3 mod 5 = 6 mod 5 = 1.
• Negative remainders speed things up: 23 mod 12 = −1 (since 23 = 24 − 1), so 23^n mod 12 = (−1)^n — huge for powers.
• Fermat's Little Theorem: if p is prime and gcd(a,p)=1, then a^(p−1) ≡ 1 (mod p) — collapses big exponents. E.g., a^100 mod 7: 100 = 6·16 + 4, and a^6 ≡ 1, so a^100 ≡ a^4 (mod 7).
• Chinese Remainder / splitting: for mod of a composite, work modulo its coprime factors and combine.
• Remainder of a^n: use cyclicity of remainders (the pattern repeats with a fixed period).

Worked example

Question: Find the smallest number that leaves a remainder of 3 when divided by 5, 6, and 8.
"Same remainder 3 with each divisor" → number = k·LCM(5,6,8) + 3. LCM(5,6,8): 5 = 5, 6 = 2·3, 8 = 2³ → LCM = 2³·3·5 = 120. Smallest such number (k=1, and we want the smallest positive that actually leaves remainder 3, i.e., bigger than 3): 120·1 + 3 = 123. (Check: 123 = 24·5+3, 20·6+3, 15·8+3 ✓.) The LCM-plus-remainder template gives it in one line. Answer: 123.

CAT relevance

HCF/LCM/remainder questions are a staple of CAT QA (Number System is heavily weighted), and remainder theorems (Fermat, cyclicity, negative remainders) appear in the harder problems that separate high scorers. Recognising the word-pattern that selects HCF vs LCM is a pure speed edge.

Speed tricks & shortcuts

• HCF × LCM = product of the two numbers (two-number problems).
• Word cue: "largest common / grouping" → HCF; "coincide / smallest common" → LCM.
• "Same remainder, unknown" → HCF of the differences.
• Reduce each factor mod n before multiplying; use negative remainders for powers.
• Fermat: a^(p−1) ≡ 1 (mod p) collapses large exponents. Mnemonic — "Reduce, then compute."

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: (a) Find the largest number that divides 2011 and 2623 leaving the same remainder in each case. (b) Find the smallest number which when divided by 12, 15, and 20 leaves remainder 5 in each case.

Solution:
(a) "Same remainder" trick: if a number d divides both A and B leaving the SAME remainder r, then d divides their DIFFERENCE (B − A) exactly (the remainders cancel). So the required largest d is the HCF of the differences.
Difference = 2623 − 2011 = 612.
The largest number dividing both with equal remainder is the largest divisor of 612 — but we want the number itself, which is HCF of the relevant differences. With only two numbers, d = the greatest divisor giving a valid remainder = HCF, so d must divide 612. The LARGEST such d is 612 itself? Check remainder: 2011 ÷ 612 = 3 remainder 175; 2623 ÷ 612 = 4 remainder 175 — same remainder 175 ✓. So the largest number is 612.

(b) "Same remainder 5 for several divisors" trick: a number leaving remainder 5 when divided by 12, 15, and 20 is of the form (common multiple of 12, 15, 20) + 5. The smallest such (positive, exceeding the divisors) uses the LCM.
LCM(12, 15, 20): 12 = 2^2·3, 15 = 3·5, 20 = 2^2·5. LCM = 2^2 · 3 · 5 = 60.
Smallest number = LCM + remainder = 60 + 5 = 65.
Check: 65 ÷ 12 = 5 r5; 65 ÷ 15 = 4 r5; 65 ÷ 20 = 3 r5 — all remainder 5 ✓.

Answer: (a) 612 (the difference 2623 − 2011; it divides both leaving remainder 175). (b) 65 = LCM(12, 15, 20) + 5 = 60 + 5.