Last week we looked at how to “cast out nines” to check arithmetic, and touched only briefly on its relationship with modular arithmetic and remainders. Here we’ll look at several explanations of why it works, aimed at different levels of students, with varying levels of success..

## Why we use 9: Modular arithmetic

We’ll start with a question from 1997:

Casting Out Nines and Elevens At a parent-teacher meeting this evening, the teacher asked the parentswhy nine is used in proving a math answer. She did not know the answer, and the parents didn't either. Can you help? Our fourth-grade students will be taking this new method of problem solving. EXAMPLE 6313 6+3 = 9 throw away 1+3 = 4 1452 4+5 = 9 throw away 1+2 = 3 7765 7+7+6+5 = 25, 2+5 = 7 If you're left with 7, then your answer is correct.

Susan has found the digital roots of 6313 and 1452 (4 and 3, respectively, whose sum is 7), and of their presumed sum, 7765 (also 7); as we saw last time, this doesn’t actually prove the answer *correct*, but only plausible (that is, it *does not* show that it is *incorrect*).

Doctor Rob answered, introducing ideas of modular arithmetic gradually:

This procedure for checking arithmetic is called "casting out nines," and has been known for some centuries. It is based onmodular arithmetic with modulus nine. Nine is used because it is the largest integer such that it fits into the following pattern: 10 = 9* 1 + 1 100 = 9* 11 + 1 1000 = 9* 111 + 1 10000 = 9* 1111 + 1 100000 = 9*11111 + 1 ... ... The powers of 10 on the left represent the place values of the various digits. The 1 on the far right represents the digit itself.

Now we can use those facts to break down any number.

Your example: 6313 = 6*1000 + 3*100 + 1*10 + 3 = 6*(9*111+1) + 3*(9*11+1) + 1*(9*1+1) + 3 =9*(6*111+3*11+1*1) + 6 + 3 + 1 + 3 6313 - (6+3+1+3) =9*(6*111+3*11+1*1) This shows that the number and the sum of its digitsdiffer by a multiple of nine. This is true for every counting number (positive integer). A consequence of this is that if, in an addition, subtraction, or multiplication problem, youreplace each number by the sum of its digits, you change the result by a multiple of nine.

Here’s a way to see that:

If the numbers \(A\) and \(B\) differ by a multiple of 9, that is, \(A-B=9n\). then

- \((A+C)-(B+C)=(A-B)+(C-C) = 9n\), so the
**sums**\(A+C\) and \(B+C\) differ by a multiple of 9; - \((A-C)-(B-C)=(A-B)-(C-C) = 9n\), so the
**differences**\(A-C\) and \(B-C\) differ by a multiple of 9; - \(AC-BC=(A-B)C = 9nC\), so the
**products**\(AC\) and \(BC\) differ by a multiple of 9;

In each case, replacing \(A\) with \(B\) makes a result that again differs from the original by a multiple of 9.

In particular, then, any sum, difference, or product is changed by a multiple of 9 when you replace each number by the sum of its digits.

The usual notation for this situation is to say that two numbers x and y arecongruent modulo mif their difference is a multiple of m. This is writtenx = y (mod m). In the case at hand 6313 = 6+3+1+3 = 13 (mod 9), and further 13 = 1+3 = 4 (mod 9). Similarly 1452 = 1+4+5+2 = 12 (mod 9), and further 12 = 1+2 = 3 (mod 9). The answer 7765 = 7+7+6+5 = 25 = 2+5 = 7 (mod 9).

Properly, we express congruence using a special “triple-equal” symbol: \(x\equiv y(\text{mod }9)\); that symbol could be used for all the equal signs here.

The word “modulus” is Latin for “small measure”; the modulus was thought of as a unit by which the difference between two numbers can be “measured” (evenly divided). “Modulo” is its ablative form, meaning “*with respect to* the modulus …”. So \(x\equiv y(\text{mod }9)\), read as “*x* is congruent to *y* modulo 9″, means “*x* is congruent to *y* with respect to the modulus 9″, or “*x* and *y* differ by a multiple of 9″.

