click through for a brief proof, which generally assumes a number of the form ...dcba being expressed as x = a + 10b + 100c + 1000d + ... (which is backwards, with the ones digit first, but that's so an arbitrarily long number can be handwaved with dotdotdot). the secret ingredient is that we can add or subtract whatever multiples of N we want, without affecting divisibility by N.
these generally work by reducing the number to a smaller number that is congruent mod N; thus if the smaller number is divisible by N, the original is too. but that means these tests are more powerful than they appear — you can also use every single one of them to determine the remainder when dividing a number by N. for example, 196 is not divisible by 3; the rule has you add the digits, which gives 16. but 16 is 1 more than a multiple of 3 (3×5 + 1), and thus so is 196 (3×65 + 1).
caveats:
-
if you end up with a negative number then you'll have to add some multiples of N to get an appropriate remainder
-
some of the later rules (7, 13, and others following a similar pattern) produce a multiple of the remainder. for example, testing if 15 is divisible by 7 produces -9. to get the remainder, we need to divide by -2. -9 is odd, but we can add or subtract multiples of 7 all we like, so add 7 to get -2, then divide by -2 to get 1, which is the actual remainder. (you can equivalently divide by 5, because 5 and -2 are equivalent mod 7, but a multiple of -2 is easier to find. modular arithmetic is cool.)
the interesting ones are primes and powers of primes; divisibility by anything else can be broken down into testing divisibility of its prime powers, e.g. a number is divisible by 24 iff it is divisible by both 3 and 8.
remember, to fully factor a number, you need only check primes up to its square root.
bonus fact: perfect squares never end in 2, 3, 7, or 8. fourth powers only end in 0, 1, 5, or 6. fifth powers have the same final digit as the original number.
1 — always true.
2 — check if last digit is divisible by 2.
3 — check if sum of digits is divisible by 3. recurse if necessary.
4 — check if last two digits are divisible by 4. subtract multiples of 20 if that helps.
5 — check if last digit is divisible by 5.
6 — check if divisible by both 2 and 3.
7 — double the last digit and subtract from the rest of the number. check if result is divisible by 7. recurse if necessary. (divide by -2 or 5 to get remainder.)
7 — multiply the last digit by 5 (add a 0 and halve it) and add to the rest of the number. check if result is divisible by 7. recurse if necessary. (divide by 5 or -2 to get remainder.)
8 — check if last three digits are divisible by 8. subtract multiples of 40 or 200 if that helps.
9 — check if sum of digits is divisible by 9. recurse if necessary.
10 — check if last digit is divisible by 10.
11 — add up alternating digits, i.e. digits in odd positions and digits in even positions. check if the difference is divisible by 11. (to get the correct remainder, do (ones group) - (tens group). otherwise you'll get the negative of the remainder. for divisibility, it doesn't matter.)
12 — check if divisible by both 3 and 4.
13 — multiply the last digit by 4 and add to the rest of the number. check if result is divisible by 13. recurse if necessary. it may help to know that 52 and 104 are multiples of 13. (divide by 4 or -9 to get remainder.)
14 — check if divisible by both 2 and 7.
15 — check if divisible by both 3 and 5.
16 — check if last four digits are divisible by 16. subtract multiples of 80, 400, or 2000 if that helps.
16 — add the last two digits and four times the next two digits. check if result is divisible by 16.
17 — multiply the last digit by 5 and subtract from the rest of the number. check if result is divisible by 17. recurse if necessary. it may help to know that 51 and 102 are multiples of 17. (divide by 5 or -12 to get remainder.)
18 — check if divisible by both 2 and 9.
19 — double the last digit and add to the rest of the number. check if result is divisible by 19. recurse if necessary. it may help to know that 95 is a multiple of 19. (divide by 2 to get remainder.)
20 — check if divisible by both 4 and 5.
21 — check if divisible by both 3 and 7.
22 — check if divisible by both 2 and 11.
23 — multiply the last digit by 7 and add to the rest of the number. check if result is divisible by 23. recurse if necessary. it may help to know that 69 and 299 are multiples of 23. (divide by 7 to get remainder.)
24 — check if divisible by both 3 and 8.
25 — check if last two digits are divisible by 25.
26 — check if divisible by both 2 and 13.
at this point i was musing over a better rule for 27 when i discovered that wikipedia just has a fucking table all the way up to 30 including a bunch of alternative rules i've never even heard of so i guess this was a huge waste of time!
