Casting Out Nines

You may already be familiar with the divisibility rule that says a number is evenly divisible by 9 if and only if the sum of its digits is also divisible by 9. For example, I know 3,645 is divisible by 9 without dividing because its digits add up to 18, which I remember from elementary school to be 2 * 9.

This is an interesting rule because it leads to a recursive property of divisibility by 9. Notice that the digits of 18 in the preceding example also add up to 9. If we have a larger number like 13,286,025,801 we can repeatedly apply the same rule until we get down to one digit. Only if that single digit is a 9 is the original number (and every digital sum in between) divisible by 9.

For example, the sum of the digits of 13,286,025,801 is:

1 + 3 + 2 + 8 + 6+ 0 + 2 + 5 + 8 + 0 + 1 = 36

and the sum of the digits of 36 is:

3 + 6 = 9

This process of repeatedly summing the digits of a number until you're left with a single digit is called finding the number's digital root. If the digital root of a number is 9, then that number is divisible by 9.

For small numbers like the ones above it's easy to just do long division to see if a number is evenly divisible by 9, but for extremely large numbers with hundreds of digits, division can be quite time consuming. For example, can you tell me if

153,441,702,921,204,324,780,111,405,711,
801,641,412,504,117,621,135,207,441,603,
126,450,890,010,720,810,243,171,423,583,
110,999,306,450,902,232,414,027,522,126,
087,102,603,909,333,306,252,412,702,011

is divisible by 9? You might be awhile if you try to solve this using long division. I can tell you that this number is divisible by 9, but before you add up all the digits, let me show you a shortcut called "casting out nines." Let's first try it out on the following example, which is a little bit more manageable

1,729,254,036

Start off adding from the left as normal, and for each digit you add, keep a running total.

1 + 7 = 8

8 + 2 = 10

When you reach a total greater than 9, as I have here after the third digit, "cast out" a 9 from the total by simply subtracting 9 from it. In this case our running total of 10 becomes 1.

1 + 9 = 10 (-9 = 1)

1 + 2 = 3

3 + 5 = 8

8 + 4 = 12 (-9 = 3)

3 + 0 = 3

3 + 3 = 6

6 + 6 = 12 (-9 = 3)

If the final total isn't 9 (or 0 after casting out that final 9) then the number is not divisible by 9. Since we were left with a remainder of 3, we now know that 1,729,254,036 is not divisible by 9.

An even quicker method of casting out nines is by grouping the digits that add up to 9 and eliminating them. The sum

1 + 7 + 2 + 9 + 2 + 5 + 4 + 0 + 3 + 6

is much easier to reduce if you group it by digits that add up to 9.

1 + (7 + 2) + (9) + 2 + (5 + 4) + 0 + (3 + 6)

You can cast out these nines at this step before you do any addition at all.

1 + (0) + (0) + 2 + (0) + 0 + (0)
1 + 2 = 3

You can repeat the grouping and casting process as many times as you need before summing the remaining digits.

Now that you know these shortcuts, take a closer look at that monstrous 150-digit number that I showed you earlier. Using the grouping and casting method it shouldn't take more than a moment to reduce even that large a number to see that it is divisible by 9.

Why does the divisibility test even work?

To understand why the test for divisibility by 9 works, we need to use a few properties of congruences. Let's start with the fact that

10 ≡ 1 (mod 9)

which in English says that 10 is congruent to 1 modulus 9, or in plain English that 10 and 1 both leave the same remainder (sometimes called the residue) when divided by 9. (In fact, if the right-hand side of the congruence, in this case 1, is less than the modulus, then the right-hand side is the remainder when the left-hand side is divided by the modulus.) In general,

b ≡ c (mod n)

says that the difference between b and c is evenly divisible by n.

One algebraic property of congruences says that we can raise both sides of the congruence to the same power and the modulus will stay the same (this can be more generally stated as P(a) ≡ P(b) (mod n), where P(x) is any polynomial). Using this property we can say that

