Casting Out Nines 

For any given integer B greater than 1, each natural number N has a unique expression of the form

_{} 

where each of the digits d_{0}, d_{1},... is an integer in the range from 0 to B1. It's conventional to omit the operation symbols and powers of B, and simply express the number N by its sequence of digits, arranged in descending order. Thus the number N would be expressed as the string of digits ...d_{2}d_{1}d_{0}. Typically the leftmost digit is the largest nonzero digit. This form of expression is called placevalue notation, and the integer B is called the base (or radix). Obviously we have d_{0} = N modulo B, so if we are working in the modulus B we can simply replace each number by its least significant digit. 

The baseB digits of a number also satisfy some interesting relations modulo B1. If we let S_{B}(N) denote the sum of the baseB digits of N, we have 

_{} 

Since each of the quantities B^{k}1 is divisible by B1, we see that N is congruent to S_{B}(N) modulo B1. (This is also obvious from the fact that B = 1 modulo B1, and so every power of B is also congruent to 1, and thus the baseB representation of a number modulo B1 reduces to just the sum of its digits.) It follows that N is also congruent to S_{B}(S_{B}(N)), and so on. Thus to find the residue class of N modulo B1 we need only sum the baseB digits of N, and then sum the baseB digits of the resulting number, and so on, until reaching a single digit result. Equivalently, we can just evaluate modulo B1 the sum of the digits of N. This shows that if xy = z for two integers x,y, the congruence xy = z (mod B1) can be rewritten in terms of the residues modulo B1 as 

_{} 

We can verify this explicitly by simply multiplying out the baseB representations 

_{} 

The baseB digits of z = xy are then related to the coefficients of this product by 

_{} 

and so on, where c_{0}, c_{1},... are the "carry" terms in the multiplication. (The carry terms need not be in the range from 0 to B1.) Adding all these expressions together, we get 

_{} 

This confirms the previous congruence modulo B1, and also gives a simple formula for the sum of the carries in a multiplication in terms of the sums of digits of the operands and product. 

This is the basis for the old technique of "casting out nines", which was sometimes useful for checking multiplications performed by hand. To illustrate, suppose we multiply 23579 by 84427 to give the product 199074233. Needless to say, it's easy to check our calculation modulo 10 by noting that the residues of the operands are 9 and 7 (mod 10), giving a product of 63, whose residue is 3 (mod 10), consistent with the fact that the residue of 199074233 (mod 10) is 3. This check just makes use of the least significant digit of each number, so it is not very robust. 

For a stronger test, we can verify our calculation modulo 9, which can be done easily by means of the congruences modulo B1 described above. We first find the residue class of 23579 (mod 9), which we can do by simply adding up the digits and discarding all multiples of 9. This is why the method is called "casting out nines". The number 23579 has the digits 2, 3, 5, 7, and 9. We can obviously ignore the digit 9, and we can discard the digits 2 and 7 because they sum to 9. This leaves just 3 + 5 = 8, so we know that 23579 is congruent to 8 (mod 9). Likewise we can sum the digits of 84427, casting out all whole multiple of 9 along the way, to give the result 7. Now, the product of 8 and 7 is 56, and the sum of those digits is 5+6=11, and the sum of those digits is 1+1=2. To check the correctness of our multiplication, we just need to verify that the sum of the digits of the product 199074233, after casting out all multiples of 9, is 2. 

The combination of the checks modulo B and modulo B1 assures us that the product is correct modulo B(B1), which is 90 in decimal arithmetic. The chance of a random error passing both of these tests is about 1/90. With roughly the same amount of labor we can use a process of “casting out elevens” to perform a similar test modulo B+1 by summing the baseB digits of the number with alternating signs. For example, the decimal number 73875613 is congruent modulo 11 to 3 – 1 + 6 – 5 + 7 – 8 + 3 – 7. To perform this summation in our heads, we can sum the positive terms 3+6+7+3, casting out elevens as we go, giving the result 8. (We could also just sum these numbers to give 19, and then repeat to give 9 – 1 = 8.) Then we can sum the negative terms 1+5+8+7, casting out elevens, to give 10. The overall residue modulo 11 is therefore 8 – 10, which is 2, congruent to 9 mod 11. 

