HCF & LCM

🔒 Log in to track

medium importance~1 Q in Tier 117 formulas⚡ 12 shortcuts4 subtopics

Overview Learn (4)Formulas (17)Examples (5)Practice (56)

Subtopic 4 of 4·← Standard word problems (tiles, bells, groups, divisible numbers)

Two-step LCM/HCF cases (extra condition, N-digit bounds)

🔒 Log in to track

The hardest CGL variants combine LCM/HCF with one extra condition:

LCM + remainder, further divisible by p: write $N = \text{LCM}\cdot k + r$ and solve $N \equiv 0 \pmod p$ for the smallest k.
Greatest/least n-digit number with properties: bound the LCM multiples inside the digit range first, then apply the extra condition.
Given HCF and LCM, reconstruct numbers: numbers $= h\,a$ and $h\,b$ with $\gcd(a,b) = 1$ and $ab = \frac{\text{LCM}}{h}$ ; use the sum/difference to pick the pair.
Count of possible pairs: count co-prime factor pairs of LCM/HCF.

📖 Notes 🧩 4 question types ⚡ Formulas 🎯 14 practice Q

Detailed notes

The master frame: N = LCM·k + r

Every remainder question reduces to $N = L \cdot k + r$ , where $L$ is the LCM of the divisors. $k = 1$ gives the least positive value; larger k gives later values in the same pattern. Any extra condition simply pins down k.

Extra condition: the number must also be divisible by p

Write $N = Lk + r$ .
Try $k = 1, 2, 3, \dots$ until $Lk + r$ is divisible by p (or solve $Lk \equiv -r \pmod p$ ). Example: N divided by 4, 6, 9 leaves remainder 1 in each case, and N is divisible by 11. $L = 36$ → $N = 36k + 1$ : k = 7 gives $253 = 11 \times 23$ ✓ → N $= 253$ .

Least / greatest n-digit numbers

Take $L =$ LCM of the divisors.
Least n-digit: divide 10…0 by L and step up to the next multiple.
Greatest n-digit: divide 99…9 by L and subtract the remainder.
With a remainder r, fit $N = Lk + r$ inside the digit range. Example: least 5-digit number divisible by 32, 36, 40, 45, 48 → $L = 1440$ ; $10000 = 6 \times 1440 + 1360$ → add $1440 - 1360 = 80$ → 10080.

Rebuilding numbers from HCF and LCM

Numbers with HCF h can be written $ha$ and $hb$ with $\gcd(a, b) = 1$ , and $ab = \frac{\text{LCM}}{h}$ .

Compute $ab$ .
List the factor pairs of $ab$ ; keep only the co-prime pairs.
Use the given sum or difference to pick the pair; the numbers are $ha$ and $hb$ . Example: HCF 5, LCM 495, sum 100 → $ab = 99$ → pairs (1, 99) and (9, 11); the sum needs $a + b = 20$ → (9, 11) → numbers 45 and 55.

How many pairs are possible?

Count the co-prime factor pairs of $ab = \frac{\text{LCM}}{h}$ (or $\frac{\text{product}}{h^2}$ when the product is given). Do not forget the pair (1, ab) itself, and never count (a, b) and (b, a) as different pairs. Example: product 2160, HCF 12 → $ab = \frac{2160}{144} = 15$ → (1, 15), (3, 5) → 2 pairs.

Same unknown remainder → HCF of the pairwise differences

If a, b, c leave the same (unknown) remainder, the answer divides $a - b$ , $b - c$ , $a - c$ — so it is the HCF of the pairwise differences. The common remainder is then a mod (answer). Example: greatest number dividing 84, 156, 204 leaving the same remainder: differences 72, 120, 48 → HCF $= 24$ , and the remainder is $84 \bmod 24 = 12$ in each case.

Quick revision

$N = Lk + r$ : extra condition → test k = 1, 2, 3, …
n-digit: step up from 10…0 or step down from 99…9.
Rebuild: numbers $= ha, hb$ with $ab = \text{LCM} \div h$ , co-prime parts.
Pair count: co-prime factor pairs of LCM/H (or product/H²).
Unknown same remainder → HCF of the pairwise differences.

Types of questions asked

Every way this subtopic shows up in exams — how to recognise it, the formula or logic to use, and a solved example.

Type 1: Least / greatest n-digit number divisible by a setvery common2 practice Q

How to spot it:

'Find the least four-digit number exactly divisible by 12, 15, 20' or the greatest such five-digit number.

\text{least: next multiple of } L \ge 10^{n-1}; \qquad \text{greatest: } 10^n - 1 - ((10^n - 1) \bmod L), \quad L = \text{LCM}

Take L = LCM of the divisors.
Least: divide the smallest n-digit number by L, subtract the remainder from L, add to the base.
Greatest: divide 99…9 by L and subtract the remainder.
Add the remainder r first if the question says 'leaves remainder r': work with Lk + r inside the range.

Why: multiples of the LCM are exactly the numbers divisible by every divisor; the digit bounds just pick where to stop.

Example: Find the least five-digit number exactly divisible by 32, 36, 40, 45 and 48.

