Divisibility tests

Base ten representation: n = d_r d_r-1 ... d₀

Then n is divisible by the listed number, if

2. d₀ divisible by 2
3. sum of the digits divisible by 3
4. d₁d₀ divisible by 4
5. d₀ divisible by 5
6. divisible by 2 and by 3
7. d_r ...d₁- 2×d₀ divisible by 7
   Example 4319 431 - 2×9 = 413 41 - 2×3 = 35 = 5×7
   If d_r ...d₁- 2×d₀ = m×7, then d_r ...d₁d₀ = (10×m+3×d₀)×7
   Example 413 = (10×5+3×3)×7 = 59×7 and then 4319 = (10×59+3×9)×7 = 617×7
8. d₂d₁d₀ divisible by 8
9. sum of the digits divisible by 9
10. d₀ = 0
11. sum of the even digits, minus sum of the odd digits, divisible by 11
12. divisible by 3 and by 4
13. d_r ...d₁- 9×d₀ divisible by 13
    Example 4316 431 - 9×6 = 377 37 - 9×7 = -26 = -2×13
    If d_r ...d₁- 9×d₀ = m×13, then d_r ...d₁d₀ = (10×m+7×d₀)×13
    Example 377 = (10×-2+7×7)×13 = 29×13 and then 4316 = (10×29+7×6)×13 = 332×13
25. d₁d₀ divisible by 25

Fast algorithm for prime factors:

7. d₀ + 3×d₁ + 2×d₂ - d₃ - 3×d₄ - 2×d₅ ... divisible by 7, where the coefficient c_n of digit d_n is 10ⁿ mod 7 (taking the closest result to zero, rather than a positive result, to help the sum cancel)
   Example 4319 9 + 3×1 +2×3 - 4 = 14 = 2×7
13. d₀ - 3×d₁ - 4×d₂ - d₃ + 3×d₄ + 4×d₅ ... divisible by 13, where the coefficient c_n of digit d_n is 10ⁿ mod 13
    Example 4316 6 - 3×1 - 4×3 - 4 = -13

• The technique can be used for divisibility by any prime p, where the coefficient c_n of digit d_n is 10ⁿ mod p.
• The earlier rules for 2, 3, 5 and 11 are special cases of this rule, where the coefficients have a simple pattern.