Before the advent of pocket calculators, arithmetic was generally
done by hand, and was frequently subject to errors. One technique
to quickly verify that a calculation was accurate was called
casting out nines.
This meant taking the sum of the digits of a number,
subtracting 9 whenever the sum was greater than 9, or, equivalently, taking the sum of the digits and then taking the sum of the digits of that sum, and so on, until sum was less than 9. It was asserted
that for any integers x, y, and z, if
,
the sum of the digits of x plus the sum of the digits of y
would always be congruent mod 9
with the sum of the digits of z.
Similarly for multiplication, if
,
the sum of the digits of x times the sum of the digits of y
would always be congruent mod 9
with the sum of the digits of z.
So, for example, 241 x 382 = 92,062. The sum of digits of 241 = 2+4+1 = 7, and the sum of digits of 382 = 3+8+2 = 13, sum of digits of 13 = 4. So we can expect the product of 241 and 382 to have the sum of digits = 7 x 4 = 28 = 2 + 8 = 10 = 1 + 0 = 1. Examining our initial calculation, sum of digits of 92,062 = 9+ 2 + 0 + 6 + 2 = 19, 1 + 9 = 10, 1+0= 1. The match doesn't guarantee that our calculation is correct, but will definitely tell us if it is wrong.
This article develops a rigorous proof of the correctness of that technique.
Lemma 1:Every positive integer is greater than or equal to the sum of its digits.
Proof: Let n be a positive integer
with non-negative digits (from right to left) of
so that
.
By induction over the number of digits, we see clearly that for single-digit
numbers, . If we can show that the proposition
is true for m digit numbers, it must also be true for
m + 1 digit numbers, because since
,
and since every digit is non-negative,
so
Hence, the proposition holds for numbers of any number of digits. .
Lemma 3: Repeated applications of
will eventually yield a single non-negative number less than 9.
Proof: Consider the series
{}.
Evaluating each adjacent pair of terms, we see it cannot be the case
that each pair must have the strictly greater than relation, because there
are only finitely many non-negative integers less than n. Eventually,
by Lemma 2, there must be a pair
.
This can only be true when
, since
and
for all
.
So for conciseness, we will say in this article that
means repeated evaluations of the sum of digits function
until .