Divisibility Rules

Why does the rule for 3 use the sum of digits, while the rule for 4 uses only the last two digits?

These are not arbitrary mnemonics. They are consequences of a single idea: the value of each digit depends on its position, and different moduli react differently to powers of 10.

---

The underlying idea

Every positive integer $n$ can be written in terms of its digits:

$n = d_k \cdot 10^k + d_{k-1} \cdot 10^{k-1} + \cdots + d_1 \cdot 10 + d_0$

To check if $m \mid n$, reduce modulo $m$:

$n \equiv d_k \cdot (10^k \bmod m) + \cdots + d_1 \cdot (10 \bmod m) + d_0 \pmod{m}$

The rule for $m$ depends entirely on the pattern of $10^k \bmod m$.

---

Rule for 2 and 5

$10 \equiv 0 \pmod{2}$ and $10 \equiv 0 \pmod{5}$.

So $10^k \equiv 0$ for all $k \geq 1$, meaning all digits except the last vanish:

$n \equiv d_0 \pmod{2} \quad \text{and} \quad n \equiv d_0 \pmod{5}$

Rule. $2 \mid n \iff$ last digit is $0, 2, 4, 6,$ or $8$.

Rule. $5 \mid n \iff$ last digit is $0$ or $5$.

---

Rule for 4 and 25

$100 \equiv 0 \pmod{4}$ and $100 \equiv 0 \pmod{25}$.

So $10^k \equiv 0$ for all $k \geq 2$:

$n \equiv d_1 \cdot 10 + d_0 \pmod{4} \quad \text{and} \quad n \equiv d_1 \cdot 10 + d_0 \pmod{25}$

Rule. $4 \mid n \iff 4$ divides the last two digits.

Rule. $25 \mid n \iff 25$ divides the last two digits.

Example. $4 \mid 1836$? Last two digits: $36 = 4 \times 9$. Yes.

Rule for 8 and 125

$1000 \equiv 0 \pmod{8}$ and $1000 \equiv 0 \pmod{125}$.

Rule. $8 \mid n \iff 8$ divides the last three digits.

Rule. $125 \mid n \iff 125$ divides the last three digits.

---

Rule for 3 and 9

$10 \equiv 1 \pmod{3}$ and $10 \equiv 1 \pmod{9}$.

So $10^k \equiv 1^k = 1$ for all $k$:

$n \equiv d_k + d_{k-1} + \cdots + d_1 + d_0 \pmod{3}$

Rule. $3 \mid n \iff 3$ divides the sum of digits of $n$.

Rule. $9 \mid n \iff 9$ divides the sum of digits of $n$.

Example. Is $3 \mid 47382$? Sum of digits: $4+7+3+8+2 = 24$, and $3 \mid 24$. Yes.

Why casting out nines works. Since any digit $d$ contributes $d \pmod 9$, and $9 \equiv 0 \pmod 9$, you can drop any 9s or digit groups summing to 9. The remainder is the same.

---

Rule for 11

$10 \equiv -1 \pmod{11}$, so $10^k \equiv (-1)^k \pmod{11}$:

$n \equiv d_0 - d_1 + d_2 - d_3 + \cdots \pmod{11}$

Rule. $11 \mid n \iff 11$ divides the alternating sum of digits (starting from the right with $+$).

Example. Is $11 \mid 85437$?

Alternating sum: $7 - 3 + 4 - 5 + 8 = 11$. Yes, $11 \mid 85437$.

Example. Is $11 \mid 9$ (i.e., 9)? Alternating sum is 9. $11 \nmid 9$. No.

---

Rule for 7

$10 \equiv 3 \pmod{7}$. The powers of 3 mod 7 cycle with period 6:

$3^0 \equiv 1,\quad 3^1 \equiv 3,\quad 3^2 \equiv 2,\quad 3^3 \equiv 6,\quad 3^4 \equiv 4,\quad 3^5 \equiv 5,\quad 3^6 \equiv 1\ \ldots$

So $10^k \pmod 7$ cycles: $1, 3, 2, 6, 4, 5, 1, 3, 2, \ldots$

