If you're curious why these work:
The basic principle is that if A is divisible by N, and B is also divisible by N, then A+B and A-B are divisible by N. So we want to split the number you're testing into a number we know is divisible by N, plus a small number that you can just look at.
2 and 5: the number is in base 10, which is 2*5. You can split the number into a number ending in zero, plus the last digit (9876 = 9870 + 6). The number ending in zero is always a multiple of 10, so it's a multiple of 2. So the whole number is a multiple of 2 if, and only if, the last digit is also a multiple of 2. (And the same for 5.)
4, 8, 16...: do the same, but split off the last n digits (9800 + 76, 9000 + 876). The number ending in n zeroes is a multiple of 10^n, so it's a multiple of 2^n. Then check the last n digits.
9: Much more interesting!
If you sum the digits of a two-digit number, what happens? You're subtracting some number of tens (whatever is in the tens place), and adding the same number of ones, which is the same as subtracting nines. If there's a third digit then you're subtracting hundreds and adding ones, which is subtracting a multiple of 99. And so on: each digit corresponds to a power of 10, so when you add it to the digit sum, you're subtracting 999... which is a multiple of 9. So the starting number is the sum of its digits, plus some multiple of 9. (This works because 9 is 10 - 1.)
And the sum of the digits has a sum of its digits, and so on until you get to a single digit. So the original number is that digit plus a big stack of nines, which is divisible by 9 only if the single digit is 9.
3: Same as 9, except at the end the single digit has to be divisible by 3, so it can be 3, 6, or 9.
All of these methods work in any other base, too--in base 16, the 2 trick works for 4 and 8 as well, and the 3/9 trick works for 3 and 5 because 3*5 = 16 - 1.
gamechangershow
areudirty
tangentwithtanner
stormborns
prguitarman
snowghoul
theartofmadeline
