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 d0, d1,... is an integer in the range from 0 to B-1.  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   ...d2d1d0.  Typically the left-most digit is the largest non-zero digit.  This form of expression is called place-value notation, and the integer B is called the base (or radix).  Obviously we have d0 = N modulo B, so if we are working in the modulus B we can simply replace each number by its least significant digit.

 

The base-B digits of a number also satisfy some interesting relations modulo B-1.  If we let SB(N) denote the sum of the base-B digits of N, we have

 

 

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

 

 

We can verify this explicitly by simply multiplying out the base-B representations

 

 

The base-B digits of z = xy are then related to the coefficients of this product by

 

 

and so on, where c0, c1,... are the "carry" terms in the multiplication.  (The carry terms need not be in the range from 0 to B-1.)  Adding all these expressions together, we get

 

 

This confirms the previous congruence modulo B-1, 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 B-1 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 B-1 assures us that the product is correct modulo B(B-1), 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 base-B 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 three-digit integer, a two-digit integer, and a four-digit integer.  For example, one possible social security number is 728;35;4589.  (We use semi-colons 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 four-digit number is the product of the three-digit and two-digit 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 three-digit integer, Y is a two-digit integer, and Z is a four-digit 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 Z2 - 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.

 

Return to MathPages Main Menu