“Casting out nines” is a trick for determining the remainder when a number is divided by nine. Just add the digits of the number together. For example, what’s the remainder when 3679 is divided by 9? The same as when 3 + 6 + 7 + 9 = 25 is divided by 9. We can apply the same trick again: 2 + 5 = 7, so the remainder is 8.
The “casting out” part of the name refers to the fact that you can ignore 9’s along the way because they don’t effect the final sum. In the example above, we could see that the result would be 7 by “casting out” 36 and 9.
Casting out nines works because 9 is one less than 10, i.e. one less than the base we use to represent numbers. The analogous trick would work casting out (b − 1)’s in base b. So you could cast out 7’s in base 8, or F‘s in base 16, or Z’s in base 36.
Why can you cast out (b − 1)’s in base b? First, a number written is base b is a polynomial in b. If the representation of a number x is anan-1 … a1a0 then
x = anbn + an−1bn−1 + … + a1b + a0.
Since
bm − 1 = (b − 1)(bm−1 + bm−2 + … + 1)
it follows that bm leaves a remainder of 1 when divided by b − 1. So ambm leaves the same remainder as am when divided by b − 1. If follows that
anbn + an−1bn−1 + … + a1b + a0
has the same remainder when divided by b − 1 as
an + an−1 + … + a1 + a0
does when it is divided by b − 1.
Reminds me of a similar trick — a number is divisible by three if the sum of its digits is divisible by three.
For young people of today, you should rename ‘casting out nines’ to ‘nuking nines’ IMO.
Another interesting observation in this area is the divisibility test for 7: to check if a number is divisible by 7, double the last digit and subtract it from the number formed by truncating the last digit from the original number. If the number so formed is divisible by 7, so is the original. So, 161 is divisible by 7 since (16 – 2 * 1) = 14 is divisible by 7.
The proof is also simple: we need to show that if (x – 2y) [= A] divides 7, so does (10x + y) [= B]. If A is divisible by 7, so is (10 * A + 21 * y) = B. Hence the result.
A better way of showing this is to use modular arithmetic. In particular, in base b, b = 1 (modulo b -1), hence a_nb^n+…a_1b+a_0 = a_n+…a_1+a_0 (modulo b -1). This last equality (actually, congruence) saying precisely that both sides have the same remainder on division by b -1, and hence it’s clear that repeated application gives what we want. The advantage of this method is that it gives us immediately the test for divisibility by 3 (in base 10), since 10 = 1 (modulo 3). Further, we can use this to see the test for divisibility by 11 since 10 = -1 (modulo 11), or more generally a test for divisibility by b + 1 since b = -1 (modulo b + 1). In particular, since (-1)^n alternates between +1 and -1, so does b^n modulo (b + 1), so adding and subtracting alternate terms (starting at the right-hand side) repeatedly gives us the remainder (if we end on a negative, simply add b + 1). This easy test gives a good reason we should work in base 12 rather than base 10, since we then have an easy test for 11 and 13, rather than 9 and 11 (and we lose those nasty recurring decimals when dividing by 3).