As an illustration of the occasional usefulness of "casting out nines", consider social security numbers, which can be regarded as consisting of a threedigit integer, a twodigit integer, and a fourdigit integer. For example, one possible social security number is 728;35;4589. (We use semicolons to avoid confusion between the usual dashes and minus symbols.) Do there exist any social security numbers such that each of the numerals 1 through 9 appears exactly once, and such that the fourdigit number is the product of the threedigit and twodigit numbers? 

We can use modulo 9 arithmetic to simplify the search for solutions. It's useful to recall the multiplication table modulo 9. 



Let's denote a social security number by X;Y;Z, where X is a threedigit integer, Y is a twodigit integer, and Z is a fourdigit integer. Since we require that each of the numerals 1 through 9 appears exactly once, we have X + Y + Z = 0 (mod 9). We also require XY = Z (mod 9). Eliminating Y from these two congruences, we have 

_{} 

It follows that, for any given residue Z (mod 9), we have 

_{} 

This has integer solutions if and only if Z^{2 } 4Z is a square (mod 9). The only squares modulo 9 are 0, 1, 4, and 7, so the only possible residue classes for Z are 0 and 4. Noting that 0 has three square roots (0,3,6) modulo 9, each of these values of Z gives three sets of X and Y values, as listed below. 


Now we need only consider each of these six possibilities in turn to determine all possible solutions. Taking the case X = Y = Z = 0 (mod 9), we know Y must be one of the numbers 18, 81, 27, 72, 36, 63, 45, or 54. If Y = 18, we know X and Z must be composed of the digits 2, 3, 4, 5, 6, 7, and 9, each appearing exactly once, such that X = Z = 0 (mod 9). Hence X must be composed of the digits in one of the sets {2,7,9}, {3,6,9}, {4,5,9}, {5,6,7}. Focusing on the first set, {2,7,9}, it's clear that the first digit must be 2 (because X cannot exceed 700 without Z exceeding 9999), and the last digit cannot be 9 (because the product of numbers ending with 8 and 9 ends in 2, which means the numeral 2 would be repeated). Therefore, the only possibility for the set {2,7,9} is X = 297. If we then multiply this out, we get (297)(18) = 5346, which is indeed a solution. We can quickly rule out the remaining three possible sets of numerals for X, so the only solution with X = Y = Z = 0 (mod 9) and Y = 18 is the social security number 297;18;5346. Clearly we can rule out Y = 81 based on size alone, so the next possible case is Y = 27, which means X must be composed of the digits in one of the sets {1,8,9}, {3,6,9}, {4,5,9}, {4,6,8}. Focusing on {1,8,9}, the first digit must be 1, so the only possibilities are 198 and 189. Indeed we find that (198)(27) = 5346, so this is another solution. The other three digit sets can be immediately ruled out for X due to size. Continuing on in this way, we can show that none of the remaining values of Y leads to a complete solution, so there are just two solutions of the form X = Y = Z = 0 (mod 9). 

Applying the same sort of analysis of the case X=6, Y=3, Z=0 (mod 9), we find that there are exactly three solutions of this form, namely 159;48;7632, 186;39;7254, and 483;12;5796. The case X=3, Y=6, Z=0 (mod 9) yields just one solution, namely 138;42;5796. With Z=4 (mod 9), only the case X=4,Y=1, Z=4 (mod 9) yields a solution, namely 157;28;4396. Thus we have determine that there are exactly seven social security numbers with the specified properties: 

It's interesting that this set contains two pairs with the same last four digits. 

For an amusing anecdote on “casting out nines”, see the article on Mayan Numeration. 