If the answer 7765 is correct, then 6313 + 1452 = 4 + 3 = 7 (mod 9) and 7765 = 7 (mod 9) provides a degree of checking.If these two numbers disagree, you know you have made an arithmetic error.If they are the same, you have a certain degree of confidence that you have not, although not certainty! For example, a transposition of digits (7675, say) cannot be detected by casting out nines.

What we’ve seen here, expressed fully in terms of modular arithmetic, is that (1) because \(10\equiv 1(\text{mod }9)\), any number (written in base ten) is congruent to the sum of its digits, so that the digital root (obtained by repeatedly adding digits) is likewise congruent to the original number; and (2) addition, subtraction, and multiplication all work mod 9, so that we can replace each operand with anything congruent to it, and the result will again be congruent. Together, this explains casting out nines.

### Not only nines, but elevens

There is a related technique called "casting out elevens" which is based on the following pattern: 1 = 11* 0 + 1 10 = 11* 1 - 1 100 = 11* 9 + 1 1000 = 11* 91 - 1 10000 = 11* 909 + 1 100000 = 11* 9091 - 1 1000000 = 11* 90909 + 1 10000000 = 11*909091 - 1 ... ... 6313 = 6*1000 + 3*100 + 1*10 + 3 = 6*(11*91-1) + 3*(11*9+1) + 1*(11*1 - 1) + 3 = 11*(6*91+3*9+1*1) - 6 + 3 - 1 + 3 6313 - (3-1+3-6) = 11*(6*91+3*9+1*1) It uses thealternating-sign sumof digits, working *right to left*: 6313 = 3 - 1 + 3 - 6 = -1 = 10 (mod 11) 1452 = 2 - 5 + 4 - 1 = 0 (mod 11) 7765 = 5 - 6 + 7 - 7 = -1 = 10 (mod 11) The fact that 10 + 0 = 10 (mod 11) gives an additional check on the validity of the arithmetic.

Replacing each number with its elevens-root (I don’t know a standard word for this) means we are “doing the arithmetic modulo 11”; if the result doesn’t agree (modulo 11), then one of the calculations is wrong!

Casting out elevens is much less well known than casting out nines. It WILL detect digit transpositions.

But it will still miss transpositions between digits an even number of places apart, or other errors!

Now, can we explain all this without the complexity?

## Proving it for second graders … maybe

A 2004 question makes a big request:

Casting Out Nines for 2nd Graders Dear Dr. Math, Can you please send me a simpler explanation of WHY the Casting Out Nines method works than you have in your archives? I understand how to do it, but I need to know why it works. I have to present this methodso that second graders can understand why it works.

I answered:

Hi, Donna. I've tried a number of times to find a good way to prove the method at an elementary level, and found thatany really clear explanation requires some knowledge of modular arithmetic and algebra. Without those ideas, there's just too much work needed to work around them. But that's talking mostly aboutproofs. Second graders wouldn't appreciate an actual proof anyway, so we can just look for aplausible explanationto show HOW it works -- what's going on behind the scenes. That may be easier to handle, though we'll have to keep it extremely simple.

The first step is to boil the idea down to its essentials at an adult level.

The basic idea, leaving out all the details, is this:Adding the digits of a number decreases it by a multiple of 9, so repeating the process until you have a single digit leaves you with theremainderafter division by 9 (or with 9 if that remainder is 0). (In advanced terms, the digit sum iscongruentto the original number modulo 9). When numbers areadded or multiplied, the remainder of the result is the same as the sum or product of theremaindersof the given numbers. (In advanced terms, the sum and product arewell-defined in modular arithmetic; that is, theypreserve congruence.) So if the remainders on both sides of an equation arenotequal, then neither are the values of both sides themselves.

Now we want to take out the hard language:

