Casting Out Nines (and Elevens and Sevens . . .)

Most of you probably know (or knew at one time) the trick from pre-calculator days for deciding quickly whether a number is divisible by 9. You add up all the digits, and if the result is divisible by 9, then so was the original number. If you like, you can repeat the process, just summing the digits until only a one-digit number remains; if you started with a multiple of 9, the number you get will be a 9; otherwise, it won’t. I’ve heard that this process is well-known to numerologists under the name “casting out nines”.

What you may not know is that the same rule tests for divisibility by 3, and that a very similar rule tests for divisibility by 11.

Direct Digit Casting for 3 and 9: Start with a number. Add up the digits to get a new number. (Repeat as desired.) The original number is divisible by 3 (or 9) if and only if the new number is divisible by 3 (or 9).

Alternate Digit Casting for 11: Start with a number. Working from right to left, alternately add and subtract the digits. (Repeat as desired.) The original number is divisible by 11 if and only if the new number is divisible by 11.

Examples:

$2345823$ is divisible by 9 because $3+2+8+5+4+3+2=27$ is divisible by 9.

$9471282$ is divisible by 3 but not by 9, because $2+8+2+1+7+4+9=33$ is divisible by 3 but not by 9.

$1238537$ is not divisible by 3, because $7+3+5+8+3+2+1=29$ is not divisible by 3.

$7328519$ is divisible by 11 because $9-1+5-8+2-3+7=11$ is divisible by 11.

$9342886$ is not divisible by 11 because $6-8+8-2+4-3+9=14$ is not divisible by 11.

So what is going on? Why does this work? Are there other rules like this?

What you may not know is that the same rule tests for divisibility by 3, and that a very similar rule tests for divisibility by 11.

Direct Digit Casting for 3 and 9: Start with a number. Add up the digits to get a new number. (Repeat as desired.) The original number is divisible by 3 (or 9) if and only if the new number is divisible by 3 (or 9).

Alternate Digit Casting for 11: Start with a number. Working from right to left, alternately add and subtract the digits. (Repeat as desired.) The original number is divisible by 11 if and only if the new number is divisible by 11.

Examples

$2345823$ is divisible by 9 because $3+2+8+5+4+3+2=27$ is divisible by 9.
$9471282$ is divisible by 3 but not by 9, because $2+8+2+1+7+4+9=33$ is divisible by 3 but not by 9.
$1238537$ is not divisible by 3, because $7+3+5+8+3+2+1=29$ is not divisible by 3.
$7328519$ is divisible by 11 because $9-1+5-8+2-3+7=11$ is divisible by 11.
$9342886$ is not divisible by 11 because $6-8+8-2+4-3+9=14$ is not divisible by 11.

So what is going on? Why does this work? Are there other rules like this?

To understand this, we’ll need to know a little bit about modular arithmetic.

In modular arithmetic, we make the infinite set of integers into a more manageable, finite set based on their remainders. When we work modulo some integer $m>1$ , that means that all we care about is the remainder of a number when we divide by $m$ . In other words, if two numbers differ by a multiple of $m$ , we treat them as being the same number. So working modulo 2 means classifying numbers based on whether they are even or odd, working modulo 10 means classifying numbers based on their last digit, etc. (So modular arithmetic is a feat of abstraction.)

So addition and subtraction still make sense. That is, if two numbers $a,b$ have the same remainder modulo $m$ and two other numbers $c,d$ have the same remainder modulo $m$ , then $a+c$ and $b+d$ have teh same remainder modulo $m$ .

What’s less obvious (and more interesting) is that multiplication still makes sense. For example, since 2 and 15 have the same remainder modulo 13, and likewise -8 and 5 have the same remainder modulo 13, it must be true that $2(-8)=-16$ and $15(5)=75$ differ by a multiple of 13.

If this seems too confusing, think about what I’m saying modulo 10. I’m saying that, if all I want to know is the last digit of the answer to an addition/subtraction/multiplication problem, I only have to look at the last digits of the numbers involved. A number ending in 7 times a a number ending in 3 will be a number ending in 1, no matter what the specific numbers are.

(The technical term is that addition, subtraction, and multiplication are well-defined modulo $m$ . The situation with division is not so nice, but more on that another day.)

We work in base 10, which means that each place value counts for ten times as much as the one on the right. We have ten digits, from 0 to 9. So, if the $a$ ‘s are digits, the $n+1$ digit number $a_na_{n-1}\cdots a_2a_1a_0$ resolves as $a_0+10a_1+(10^2)a_2+(10^3)a_3+\cdots +(10^n)a_n$ . We can also talk about other bases. Any integer $b$ greater than 1 can play the role. Base 2 is what’s common called binary, etc.

Now we can understand why these rules work.

Working modulo 9, 10 and 1 are the same number, so, if the $a$’s are digits, $a_na_{n-1}\cdots a_1a_0 = 1a_0+10a_1+100a_2+\cdots+10^na_n$ is the same number (mod 9) as $1a_0+1^1a_1+1^2a_2+\cdots+1^na_n=a_0+a_1+\cdots+a_n$ . So a number and the sum of its digits are in the same class mod 9. In particular, either both are divisible by 9 or neither is (actually a little more is true: both numbers will have the same remainder). The same argument applies modulo 3. This explains the direct casting trick for 3 and 9.

Modulo 11, on the other hand, 10 is the same as -1. So $a_na_{n-1}\cdots a_1a_0 = 1a_0+10a_1+100a_2+\cdots+10^na_n$ is the same number (mod 9) as $1a_0+(-1)a_1+(-1)^2a_2+\cdots+(-1)^na_n=a_0-a_1+a_2-a_3+\cdots\pm a_n$ , leading to the alternate casting trick for 11.

So we get divisibility rules for 9 and 11 precisely because we work in base 10. If instead of base 10 we used some other base $b$ , the direct casting rule will apply to $b-1$ (and its factors), while the alternate casting rule wil apply for divisibility by $b+1$ . Some other civilization which uses base 42, say, would have easy rules for divisibility by 41 and 43.

All you computer types who think about numbers in binary should now have a trick for divisibility by 3. If you prefer hexadecimal, then direct casting is a divisibility rule for 15 (and 3 and 5), and alternate casting is a divisibility rule for 17.

Even if converting a number from one base to another makes you seasick, there are still more slick tricks we can learn. What about bases like 100, 1000, etc.? All this means is that we are consider pairs (triples, etc.) of decimal digits as a single unit. So the number 2463245, in base 100, has the digits (02)(46)(32)(45). So direct casting on pairs of digits tests for divisibility by 99 (or 3, 9, 11, 33), and alternate casting on pairs test for divisibility by 101. More useful is base 1000 (triples of digits, i.e. the blocks of digits set apart by commas in really big numbers). Then alternate casting is a rule for 1001 and its divisors; 1001 turns out to have interesting prime factors, namely 7, 11, and 13.

Presto! A simple way to test for divisibility by 7 or 13. Take the number 9524857394. Since $394-857+524-9=52$ , some easy addition shows this huge number is divisible by 13 but not by 7.

This entry was posted on Thursday, July 23rd, 2009 at 11:30 and is filed under Articles. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Not About Apples