Exercises — Divisibility rules — 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 (with proofs where possible)

Rule for 5: last digit is $0$ or $5$. Rule for 10: last digit is $0$.

• Last digit of $4830$ is $d_0===0==$.
• $0$ is one of $\{0,5\}$ → divisible by $5$. ✓
• $0$ is exactly $0$ → divisible by $10$. ✓ Why the last digit alone decides it: every earlier digit is multiplied by $10,100,1000,\dots$, and each of those is already a multiple of both $5$ and $10$. So $n\equiv d_0(\mathrm{mod}5)$ and $n\equiv d_0(\mathrm{mod}10)$ — only the units digit $d_0$ survives. Answer: divisible by both $5$ and $10$.

Rule for 4: the last two digits, as a number, must be divisible by $4$.

• Last two digits: $16$.
• $16=4\times 4$ → divisible. Why only two digits: everything from the hundreds place up is a multiple of $100=4\times 25\equiv 0(\mathrm{mod}4)$. So $n\equiv (\text{last two digits})(\mathrm{mod}4)$. Answer: yes, $3516$ is divisible by $4$ (indeed $3516=4\times 879$).

Digit sum $=8+1+2+7===18==$.

• $18=9\times 2$ → divisible by $9$, hence $n$ is divisible by $9$.
• $18=3\times 6$ → divisible by $3$, hence $n$ is divisible by $3$. Why the plain sum works here: $10\equiv 1(\mathrm{mod}9)$ and $10\equiv 1(\mathrm{mod}3)$, so every $10^i\equiv 1$, and $n\equiv \sum d_i$ (the sum of all digits). The weights collapse to $1$. Answer: divisible by both $3$ and $9$.

The rule: write $n=10a+b$ ($b$ = last digit $d_0$, $a$ = the rest), then test $a-2b$. Repeat until small.

• Round 1: $1057\to a=105,b=7\Rightarrow 105-2(7)=105-14===91==$.
• Round 2: $91\to a=9,b=1\Rightarrow 9-2(1)=7$.
• $7$ is divisible by $7$. ✓ Why $-2b$ and not something else: $10\equiv 3(\mathrm{mod}7)$, so $n\equiv 3a+b$. Multiply by the inverse of $3$ (which is $5$, since $3\times 5=15\equiv 1$): $5(3a+b)\equiv a+5b\equiv a-2b$ (because $5\equiv -2(\mathrm{mod}7)$). The whole point is to strip $a$ down to coefficient $1$. Answer: yes, $1057=7\times 151$.

Rule for 11: alternating digit sum, from the right, must be a multiple of $11$ (including $0$).

• Digits right-to-left: $d_0=8,d_1=2,d_2=7,d_3=2$.
• Alternating sum $d_0-d_1+d_2-d_3=8-2+7-2===11==$.
• $11$ is a multiple of $11$. ✓ Why alternating: here $10\equiv -1(\mathrm{mod}11)$, so the weights become $+1,-1,+1,-1,\dots$ — the signs flip each step. Answer: yes, $2728=11\times 248$.

Rule for 6: divisible by $6$ ⟺ divisible by both $2$ and $3$.

• By $2$: last digit $6$ is even. ✓
• By $3$: digit sum $1+2+3+6=12=3\times 4$. ✓ Both pass, so $n$ is divisible by $6$. Why both (not either): $6=2\times 3$ with $\gcd (2,3)=1$. By the Chinese Remainder Theorem, the pair of conditions "$\equiv 0(\mathrm{mod}2)$ and $\equiv 0(\mathrm{mod}3)$" is equivalent to "$\equiv 0(\mathrm{mod}6)$" precisely because $2$ and $3$ share no factor. See also GCD and LCM. Answer: yes, $1236=6\times 206$.

Digit sum $=5+3+d+4=12+d$. We need $12+d\equiv 0(\mathrm{mod}3)$. Since $12\equiv 0(\mathrm{mod}3)$, we need $d\equiv 0(\mathrm{mod}3)$. Digits $0$–$9$ with $d\equiv 0$: $d\in ==\{0,3,6,9\}==$. Why this is clean: the fixed digits already contribute a multiple of $3$, so the whole condition lands on $d$ alone. Answer: $d=0,3,6,9$.

Right-to-left digits: $d_0=2,d_1=d,d_2=6$. Alternating sum $=2-d+6=8-d$. Need $8-d\equiv 0(\mathrm{mod}11)$, i.e. $8-d\in \{\dots ,-11,0,11,\dots \}$. With $d\in \{0,\dots ,9\}$, $8-d$ ranges from $8$ (at $d=0$) down to $-1$ (at $d=9$). The only multiple of $11$ in that range is $0$. $8-d=0\Rightarrow d===8==$. Check: $682=11\times 62$. ✓ Answer: $d=8$.

The $8$-rule looks at the last three digits — but that is the whole number here, so we test $700+10d+6=706+10d$ for divisibility by $8$. $706+10d\equiv 0(\mathrm{mod}8)$. Reduce: $706=8\times 88+2$, so $706\equiv 2$; and $10=8+2$, so $10\equiv 2(\mathrm{mod}8)$. Condition: $2+2d\equiv 0(\mathrm{mod}8)\Rightarrow 2d\equiv -2\equiv 6(\mathrm{mod}8)\Rightarrow d\equiv 3(\mathrm{mod}4)$. Digits with $d\equiv 3(\mathrm{mod}4)$: $d\in ==\{3,7\}==$. Check: $736=8\times 92$ ✓ and $776=8\times 97$ ✓. Answer: $d=3,7$.