10² ≡ 1² (mod 9)

or

100 ≡ 1 (mod 9)

You can substitute any non-negative whole exponent you like.

10⁰ ≡ 1⁰ (mod 9)

10¹ ≡ 1¹ (mod 9)

10² ≡ 1² (mod 9)
10³ ≡ 1³ (mod 9)

...

10ⁿ ≡ 1ⁿ (mod 9)

So 10 raised to any natural exponent will leave a remainder of 1 when divided by 9.

10ⁿ ≡ 1 (mod 9)

This should be intuitively obvious when you consider that

10³ - 1 = 1,000 - 1 = 999 is evenly divisible by 9

10⁴ - 1 = 10,000 - 1 = 9,999 is evenly divisible by 9

10⁵ - 1 = 100,000 - 1 = 99,999 is evenly divisible by 9

...

Another property of congruences says that we can multiply both sides by the same number and the congruence remains unchanged. So starting back at

10 ≡ 1 (mod 9)

we can multiply both sides by any number and still have a valid congruence.

10 * 2 ≡ 1 * 2 (mod 9)
20 ≡ 2 (mod 9)

10 * 5 ≡ 1 * 5 (mod 9)
50 ≡ 5 (mod 9)

10 * 8 ≡ 1 * 8 (mod 9)
80 ≡ 8 (mod 9)

Starting from the following statements (that we showed to be true above)

1000 ≡ 1 (mod 9)

100 ≡ 1 (mod 9)

10 ≡ 1 (mod 9)

1 ≡ 1 (mod 9)

we can multiply both sides of each congruence by any number we like.

1000 * 3 ≡ 1 * 3 (mod 9)

100 * 6 ≡ 1 * 6 (mod 9)

10 * 4 ≡ 1 * 4 (mod 9)

1 * 5 ≡ 1 * 5 (mod 9)

is the same as

3000 ≡ 3 (mod 9)

600 ≡ 6 (mod 9)

40 ≡ 4 (mod 9)

5 ≡ 5 (mod 9)

We can add congruences together as long as they have the same modulus. Adding the four congruences above we get

3000 + 600 + 40 + 5 ≡ 3 + 6 + 4 + 5 (mod 9)

or

3645 ≡ 3 + 6 + 4 + 5 (mod 9)

Doesn't that look like it says that 3645 is congruent to the sum of its own digits modulo 9? Yes, in fact, it does. I deliberately chose the numbers 3, 6, 4, and 5 so that we would arrive back at a familiar example (from the first paragraph of this post), but I could have chosen any digits I wanted. This relationship holds true for any natural number. If s is the sum of the digits of n, then n is congruent to s modulo 9.

n ≡ s (mod 9)

But we're only really concerned with the cases where the sum of the digits is evenly divisible by 9. Another way of stating this is

s ≡ 0 (mod 9)

This brings us to the last algebraic property of congruences that we need to use (I promise, this is the last one). Remember that the transitive property of regular arithmetic says that if a = b and b = c, then a = c. The transitive property of congruences is similar. It says that if

a ≡ b (mod n)

and

b ≡ c (mod n)

then

a ≡ c (mod n)

This is simply saying that if a and b leave the same remainder when divided by n, and b and c leave the same remainder when divided by n, then a and c must also leave the same remainder when divided by n. For a concrete example, consider that

32 ≡ 18 (mod 7) and 18 ≡ 11 (mod 7)

so that

32 ≡ 11 (mod 7)

(They all leave a remainder of 4.)

Since we've already shown that in the general case

n ≡ s (mod 9)

and we know that in the particular cases we're concerned with that the sum of the digits is evenly divisible by 9, or

s ≡ 0 (mod 9)

we can say that in those cases

n ≡ 0 (mod 9)

This means that in those cases where the sum of the digits of n is divisible by 9, the number n itself is also divisible by 9. Precisely what we set out to prove.