Number System: Divisibility, HCF–LCM and Remainders

Prerequisites: Number System — overview · Percentages for CSAT

The Hook: Three Bells and a Timetable

The Core Concept

1. Kinds of numbers

Type	Definition	Note
Natural	1, 2, 3, …
Whole	0, 1, 2, …
Integers	…, −2, −1, 0, 1, 2, …
Rational	$p/q$ with integers $p, q$ and $q \neq 0$	Terminating or repeating decimals
Irrational	Not expressible as $p/q$	$\sqrt{2}$, $\pi$
Prime	Exactly two factors	2 is the only even prime; 1 is neither prime nor composite; there are 25 primes below 100
Co-prime	HCF = 1	8 and 15 are co-prime though neither is prime

2. Divisibility rules

Divisor	Rule	Example
2	Last digit even	3,514
3	Sum of digits divisible by 3	4,281 (sum 15)
4	Last two digits divisible by 4	7,316 (16)
5	Last digit 0 or 5	8,435
6	Divisible by 2 and 3	7,314
7	Double the last digit, subtract from the rest; repeat	875 → $87 - 10 = 77$ ✓
8	Last three digits divisible by 8	4,73,592 ($592 = 8 \times 74$) ✓
9	Sum of digits divisible by 9	34,452 (sum 18)
11	(Sum of digits in odd places) − (sum in even places) is 0 or a multiple of 11	9,18,082
12	Divisible by 3 and 4	5,436

Worked example (11). Is 918,082 divisible by 11? From the right, odd places: $2 + 0 + 1 = 3$; even places: $8 + 8 + 9 = 25$. Difference $= -22$, a multiple of 11 → yes.

3. Counting factors

If $N = p^a \times q^b \times r^c$ (prime factorisation), the number of factors is

$$\boxed{(a+1)(b+1)(c+1)}$$