"Divisible by $8$ and $9$" with $\gcd (8,9)=1$ means divisible by $\text{lcm}(8,9)=72$ (see GCD and LCM and Chinese Remainder Theorem). Rule for 9: digit sum $1+2+a+b=3+a+b\equiv 0(\mathrm{mod}9)$. Rule for 8: last three digits $\overline{2ab}=200+10a+b\equiv 0(\mathrm{mod}8)$. Now reduce each piece mod $8$, showing the steps:

• $200=8\times 25+0$, so $200\equiv 0(\mathrm{mod}8)$ (it is an exact multiple of $8$).
• $10=8\times 1+2$, so $10\equiv 2(\mathrm{mod}8)$; hence $10a\equiv 2a$.
• $b\equiv b$ (already a single digit).

Adding these: $200+10a+b\equiv 0+2a+b=2a+b(\mathrm{mod}8)$. So the $8$-condition is $2a+b\equiv 0(\mathrm{mod}8)$. We want the smallest number, so make $a$ as small as possible, then $b$.

• Try $a=0$: need $b\equiv 0(\mathrm{mod}8)\Rightarrow b\in \{0,8\}$. And $3+0+b\equiv 0(\mathrm{mod}9)\Rightarrow b\equiv 6(\mathrm{mod}9)\Rightarrow b=6$. No overlap with $\{0,8\}$. Fail.
• Try $a=1$: $8$-rule $2+b\equiv 0(\mathrm{mod}8)\Rightarrow b=6$ (or $14$, too big). $9$-rule $3+1+b\equiv 0\Rightarrow 4+b\equiv 0(\mathrm{mod}9)\Rightarrow b=5$. No overlap. Fail.
• Try $a=2$: $8$-rule $4+b\equiv 0(\mathrm{mod}8)\Rightarrow b=4$. $9$-rule $3+2+b\equiv 0\Rightarrow 5+b\equiv 0\Rightarrow b=4$. Overlap at $b=4$! ✓ Number: $\overline{1224}===1224==$. Check: $1224=72\times 17$. ✓ Answer: $1224$.

Mod 9 (the Casting Out Nines trick): the remainder equals the digit sum reduced mod $9$. $8+6+7+5+3+0+9=38$, and $3+8=11$, and $1+1=2$. So $n\equiv ==2==(\mathrm{mod}9)$. Mod 11: alternating sum from the right. Digits right-to-left: $9,0,3,5,7,6,8$. $9-0+3-5+7-6+8=16$. Reduce mod $11$: $16-11=5$. So $n\equiv ==5==(\mathrm{mod}11)$. Why we may reduce the digit sum again: $38\equiv 3+8(\mathrm{mod}9)$ because $10\equiv 1$ still holds — the trick is self-similar, you can iterate. Answer: remainder $2$ mod $9$; remainder $5$ mod $11$.

Work in Modular Arithmetic mod $7$. Let $n=10a+b$. Step 1 — reduce the $10$. Since $10=7+3$, we have $10\equiv 3(\mathrm{mod}7)$, so $n=10a+b\equiv 3a+b(\mathrm{mod}7).$ Step 2 — multiply by an invertible number. In mod $7$, the number $5$ is invertible because $\gcd (5,7)=1$ (in fact $3\times 5=15\equiv 1$, so $5$ is the inverse of $3$). Multiplying a congruence by a number coprime to the modulus is reversible — it neither creates nor destroys solutions. Multiply $n\equiv 3a+b$ by $5$: $5n\equiv 15a+5b\equiv a+5b(\mathrm{mod}7)(\text{since }15\equiv 1).$ Step 3 — rewrite $+5b$ as $-2b$. Because $5\equiv -2(\mathrm{mod}7)$: $a+5b\equiv a-2b$. So $5n\equiv a-2b(\mathrm{mod}7).$ Step 4 — the biconditional. Since $5$ is invertible mod $7$, $5n\equiv 0⟺n\equiv 0$. Combined with Step 3: $n\equiv 0(\mathrm{mod}7)⟺a-2b\equiv 0(\mathrm{mod}7).■$ Why both directions: the only non-obvious link is $5n\equiv 0\Rightarrow n\equiv 0$. That holds precisely because we can multiply back by $5^{-1}=3$: $n\equiv 3\cdot 5n\equiv 3\cdot 0=0$. If $5$ were not coprime to $7$, this back-multiplication would fail and the rule would be one-directional only.

We want $k$ with $10k\equiv \pm 1(\mathrm{mod}13)$. Because $\gcd (10,13)=1$, the inverse of $10$ exists (this coprimality is exactly the condition Fermat's Little Theorem guarantees an inverse under). Test small $k$: $10\times 4=40=39+1\equiv 1(\mathrm{mod}13)$. So $k===4==$ gives $10k\equiv +1$. Now take $n=10a+b$. Multiply by $4$: $4n\equiv 40a+4b\equiv a+4b(\mathrm{mod}13)$. Since $4$ is invertible mod $13$, $n\equiv 0⟺a+4b\equiv 0$. Resulting rule for 13: chop off the last digit $b$, add $4b$ to the remaining number $a$, and repeat; the result is divisible by $13$ exactly when the original is. Check: $n=247=13\times 19$. Chop: $a=24,b=7\Rightarrow 24+4(7)=24+28=52=13\times 4$. ✓ Answer: $k=4$; rule is $a+4b$.