Divisibility Rules

At a glance 12 formulas

1. 1Last-digit testsFor 2, 4 and 8, test the last 1, 2 and 3 digits; for 5, 25 and 125, the same. For 10, the last digit must be 0.
2. 2Digit-sum testA number is divisible by 3 or 9 exactly when its digit sum is. Reordering the digits never changes this.
3. 3Divisibility by 11$(\text{odd-place sum}) - (\text{even-place sum}) = 0, \pm 11, \dots$$\text{places counted from the units digit}$
4. 4Divisibility by 7Double the last digit and subtract it from the rest; repeat until the number is small. $2401 \to 240 - 2 = 238 \to 23 - 16 = 7$.
5. 5The 1001 rule$1001 = 7 \times 11 \times 13$, so $\overline{abcabc} = \overline{abc} \times 1001$. For $\overline{abcdef}$: $\overline{abc} - \overline{def}$ decides 7, 11 and 13.
6. 6Split into co-prime partsTest each co-prime factor: $72 = 8 \times 9$, $88 = 8 \times 11$, $12 = 3 \times 4$. Never 4 and 6 for 24: they share a 2.
7. 7Divisible by both$a \mid N \text{ and } b \mid N \Rightarrow \text{LCM}(a, b) \mid N$
8. 8Counting multiples$\text{multiples of } k \text{ in } 1 \text{ to } N = \left\lfloor \dfrac{N}{k} \right\rfloor$$\text{from } M \text{ to } N: \left\lfloor \tfrac{N}{k} \right\rfloor - \left\lfloor \tfrac{M - 1}{k} \right\rfloor$
9. 9Inclusion-exclusion$a \text{ or } b: \left\lfloor \tfrac{N}{a} \right\rfloor + \left\lfloor \tfrac{N}{b} \right\rfloor - \left\lfloor \tfrac{N}{\text{LCM}(a, b)} \right\rfloor$
10. 10Consecutive integersA product of $k$ consecutive integers is divisible by $k!$: any 3 in a row by 6, any 4 in a row by 24.
11. 11Differences of powers$(a - b) \mid a^n - b^n$$n \text{ even: } (a^2 - b^2) \mid a^n - b^n;\ \ n \text{ odd: } (a + b) \mid a^n + b^n$
12. 12Primes above 3$p > 3 \text{ prime} \Rightarrow 24 \mid p^2 - 1$