Worked example. $360 = 2^3 \times 3^2 \times 5^1$, so it has $(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24$ factors.

4. HCF and LCM

• HCF (highest common factor): product of the lowest powers of common primes.
• LCM (least common multiple): product of the highest powers of all primes present.
• For two numbers: $\text{HCF} \times \text{LCM} = \text{product of the numbers}$.

Worked example. $36 = 2^2 \times 3^2$ and $84 = 2^2 \times 3 \times 7$. HCF $= 2^2 \times 3 = 12$; LCM $= 2^2 \times 3^2 \times 7 = 252$. Check: $12 \times 252 = 3{,}024 = 36 \times 84$ ✓.

Which one to use — the four classic questions:

Question asks for…	Use	Worked example
When events recur together	LCM	Bells every 12, 15, 20 min → together every 60 min
Smallest number leaving remainder $r$ when divided by $a, b, c$	$\text{LCM}(a, b, c) + r$	Divided by 6, 9, 12 leaves 4 → $36 + 4 = 40$
Largest number dividing $x$ and $y$ leaving remainder $r$ in each	$\text{HCF}(x - r,\ y - r)$	245 and 1029, remainder 5 → $\text{HCF}(240, 1024) = 16$
Largest equal size to cut lengths / pack items	HCF	48 m and 72 m ropes → pieces of 24 m

Check the third example: $245 = 16 \times 15 + 5$ and $1029 = 16 \times 64 + 5$ ✓.

5. Remainders

The remainder of a sum or product equals the remainder of the sum or product of the individual remainders.

Worked example. Remainder when $17 \times 23 \times 29$ is divided by 5: remainders are 2, 3, 4; $2 \times 3 \times 4 = 24$; $24 \div 5$ leaves 4. (Check: $17 \times 23 \times 29 = 11{,}339$, which leaves 4.)

Divisor-of-divisor trick. If a number leaves remainder $r$ when divided by $D$, and $d$ divides $D$, then the remainder on dividing by $d$ is simply the remainder of $r \div d$.

Powers: remainders of powers repeat in cycles. Powers of 2 divided by 5 leave $2, 4, 3, 1, 2, 4, 3, 1, \ldots$ (cycle of 4).

6. Unit digits of powers

Last digit	Cycle	Length
0, 1, 5, 6	Always itself	1
4	4, 6	2
9	9, 1	2
2	2, 4, 8, 6	4
3	3, 9, 7, 1	4
7	7, 9, 3, 1	4
8	8, 4, 2, 6	4

Method: divide the exponent by 4 and use the remainder (remainder 0 → use the 4th term).

Worked example. Unit digit of $7^{95}$: $95 = 4 \times 23 + 3$ → third term of (7, 9, 3, 1) → 3.

7. Trailing zeros in a factorial

Each trailing zero needs a factor 10 = 2 × 5; fives are scarcer, so count them:

$$\text{Zeros in } n! = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots$$

Worked example. $100!$: $20 + 4 = 24$ zeros.

8. Useful sums

Sum	Formula	Example
$1 + 2 + \cdots + n$	$\dfrac{n(n+1)}{2}$	$1 + \cdots + 50 = 1{,}275$
First $n$ odd numbers	$n^2$	$1 + 3 + 5 + 7 + 9 = 25$
$1^2 + 2^2 + \cdots + n^2$	$\dfrac{n(n+1)(2n+1)}{6}$	up to $10^2$: 385
Arithmetic progression	$\dfrac{\text{number of terms}}{2} \times (\text{first} + \text{last})$	Multiples of 7 from 14 to 98: $\dfrac{13}{2} \times 112 = 728$

Counting multiples: multiples of $k$ from 1 to $N$ $= \lfloor N/k \rfloor$. Between $a$ and $b$ inclusive: $\lfloor b/k \rfloor - \lfloor (a-1)/k \rfloor$.

9. Orders of magnitude — Indian and international systems

Indian	Value	International
1 lakh	$10^5$	100 thousand
10 lakh	$10^6$	1 million
1 crore	$10^7$	10 million
100 crore	$10^9$	1 billion
1 lakh crore	$10^{12}$	1 trillion

Data-interpretation and economy questions often mix the two systems — convert before comparing.

Memory Anchors

• “Low for HCF, high for LCM” — lowest common powers versus highest powers.
• “Recur → LCM; cut → HCF.”
• Cyclicity “2-3-7-8 cycle in four; 4 and 9 in two; 0-1-5-6 stay.”
• Trailing zeros = count the fives.
• “One crore is ten million; a hundred crore is a billion.”

For Prelims

Speed Strategy

• Check options before calculating. For “which number is divisible by…” questions, apply the divisibility rule to each option rather than dividing.
• Use unit digits to eliminate. If options differ in their last digit, the unit-digit cycle alone finds the answer.
• Decide HCF or LCM from the wording (“together again”, “smallest” → LCM; “largest”, “equal pieces” → HCF) before writing any numbers.
• Never expand big powers. Use cycles of unit digits or remainders.
• What to skip: questions on sums of long, irregular series are rare and slow — leave them for the end.

Common Traps

Practice

Prelims (CSAT)

Quick Revision

Situation	Method
Divisible by 8 / 11	Last three digits / alternating sum
Number of factors	$(a+1)(b+1)(c+1)\cdots$
Together again	LCM
Smallest number with remainder $r$	LCM $+ r$
Largest divisor leaving remainder $r$	HCF of (numbers $- r$)
Two numbers	HCF × LCM = product
Unit digit of a power	Exponent mod 4 (remainder 0 → 4th term)
Trailing zeros of $n!$	$\lfloor n/5 \rfloor + \lfloor n/25 \rfloor + \cdots$
1 crore / 1 billion	$10^7$ / $10^9$ (= 100 crore)

Key Takeaways

Related Topics

• Number System — quick revision
• Number System — practice questions
• Percentages for CSAT
• Logical Reasoning: Puzzles and Arrangements — calendars and clocks use remainders
• Data Interpretation