HCF and LCM

Number theory might look like pure abstraction, but HCF and LCM are the silent engines behind timetable synchronisation, tile-laying puzzles, cutting material without waste, and nearly every quantitative-aptitude section in SSC CGL, RRB NTPC, and IBPS exams.

Foundational Concepts

Definition: A factor (or divisor) of a number n is any integer that divides n exactly (with no remainder). Every number has 1 and itself as factors.

Definition: A multiple of n is any integer that is exactly divisible by n: multiples of 6 are 6, 12, 18, 24, ...

Definition: A prime number is a natural number greater than 1 with exactly two factors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ...

Definition: HCF (Highest Common Factor) — also called GCD (Greatest Common Divisor) — is the largest number that divides each of the given numbers exactly.

Definition: LCM (Least Common Multiple) is the smallest positive number that is divisible by each of the given numbers.

Divisibility Rules — The Speed Engine

Knowing these rules lets you instantly check whether large numbers are divisible without actual division.

Rule of 7 — worked step-by-step: Is 161 divisible by 7?

• Last digit = 1; double it = 2.
• Remaining number = 16.
• 16 − 2 = 14.
• 14 ÷ 7 = 2. Yes, divisible.

Rule of 11 — worked step-by-step: Is 91,861 divisible by 11?

• Odd positions (from left): 9, 8, 1 → sum = 18.
• Even positions: 1, 6 → sum = 7.
• Alternating difference: 18 − 7 = 11. Divisible by 11. ✓

Why these rules matter: In multi-part problems, checking divisibility saves you from calculating long divisions. Especially useful for factor/LCM problems and "how many numbers between X and Y are divisible by Z" questions.

Finding HCF — Two Methods

Method 1: Prime Factorisation

Write each number as a product of prime factors in exponential form. HCF = product of minimum powers of all common primes.

Question: Find HCF(72, 120, 180).
Solution:
Step 1: 72 = 2³ × 3²; 120 = 2³ × 3 × 5; 180 = 2² × 3² × 5.
Step 2: Common primes: 2 and 3.
Step 3: Min power of 2 = 2²; min power of 3 = 3¹.
Conclusion: HCF = 2² × 3 = 4 × 3 = 12.

Method 2: Euclidean Algorithm (fastest for large numbers)

Based on the property: HCF(a, b) = HCF(b, a mod b). Repeat until remainder = 0.

Question: Find HCF(252, 105).
Solution:
Step 1: 252 = 2 × 105 + 42 → HCF(252, 105) = HCF(105, 42).
Step 2: 105 = 2 × 42 + 21 → HCF(105, 42) = HCF(42, 21).
Step 3: 42 = 2 × 21 + 0 → HCF(42, 21) = 21.
Conclusion: HCF(252, 105) = 21.

Finding LCM — Two Methods

Method 1: Prime Factorisation

LCM = product of maximum powers of all primes appearing in any of the numbers.

Question: Find LCM(72, 120, 180).
Solution:
Step 1: 72 = 2³ × 3²; 120 = 2³ × 3 × 5; 180 = 2² × 3² × 5.
Step 2: Max power of 2 = 2³; max power of 3 = 3²; max power of 5 = 5¹.
Conclusion: LCM = 8 × 9 × 5 = 360.

Method 2: Using HCF

For two numbers only: LCM(a, b) = (a × b) / HCF(a, b).

Example: LCM(48, 18) = (48 × 18) / HCF(48, 18) = 864 / 6 = 144.

Important warning: The formula LCM × HCF = a × b applies ONLY for two numbers. For three or more numbers, this shortcut does NOT hold.

The Golden Relationship

HCF(a, b) × LCM(a, b) = a × b (for two numbers)

This identity is used to find one of HCF/LCM when the other and the product are known.

HCF and LCM of Fractions

	Formula
HCF of fractions	HCF(numerators) / LCM(denominators)
LCM of fractions	LCM(numerators) / HCF(denominators)

Example: HCF(3/4, 9/16, 6/8):

• HCF(3, 9, 6) = 3; LCM(4, 16, 8) = 16.
• HCF of fractions = 3/16.