For second graders, we'll want to work with a specificexamplerather than with generalities, and withadditionrather than multiplication. Take this sum as our example: 24 + 37 = 51 Is this correct? Well, we look at the left side, the sum. We add the digits of 24 and get 6; we add the digits of 37 and get 10, then add again to get 1. Now we add 6 and 1 to get7. On the right side, we add the digits of 51 to get 6; since this is not equal to7, our answer is wrong. (The right answer is 61, which does give a digit sum of 7.)

(Possibly it would be better to use an example of a *correct* calculation.)

Now, what is happening when we do that? Instead of adding 24 + 37, we're adding 6 + 1. Now, 6 is 18 less than 24, and 1 is 36 less than 37, so their sum is 18 + 36 less than the real sum. Do you see that 18 and 36 are bothmultiples of 9? That means that the sum we get, 7, is some number of 9's less than the real sum. This will always happen. [Why? Because replacing 20+4 with 2+4 takes away 20 and adds 2, which is the same as taking away 10 and adding 1 twice. But that means taking away a multiple of 9.]

Changing 10 to 1 reduces it by 9; changing 20 to 2 reduces it by twice as much. Every time, we are taking away a multiple of 9.

When we do the same thing to the 51, the sum of the digits, 5+1=6, is 45 less than 51 itself; so again we get a number that is some number of 9's less than the actual number. But that means that the numbers we get on the two sides should themselves bea multiple of 9 apart. In fact, since they are both single-digit numbers, they should be equal (unless one is 0 and the other is 9).Since they are not, the numbers can't be right.

This is an interesting way to see that 0 and 9 are equivalent here – the reason we call it “casting out nines”.

I'm not at all sure this will work for the average second grader; even though I avoided going into detail about place value and remainders, I had to bring inmultiples of 9. It's hard to avoid something like that, since that is what the technique is all about under the hood: multiples, remainders, modular arithmetic. Please let me know if you find a nice way to express these ideas for that age.

My real hope was that this would at least be comprehensible to the adults trying to explain!

Donna wrote back:

Thank you very much for the speedy reply. My presentation is tomorrow. Maybe the other educators in my group will have a suggestion for explaining it to second graders. I'll let you know if they do. Again, thank you!!!

We didn’t hear back.

## Proving it for high schoolers

A question in 2008 gave me another chance at a basic “proof” at a slightly higher level:

Why Casting Out Nines Works Hello. I have to do a math project for school, and one of the things I must know iswhythe method of "casting out nines" works. I know it has to do withmodular arithmeticbut can you please explain the math behind this method AS SIMPLY AS POSSIBLE. I would like it if you could explain itin simple terms, not college math. NOTE: I know how to do this method, so please do not include that with your response. I cannot find any place that clearly defines why this method works to me, because I don't understand what the web site is trying to say. I have tried reading about modular arithmetic but that is only part of the reason why this works and I really need someone to explain it loud and clear to me.

It’s possible that Las needed a clear explanation of the modular arithmetic as used in the proof; but it sounded like an explanation without that, and even without algebra, would be useful. I answered:

Hi, Las. Modular arithmetic provides alanguagein which it is easy to explain what is happening; without that language,it will take more words to make it clear(and even more if I wanted to give a complete proof), but it can be done. The basic idea of modular arithmetic is that two numbers are congruent modulo 9 when theyleave the same remainders on division by 9; you'll be seeing phrases like that all through what I write here!

What I’m trying to do is to translate the modular arithmetic language into the language of remainders. We’ll see if it works. I took the same general approach as above, using an example rather than lots of symbols.

