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 parents why 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 on modular 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 digits differ 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, you replace 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 are congruent modulo m if their difference is a multiple of m. This is written x = 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 the alternating-sign sum of 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 method so 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 that any 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 about proofs. Second graders wouldn't appreciate an actual proof anyway, so we can just look for a plausible explanation to 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 the remainder after division by 9 (or with 9 if that remainder is 0). (In advanced terms, the digit sum is congruent to the original number modulo 9). When numbers are added or multiplied, the remainder of the result is the same as the sum or product of the remainders of the given numbers. (In advanced terms, the sum and product are well-defined in modular arithmetic; that is, they preserve congruence.) So if the remainders on both sides of an equation are not equal, 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 specific example rather than with generalities, and with addition rather 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 get 7. On the right side, we add the digits of 51 to get 6; since this is not equal to 7, 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 both multiples 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 be a 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 in multiples 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 is why the method of "casting out nines" works. I know it has to do with modular arithmetic but can you please explain the math behind this method AS SIMPLY AS POSSIBLE. I would like it if you could explain it in 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 a language in 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 they leave 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 algebra before 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 the remainder 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 can adding the digits of a number have to do with dividing and getting a remainder? Well, let's look at 157, which we can write as 1*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 the same 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? The check digits are remainders; now we have to consider what 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's add 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 cases the 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 the check digit for the sum is the same as the check digit for the sum of the check digits--and that is what casting out nines is. If you find that this is not true, you know that the sum is incorrect.
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.