$L = 1440$ ; $10000 = 6 \times 1440 + 1360$ → add $1440 - 1360 = 80$ → 10080.

Type 2: LCM + r with an extra condition (divisible by p, or a digit bound)common2 practice Q

How to spot it:

'…leaves remainder r in each case, and is exactly divisible by 11' — an LCM + r question with one more filter.

N = Lk + r, \qquad Lk + r \equiv 0 \pmod p \ \Rightarrow\ \text{smallest } k \text{ wins}

Write N = L·k + r with L = LCM of the divisors.
Test k = 1, 2, 3, … until L·k + r is divisible by p (small k values click fast).
If an n-digit bound is given, start k just above (bound − r) ÷ L.

Why: N − r is a multiple of L by construction; the extra condition only chooses which multiple.

Example: Find the least number which divided by 4, 6 and 9 leaves remainder 1 in each case, and is exactly divisible by 11.

$L = 36$ → N = 37, 73, 109, …, and $253 = 11 \times 23$ (k = 7) → 253.

Type 3: Rebuild numbers from HCF & LCM; count possible pairscommon4 practice Q

How to spot it:

HCF and LCM are given, plus a sum/difference/bound — find the numbers or count how many pairs fit.

\text{numbers} = ha, hb;\ \ \gcd(a, b) = 1,\quad ab = \frac{\text{LCM}}{h} \ \left(= \frac{\text{product}}{h^2}\right)

Compute $ab = \text{LCM} \div h$ (or product ÷ h²).
List factor pairs of ab; KEEP only co-prime pairs — the rest are impossible.
Use the given sum/difference/bound to pick the pair; numbers are h·a and h·b.
To count pairs: count the surviving co-prime pairs.

Why: two numbers with HCF h are h times two co-prime parts, and those parts must multiply to LCM ÷ h.

Example: The HCF and LCM of two numbers are 5 and 495 and their sum is 100. Find the numbers.

$ab = 99$ → co-prime pairs (1, 99), (9, 11); sum needs $a + b = 20$ → (9, 11) → numbers 45 and 55.

Type 4: Greatest number dividing with the same unknown remaindercommon2 practice Q

How to spot it:

'Find the greatest number which divides a, b, c leaving the same remainder in each case' — no remainder is given.

\text{answer} = \gcd(a - b,\ b - c,\ a - c), \qquad \text{remainder} = a \bmod \text{answer}

Take the pairwise differences of the numbers.
Their HCF is the greatest such divisor.
The common remainder is any number mod that HCF — check it is the same for all.

Why: if a and b leave the same remainder r, their difference is exactly divisible by the divisor; so the divisor is a common factor of all differences.

Example: Find the greatest number which divides 84, 156 and 204 leaving the same remainder in each case.

Differences: 72, 48, 120 → HCF $= 24$ ; remainder $84 \bmod 24 = 12$ (same for all three).

Formulas

Extra divisibility condition

N = Lk + r,\ N \equiv 0 \pmod p \ \Rightarrow\ Lk \equiv -r \pmod p

Reconstruction

ab = \frac{\text{LCM}}{h},\quad \gcd(a, b) = 1

Pair count

\#\{(a,b): ab = M,\ \gcd(a,b)=1,\ a \le b\}

Shortcut tricks

⚡ Solve the little congruence for k

Once N = LCM·k + r, only k's remainder mod p matters — test k = 1, 2, 3, … until it clicks.

Example: Find the least number which when divided by 6, 7, 8, 9 and 12 leaves remainder 1 in each case, and is also divisible by 13.

LCM = 504, so $N = 504k + 1$ . $504 \equiv -3 \pmod{13}$ ⇒ $-3k + 1 \equiv 0$ ⇒ $3k \equiv 1$ ⇒ $k = 9$ . $N = 4537$ .

⚡ N-digit multiple scan

For least n-digit: divide the smallest n-digit number by the LCM, go to the next multiple. For greatest: reduce the largest n-digit number by its remainder.

Example: Find the least five-digit number exactly divisible by 32, 36, 40, 45 and 48.

LCM $= 1440$ . $10000 \div 1440 = 6$ remainder $1360$ ⇒ answer $= 7 \times 1440 = 10080$ .

⚡ Sum or difference picks the pair

With LCM/HCF and a sum (or difference) given, list co-prime pairs of LCM/HCF and match the sum.

Example: Two numbers have HCF 5, LCM 495 and sum 100. Find their difference.

$a b = \frac{495}{5} = 99$ , co-prime pairs (1, 99) and (9, 11). Sum $5(a+b) = 100$ ⇒ (9, 11) ⇒ numbers 45, 55 ⇒ difference 10.

Where students lose marks

Answering LCM $+ r$ when the extra condition demands a larger multiple of the LCM.
Listing factor pairs of LCM/HCF without checking co-primality.
Forgetting the (1, M) pair when counting possibilities, or counting (a, b) and (b, a) twice.
Missing that HCF must divide the sum/difference — a quick sanity filter for options.

Practice sets — 14 questions

Sets of 10, mixed across the question types above. Each answer comes with a step-by-step explanation.

Topic test · 10 questions

Suggested time 11 min · wrong answers go to your mistake notebook automatically.