There is no clean digit-sum rule for 7. The standard approach:

Practical method. Double the last digit, subtract from the rest. Repeat until small.

$7 \mid n \iff 7 \mid (\text{number without last digit}) - 2 \times (\text{last digit})$

Why. If $n = 10q + d_0$, then $n - 2d_0 = 10q + d_0 - 2d_0 = 10q - d_0$. And $7 \mid 10q - d_0 \iff 7 \mid 10(10q-d_0) = 100q - 10d_0 \equiv 2q - 3d_0$... the cleaner proof: $n \equiv 0 \pmod 7 \iff 10q + d_0 \equiv 0 \iff 3q + d_0 \equiv 0 \iff q \equiv -d_0 \cdot 3^{-1} \equiv -d_0 \cdot 5 \equiv 2d_0 \pmod 7$... the doubling-and-subtracting shortcut collapses this.

Example. Is $7 \mid 874$?

$87 - 2(4) = 87 - 8 = 79$.

$7 - 2(9) = 7 - 18 = -11$.

$7 \nmid -11$, so $7 \nmid 874$.

---

Rule for 13

$10 \equiv 10 \pmod{13}$, and powers of 10 mod 13 cycle with period 6:

$1, 10, 9, 12, 3, 4, 1, 10, \ldots$

Practical method. Multiply the last digit by 4, add to the rest. Repeat.

$13 \mid n \iff 13 \mid (\text{number without last digit}) + 4 \times (\text{last digit})$

---

Summary table

Divisor	Key congruence	Rule
2	$10 \equiv 0$	Last digit even
3	$10 \equiv 1$	Sum of digits divisible by 3
4	$100 \equiv 0$	Last two digits divisible by 4
5	$10 \equiv 0$	Last digit is 0 or 5
7	$10 \equiv 3$, period 6	Double last digit, subtract
8	$1000 \equiv 0$	Last three digits divisible by 8
9	$10 \equiv 1$	Sum of digits divisible by 9
11	$10 \equiv -1$	Alternating digit sum
13	$10 \equiv 10$, period 6	Multiply last digit by 4, add
25	$100 \equiv 0$	Last two digits divisible by 25

---

Worked problems

Problem 1. Find the smallest 5-digit number divisible by 9 with digit sum 18.

Digit sum 18 guarantees divisibility by 9. Smallest 5-digit: $10008$ — digit sum $1+0+0+0+8 = 9$. Not 18.

Try $10008$'s neighbors... actually minimize: put the largest digits at the end. $10008$ has sum 9. We want sum 18. Minimum 5-digit with sum 18: $10089$ (sum: $1+0+0+8+9=18$). Check: $10089 / 9 = 1121$. ✓

Problem 2. A 6-digit number $\overline{1a2b3c}$ is divisible by 11. Find the relationship between $a$, $b$, and $c$.

Alternating sum (right to left): $c - 3 + b - 2 + a - 1 = a + b + c - 6$.

For divisibility by 11: $11 \mid a + b + c - 6$, so $a + b + c \equiv 6 \pmod{11}$.

Since $a, b, c \in \{0,\ldots,9\}$, the sum $a+b+c \in \{0,\ldots,27\}$, giving $a+b+c \in \{6, 17\}$.

Problem 3. Prove that $10^n - 1$ is always divisible by 9.

$10 \equiv 1 \pmod 9$, so $10^n \equiv 1 \pmod 9$, giving $10^n - 1 \equiv 0 \pmod 9$. $\blacksquare$

This is why the digit-sum rule works: $n - (\text{digit sum}) =$ a multiple of 9 always.

Problem 4. Show that no perfect square ends in 2, 3, 7, or 8.

Squares mod 10: $0^2=0, 1^2=1, 2^2=4, 3^2=9, 4^2=6, 5^2=5, 6^2=6, 7^2=9, 8^2=4, 9^2=1$.

Last digits of squares: $\{0,1,4,5,6,9\}$ only. The digits 2, 3, 7, 8 never appear. $\blacksquare$