A Guide to High-Speed Mathematics

Two of my friends who know I love math gave me an old (1959) book about high speed mathematics. Some of it I was taught in school and some I want to start using, but there was one thing in particular that struck me as odd. There is a technique they call digit-sum that checks your work for addition, subtraction, multiplication and division by taking the digit sums of each number and doing the problem with them as well as the original numbers- the digit-sum of the answer should be the answer of the digit-sums (for the mathematically inclined this may tip you off about where I'm going with this- sounds an awful lot like a homomorphism).To take a digit-sum of a natural number, add its digits, and if it ever goes above 10, apply the digit-sum to that number before proceeding. Another way to say this is the digit-sum is the sum of the digits modulus 9. Notice that there are only 0-8 (9 acts exactly like 0) so there is a 1/9 chance (all else being equal) that a mistake will go undetected (more on this latter).

My first thought was that this must be a homomorphism of some algebraic structure, and the reason it works must be some property of that structure and therefore the integers that form its underlying set (remember that homomorphisms isolate some property of the source structure), so I tried to prove some properties. At first I didn't notice that 9 was in the same equivalence class as 0, so I thought that there where no additive inverses. This led me to believe that the structure was a commutative semi-ring with unity- the same structure as the polynomial types from the theory of combinatorial species! Then I realized that we were just in Z mod 9 and there are additive inverses, making it a commutative ring with unity. It is not quite an integral domain because there are divisors of 0 as in the equation 3*6=0. The reason +, *, and - all work is that it is a ring homomorphism- f(x+y) = f(x)+f(y) and f(x*y) = f(x)*f(y) where the second plus and multiple are the digit-sum equivalent of + and *, and the existence of additive inverses (the 9s complement) gives subtraction (also f(0)=0 and f(1)=1). Division took me a while to understand- I was trying to rearrange the equation, but clearly there are no multiplicative inverses! Recall the definition of integer division, however- n = m*q + r. Therefore f(n) = f(m)*f(q)+f(r).
With this new knowledge we quickly see we the trick they have done here- for any system of base b the digit-sum is Z mod b and the property of Z that is preserved is the remainder after division by b. While it would work for any n (and the greater n the more chance of detecting errors), using the base of the number system we are used to makes it seem more magical when seeing it for the first time. Amusingly in binary it corresponds to an even-odd parity check.

That was fun! It turned out to be ultimately trivial (I think a lot of math feels that way when you figure it out), but for me it was an exciting discovery.