# Divisibility tests

Base ten representation: n = d r d r -1 ... d 0

Then n is divisible by the listed number, if

1. d 0 divisible by 2
2. sum of the digits divisible by 3
3. d 1 d 0 divisible by 4
4. d 0 divisible by 5
5. divisible by 2 and by 3
6. d r ... d 1 - 2× d 0 divisible by 7
Example 4319 431 - 2×9 = 413 41 - 2×3 = 35 = 5×7
If d r ... d 1 - 2× d 0 = m ×7, then d r ... d 1 d 0 = (10× m +3× d 0 )×7
Example 413 = (10×5+3×3)×7 = 59×7 and then 4319 = (10×59+3×9)×7 = 617×7

7. d 2 d 1 d 0 divisible by 8
8. sum of the digits divisible by 9
9. d 0 = 0
10. sum of the even digits, minus sum of the odd digits, divisible by 11
11. divisible by 3 and by 4
12. d r ... d 1 - 9× d 0 divisible by 13
Example 4316 431 - 9×6 = 377 37 - 9×7 = -26 = -2×13
If d r ... d 1 - 9× d 0 = m ×13, then d r ... d 1 d 0 = (10× m +7× d 0 )×13
Example 377 = (10×-2+7×7)×13 = 29×13 and then 4316 = (10×29+7×6)×13 = 332×13

13. d 1 d 0 divisible by 25

Fast algorithm for prime factors:

1. d 0 + 3× d 1 + 2× d 2 - d 3 - 3× d 4 - 2× d 5 ... divisible by 7, where the coefficient c n of digit d n is 10 n 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
2. d 0 - 3× d 1 - 4× d 2 - d 3 + 3× d 4 + 4× d 5 ... divisible by 13, where the coefficient c n of digit d n is 10 n 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 n mod p .
• The earlier rules for 2, 3, 5 and 11 are special cases of this rule, where the coefficients have a simple pattern.