Let's take a simple example; I'll check the addition 157 + 246. This way we can avoid using a lot of variables, but you can follow the ideas and see that they apply to any number. (This is how people talked about algebrabefore they had the idea of variables, so I'm following an old tradition.)

[As an example, here is how Al-khwarizmi explained how to solve \(x^2+bx=c\) (one of several cases of quadratic equations, when no negatives are allowed) by completing the square, using the example of \(x^2+10x=39\):

Symbols, like special words, are useful, though it is possible to do without them! But that’s just an aside …]

First, we’ll just do the check by casting out nines:

The check digit for 157 is 1+5+7 = 13, 1+3 = 4; and the check digit for 246 is 2+4+6 = 12, 1+2 = 3. The first thing to ask is,what do these numbers mean?The answer is, the check digit gives theremainder when you divide by 9. In our example, when you divide 157 by 9 you get 17 with a remainder of 4 (our check digit), and when you divide 246 by 9 you get 27 with remainder 3 (again our check digit).

### Why check digits are remainders

Why is that?What canadding the digitsof a number have to do with dividing and getting aremainder? Well, let's look at157, which we can write as1*100 + 5*10 + 7. Notice that 10 = 9+1 and 100 = 99+1;any power of ten is 1 more than a multiple of 9, and therefore will leave a remainder of 1 when divided by 9. So we can rewrite 157 as 157 = 1*100 + 5*10 + 7 = 1(99 + 1) + 5(9 + 1) + 7 = (1*99 + 5*9) + (1 + 5 + 7) Since the first part is a multiple of 9, the second part (the sum of the digits) will have thesame remainder; whatever remainder you get when you divide 1+5+7 by 9 is the remainder when you divide 157 by 9.

The number itself can be broken into a multiple of 9, plus the sum of the digits. Any two numbers that differ by a multiple of 9 (that is, that are congruent modulo 9) leave the same remainder.

So we can repeat the process with 1+5+7 = 13, adding its digits and again getting the same remainder.Once we get this down to one digit, it IS the remainder.So what have we learned? Thecheck digits are remainders; now we have to considerwhat happens to remainders when you add numbers. This will take more of the same kind of thinking.

### Why remainders are useful

Take our two numbers, 157 = 9*17 + 4 and 246 = 9*27 + 3. I've written each as a multiple of 9 plus its remainder (which is its check digit). Now let'sadd them: 157 + 246 = (9*17 + 4) + (9*27 + 3) = (9*17 + 9*27) + (4 + 3) = 9*(17 + 27) + (4 + 3) So the remainder when you divide the sum by 9 is the sum of the remainders, 4+3 = 7. Well, not always--if the sum of the remainders had been greater than 9, you'd have to divide by 9 again and take the final remainder. But in all casesthe remainder of the sum is the same as THE REMAINDER OF the sum of the remainders. This is where the language of modular arithmetic saves a lot of words!

In terms of modular arithmetic, the sum of the two numbers is congruent to the sum of the check digits.

This means that thecheck digit for the sumis the same as thecheck digit for the sum of the check digits--and that is what casting out nines is. If you find that this isnottrue, you know that the sum isincorrect.

Similarly, we find that the **product **of two numbers is congruent to the **product** of their check digits. Using the same numbers as an example,

$${\color{Red}{157}}\cdot{\color{Green}{246}}=(9\cdot17+{\color{Red}4})+(9\cdot27+{\color{Green}3})\\=(9^2\cdot17\cdot27+9\cdot17\cdot{\color{Green}3}+{\color{Red}4}\cdot9\cdot27)+{\color{Red}4}\cdot{\color{Green}3}\\=9\cdot(9\cdot17\cdot27+17\cdot{\color{Green}3}+{\color{Red}4}\cdot27)+{\color{Red}4}\cdot{\color{Green}3}$$ so the product leaves the same remainder as the product of the check digits, 12, namely 3. And, in fact, \(157\cdot246=38,622\), whose check digit is \(\require{cancel}\cancel{3}+8+\cancel{6}+2+2=12;\;\;1+2=3\)

Las replied:

Thank you so very much. This was the most helpful thing any web site did for me. I have a feeling I'm going to get a 100 on this math project! Thanks again for taking your time to help me out. Without you, I wouldn't understand this.

So, this time, it worked.