Key Exam Problem Types

Type 1: Remainder Problems — Same Remainder

"Find the greatest number that divides 250, 435, and 630 leaving the same remainder."

Method: HCF of differences: |435 − 250| = 185; |630 − 435| = 195; |630 − 250| = 380.
HCF(185, 195, 380).
185 = 5 × 37; 195 = 5 × 39 = 5 × 3 × 13; 380 = 4 × 5 × 19.
HCF = 5.
Answer: 5.

Type 2: Smallest Number with Given Remainder — Same Divisors

"Find the smallest number that when divided by 6, 8, and 15 leaves a remainder of 2."

Method: LCM(6, 8, 15) + 2.
LCM(6, 8, 15): 6=2×3; 8=2³; 15=3×5. LCM = 2³ × 3 × 5 = 120.
Answer: 120 + 2 = 122.

Type 3: Trailing Zeros in n!

The number of trailing zeros in n! equals the number of times 10 is a factor of n! = min(power of 2, power of 5). Since powers of 2 always exceed powers of 5:

Trailing zeros in n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

Question: How many trailing zeros in 100!?
Solution: ⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24.

Question: How many trailing zeros in 50!?
Solution: ⌊50/5⌋ + ⌊50/25⌋ = 10 + 2 = 12.

Type 4: Number of Factors

If n = p₁^a × p₂^b × p₃^c × ..., then:

• Number of factors = (a+1)(b+1)(c+1)...
• Sum of factors = [(p₁^(a+1) − 1)/(p₁ − 1)] × [(p₂^(b+1) − 1)/(p₂ − 1)] × ...

