HCF & LCM Notes

Last reviewed 16 Sept 2026 · 5 min read

Definitions

Factor (divisor) — a number that divides another exactly.
Multiple — product of a number with an integer.
HCF (Highest Common Factor) / GCD (Greatest Common Divisor) — the largest number that divides all given numbers exactly.
LCM (Least Common Multiple) — the smallest number divisible by all given numbers.
Co-prime numbers — HCF = 1 (their LCM = product).

Methods

Prime factorisation

HCF = product of common prime factors with lowest powers.
LCM = product of all prime factors with highest powers.

Division (Euclid's) method for HCF

Divide the larger by the smaller; divide the divisor by the remainder; repeat until remainder is 0 — the last divisor is the HCF.

Common division method for LCM

Divide the numbers simultaneously by common primes until no two share a factor; LCM = product of divisors and remaining quotients.

Key relations and properties

FormulaHCF and LCM relations

For two numbers: $HCF \times LCM = product of the numbers$ (not valid in general for three or more numbers)
HCF always divides LCM
HCF ≤ smallest number; LCM ≥ largest number
Fractions: $HCF = \frac{HCF of numerators}{LCM of denominators}$ , $LCM = \frac{LCM of numerators}{HCF of denominators}$
Decimals: equalise decimal places, find HCF/LCM as integers, then restore decimal places

Standard problem types

FormulaRemainder problems

Greatest number dividing a, b, c exactly → HCF(a, b, c)
Greatest number dividing a, b, c leaving the same remainder → HCF of the differences $∣ a - b ∣, ∣ b - c ∣, ∣ a - c ∣$
Greatest number dividing a, b, c leaving remainders p, q, r → HCF $(a - p, b - q, c - r)$
Smallest number divisible by a, b, c → LCM(a, b, c)
Smallest number which when divided by a, b, c leaves the same remainder r → LCM + r
Smallest number which when divided by a, b, c leaves remainders a − k, b − k, c − k (constant difference k) → LCM − k
Greatest n-digit number divisible by a, b, c → largest n-digit number − (its remainder when divided by LCM)
Smallest n-digit number divisible by a, b, c → smallest n-digit number + (LCM − remainder), if remainder ≠ 0

Applications

Bells, lights, runners meeting again → LCM of intervals.
Largest tile/scale/container to measure given lengths/volumes exactly → HCF.
Minimum number of square tiles for a floor → use HCF of dimensions as tile side.

Worked examples

Worked ExampleExample 1 — HCF and LCM by factorisation

Find the HCF and LCM of 72, 108 and 180.

Solution. $72 = 2^{3} \times 3^{2}$ ; $108 = 2^{2} \times 3^{3}$ ; $180 = 2^{2} \times 3^{2} \times 5$ HCF $= 2^{2} \times 3^{2} =$ 36; LCM $= 2^{3} \times 3^{3} \times 5 =$ 1080

Worked ExampleExample 2 — Euclid's method

Find the HCF of 1071 and 462.

Solution. $1071 = 462 \times 2 + 147$ ; $462 = 147 \times 3 + 21$ ; $147 = 21 \times 7 + 0$ → HCF = 21

Worked ExampleExample 3 — product relation

The HCF of two numbers is 12 and their LCM is 360. One number is 72. Find the other.

Solution. $\frac{12 \times 360}{72} =$ 60

Worked ExampleExample 4 — same remainder

Find the greatest number that divides 43, 91 and 183 leaving the same remainder.

Solution. Differences: 48, 92, 140 → HCF(48, 92, 140) = 4

Worked ExampleExample 5 — different remainders

Find the greatest number that divides 1657 and 2037 leaving remainders 6 and 5 respectively.

Solution. HCF(1651, 2032): $2032 = 1651 + 381$ ; $1651 = 381 \times 4 + 127$ ; $381 = 127 \times 3$ → 127

Worked ExampleExample 6 — smallest number with remainders

Find the smallest number which when divided by 12, 15 and 20 leaves remainder 7 in each case.

Solution. LCM(12, 15, 20) = 60 → 60 + 7 = 67

Worked ExampleExample 7 — constant difference

Find the smallest number which when divided by 6, 9 and 12 leaves remainders 4, 7 and 10 respectively.

Solution. Differences 6 − 4 = 9 − 7 = 12 − 10 = 2; LCM = 36 → 36 − 2 = 34

Worked ExampleExample 8 — bells

Three bells toll at intervals of 12, 18 and 30 minutes. If they toll together at 8:00 a.m., when will they next toll together?

Solution. LCM = 180 min = 3 h → 11:00 a.m.

Worked ExampleExample 9 — tiles

A room floor measures 6.24 m × 5.04 m. Find the largest square tile that fits exactly and the number of tiles.

Solution. HCF(624, 504) cm: $624 = 504 + 120$ ; $504 = 120 \times 4 + 24$ ; $120 = 24 \times 5$ → 24 cm Tiles $= \frac{624 \times 504}{24 \times 24} = 26 \times 21 =$ 546

Worked ExampleExample 10 — greatest four-digit number

Find the greatest four-digit number divisible by 15, 25 and 40.

Solution. LCM = 600; $9999 = 600 \times 16 + 399$ → $9999 - 399 =$ 9600

Worked ExampleExample 11 — HCF of fractions

Find the HCF of $\frac{3}{4}, \frac{9}{10}, \frac{15}{16}$ .

Solution. $\frac{HCF ( 3 , 9 , 15 )}{LCM ( 4 , 10 , 16 )} =$ 3/80

Downloaded from civilgyantests.com · Not for resale. Verify every code clause and date against the official source.

HCF & LCM