Question: Find the number of factors of 360.
Solution:
360 = 2³ × 3² × 5¹.
Number of factors = (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24.

Question: Find the sum of factors of 72.
Solution:
72 = 2³ × 3².
Sum = [(2⁴−1)/(2−1)] × [(3³−1)/(3−1)] = [15/1] × [26/2] = 15 × 13 = 195.

Type 5: Bells / Lights / Signals Blinking Together

"Three bells ring at intervals of 6, 8, and 12 minutes. If they ring together at 7:00 AM, when will they next ring together?"

Method: LCM(6, 8, 12) = 24 minutes.
Answer: Next ring together at 7:24 AM.

Real-world example: Traffic light synchronisation in cities uses LCM logic — signal timings are chosen so that multiple lights re-synchronise at a predictable time, minimising bunching.

Type 6: Largest Tile / Plank / Ruler

"Find the largest square tile that can exactly tile a floor of 216 cm × 180 cm."

Method: HCF(216, 180) = ?
216 = 2³ × 3³; 180 = 2² × 3² × 5.
HCF = 2² × 3² = 4 × 9 = 36 cm.
The tile is 36 cm × 36 cm.

Properties and Useful Identities

• HCF(a, b) always divides LCM(a, b).
• HCF(a, b) divides every linear combination ma + nb (Bezout's identity).
• If HCF(a, b) = 1, a and b are coprime (no common factor other than 1). LCM = a × b.
• HCF(a, a+1) = 1 always (consecutive integers are always coprime).
• HCF(a², b²) = [HCF(a, b)]²; LCM(a², b²) = [LCM(a, b)]².

Common Misconceptions

Common misconception: "HCF is always smaller than both numbers." True — HCF ≤ min(a, b). But students sometimes compute LCM and report it as HCF.

Common misconception: "LCM × HCF = product holds for any number of terms." FALSE — it holds only for exactly two numbers. For 3 numbers a, b, c: LCM × HCF ≠ a × b × c in general.

Common misconception: "Every common factor of two numbers is their HCF." Only the LARGEST common factor is the HCF.

Every number you will ever meet in mathematics belongs to a nested family of sets, and knowing exactly which family it belongs to tells you what operations are safe to perform and how to solve the problems built around it.

Definition: The number system is the organised hierarchy of sets — Natural, Whole, Integer, Rational, Irrational, Real, Complex — where each larger set contains all the smaller ones plus new elements.

The hierarchy of number sets

A rational number's decimal expansion either terminates (1/4 = 0.25) or repeats (1/3 = 0.333…). An irrational number does neither — its decimal goes on forever without any repeating block.

Special subsets worth memorising

• Prime numbers: exactly two distinct divisors (1 and itself): 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
• Composite numbers: more than two divisors (4, 6, 8, 9, …).
• 1: neither prime nor composite.
• 2: the only even prime.
• Co-prime (relatively prime): two numbers whose HCF = 1. Example: 7 and 12 share no factor other than 1.

Properties of operations

Closure — an operation is closed on a set if the result is always in the same set:

• N is closed under + and × but not under − (3 − 5 = −2 ∉ N) or ÷ (3 ÷ 7 ∉ N).
• Z is closed under +, −, × but not ÷ (7 ÷ 3 ∉ Z).
• Q is closed under +, −, ×, and ÷ (excluding division by 0).

Commutativity: a + b = b + a and a × b = b × a. Subtraction and division are not commutative.

Associativity: (a + b) + c = a + (b + c). True for + and ×; not for − or ÷.

Distributivity: a × (b + c) = ab + ac.

Identities: 0 is the additive identity; 1 is the multiplicative identity.

Inverses: −a is the additive inverse of a; 1/a is the multiplicative inverse (a ≠ 0).

Divisibility rules

LCM and HCF

LCM (Least Common Multiple): the smallest positive integer divisible by both numbers. Used in problems involving cycles, scheduling, or finding when two periodic events coincide.

HCF / GCD (Highest Common Factor): the largest integer that divides both numbers without a remainder. Used in problems involving splitting into equal groups or simplifying fractions.

Golden property: LCM(a, b) × HCF(a, b) = a × b

Method 1 — Prime factorisation (preferred for exam)

Example: HCF and LCM of 18 and 24.

• 18 = 2¹ × 3²
• 24 = 2³ × 3¹
• HCF: take minimum power of each prime → 2¹ × 3¹ = 6
• LCM: take maximum power of each prime → 2³ × 3² = 72
• Check: 6 × 72 = 432 = 18 × 24 ✓

Method 2 — Euclidean algorithm (fast for two large numbers)

gcd(a, b) = gcd(b, a mod b), repeating until the remainder is 0.
Example: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6.

Remainder and modular arithmetic

For cyclic remainder problems, find the cycle length and use modular arithmetic.

Example: Find 2^10 mod 7.
Powers of 2 mod 7: 2, 4, 1, 2, 4, 1, … (cycle of length 3).
10 mod 3 = 1. So 2^10 mod 7 = 2¹ mod 7 = 2.

Fermat's little theorem: If p is prime and gcd(a, p) = 1, then a^(p−1) ≡ 1 (mod p). Useful for large exponents with prime moduli.

Wilson's theorem: (p−1)! ≡ −1 (mod p) for any prime p.

Unit-digit (last digit) patterns

The last digit of powers cycles with short periods:

Question: Unit digit of 7^100?
Cycle for 7: 7, 9, 3, 1 (length 4). 100 mod 4 = 0 → treat as the 4th position = 1.

Question: Unit digit of 3^25?
Cycle for 3: 3, 9, 7, 1 (length 4). 25 mod 4 = 1 → 1st position = 3.

Factorials and trailing zeros

n! = n × (n−1) × … × 2 × 1. By definition, 0! = 1.

Trailing zeros in n!: each trailing zero requires one factor of 10 = 2 × 5. Since factors of 2 are far more abundant than factors of 5, count only the factors of 5 using Legendre's formula:

Number of trailing zeros in n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …

Question: Trailing zeros in 100!?
= ⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24.

Surds and indices

Definition: A surd is an irrational number expressed using a radical, such as √2 or ³√5, that cannot be simplified to a rational number.

Index laws:

Law	Statement
Product	a^m × a^n = a^(m+n)
Quotient	a^m ÷ a^n = a^(m−n)
Power of a power	(a^m)^n = a^(mn)
Zero exponent	a^0 = 1 (a ≠ 0)
Negative exponent	a^(−n) = 1/a^n
Fractional exponent	a^(1/n) = ⁿ√a

Surd operations:

• √a × √b = √(ab)
• √a / √b = √(a/b)
• (√a)² = a
• Rationalising the denominator: multiply numerator and denominator by the conjugate. E.g., 1/(√3+1) × (√3−1)/(√3−1) = (√3−1)/2.

Worked examples

Q1 — LCM/HCF: LCM and HCF of 18 and 24?

• Answer: HCF = 6, LCM = 72 (see prime factorisation above).

Q2 — Trailing zeros: How many zeros at the end of 100!?

• Answer: 24.

Q3 — Unit digit: Unit digit of 3^25?

• Answer: 3 (cycle position 1, since 25 mod 4 = 1).

Q4 — AP from divisibility: Sum of all 2-digit numbers divisible by 7?

• List: 14, 21, 28, …, 98 (AP with a = 14, d = 7, last term = 98).
• n = (98 − 14)/7 + 1 = 13.
• Sum = 13/2 × (14 + 98) = 13 × 56 = 728.

Why it matters: The number system is the bedrock topic for SSC CGL, RRB NTPC, IBPS, CSAT and all school mathematics. Divisibility rules, LCM/HCF, unit digits and trailing zeros appear in nearly every shift of competitive exams. Mastering these is non-negotiable for a high score in quantitative aptitude.

Real-world example: The LCM concept appears directly in everyday scheduling — if Bus A departs every 12 minutes and Bus B every 18 minutes, they leave together every LCM(12, 18) = 36 minutes. That is a standard exam template repeated in dozens of variations.

Common misconception: Students frequently confuse HCF and LCM applications. HCF is used to split (find the largest equal group), LCM is used to combine (find when events coincide). Also, 1 is neither prime nor composite — this trips a remarkable number of students in exam conditions.

Quick-revision notes for HCF and LCM — the must-know points for SSC CGL Tier-I/II.

• HCF (Highest Common Factor) is the largest number dividing all given numbers; LCM is the smallest number divisible by all.
• For two numbers: HCF × LCM = product of the two numbers.
• Find HCF/LCM by prime factorisation or the division method.
• HCF of fractions = HCF(numerators)/LCM(denominators); LCM of fractions = LCM(numerators)/HCF(denominators).
• LCM is used for "bells ring together" and "same time" problems; HCF for "largest that divides" or "greatest measure".
• Co-prime numbers have HCF = 1, so their LCM equals their product.

Cover the answer, recall, then check. 7 cards on the must-know HCF and LCM facts for SSC CGL.

Q1. State the relation between HCF and LCM of two numbers.
A1. HCF × LCM = product of the two numbers.

Q2. Find the HCF and LCM of 12 and 18.
A2. HCF = 6, LCM = 36 (check: 6 × 36 = 216 = 12 × 18).

Q3. What is the HCF of two co-prime numbers?
A3. 1 (so their LCM equals their product).

Q4. Formula for HCF of two fractions?
A4. HCF of numerators divided by LCM of denominators.

Q5. Which of HCF/LCM is used for "bells ringing together" problems?
A5. LCM.

Q6. The LCM of 4 and 6 is?
A6. 12.

Q7. If HCF of two numbers is 8 and LCM is 48, and one number is 16, find the other.
A7. 24 — product = 8 × 48 = 384, so 384 ÷ 16 = 24.

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: The product of two numbers is 2028 and their HCF is 13. How many distinct pairs of such numbers are possible?

Solution:
Let the two numbers be 13a and 13b, where a and b are coprime (their only common factor is 1, since 13 is the HCF).
Product = 13a × 13b = 169ab = 2028
So ab = 2028 ÷ 169 = 12.
Now list coprime factor pairs of 12:
(1, 12) — HCF 1 ✓
(2, 6) — HCF 2 ✗ (not coprime)
(3, 4) — HCF 1 ✓
So the valid coprime pairs are (1, 12) and (3, 4), giving numbers (13, 156) and (39, 52).

Answer: 2 distinct pairs are possible.