User:CaritasUbi/Casting out nines

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 $x+y=z$, 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 $x\cdot y=z$, 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.

This article develops a rigorous proof of the correctness of that technique.

Definition 1

Define $s:\mathbb {N} \to \mathbb {N}$ to be a function that maps an integer n to the sum of its digits. That is, for the digits of n (from right to left), $s(n)=d_{0}+d_{1}+d_{2}+\dotsb =\sum _{k=0}^{\infty }d_{k}$

where each of the digits $d_{k}$ is an integer $0\leq d_{k}\leq 9$.

Lemma 1

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 $d_{0},d_{1},\dotsc ,$ so that $n=d_{0}+10d_{1}+100d_{2}+\dotsc =\sum _{k=0}^{\infty }10^{k}\cdot d_{k}$. By induction over the number of digits, we see clearly that for single-digit numbers, $d_{0}=d_{0}$. 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 $\sum _{k=0}^{m}10^{k}\cdot d_{k}>=\sum _{k=0}^{m}d_{k}$, and since every digit $d_{k}$is non-negative, $10^{k}d_{k}\geq d_{k}$ so $\sum _{k=0}^{m}10^{k}\cdot d_{k}+(10^{m+1}\cdot d_{m+1})>=\sum _{k=0}^{m}d_{k}+(d_{m+1})$

Hence, the proposition holds for numbers of any number of digits. $\Box$.

Lemma 2

Lemma 2: Every positive integer is congruent mod 9 to the sum of its digits.

Proof: Let n by a positive integer with non-negative digits (from right to left) $d_{0},d_{1},\dotsc .$ so that

$n=d_{0}+10d_{1}+100d_{2}+\dotsb =\sum _{k=0}^{\infty }10^{k}d_{k}$ (1)

In this case,

$s(n)=d_{0}+d_{1}+d_{2}+\dotsb =\sum _{k=0}^{\infty }d_{k}$ (2)

By the definition of congruence, $a\equiv b$ mod 9 if and only if there is some integer m such that $a-b=p\cdot m$. So $a\equiv b$ mod 9 if and only if there is some integer m such that $a-b=9\cdot m$.

Now consider

$n-s(n)=\sum _{k=0}^{\infty }10^{k}d_{k}-\sum _{k=0}^{\infty }d_{k}$

$=(d_{0}-d_{0})+(10d_{1}-d_{1})+(100d_{2}-d_{2})+(1000d_{3}-d_{3})+\dotsb$

$=0d_{0}+9d_{1}+99d_{2}+999d_{3}+\dotsb$

$=9\cdot (0d_{0}+1d_{1}+11d_{2}+111d_{3}+\dotsb )$ (3)

This means that $n-s(n)$ is an even multiple of 9, hence

$n\equiv s(n)$ mod 9  $\Box$.

Lemma 3

Lemma 3: Repeated applications of $s(n)$ will eventually yield a single non-negative number less than 9.

Proof: Consider the series {$n,s(n),s(s(n)),\dotsc ,s^{k}(n),\dotsc$}. 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 $s^{k}(n)=s^{k+1}(n)$. This can only be true when $s^{k}(n)\leq 9$, since $s^{k+1}(n)=s^{k}(n)+d_{k+1}$ and $10^{k}>k$ for all $k\geq 0.$  $\Box$.

So for conciseness, we will say in this article that $s(n)$ means repeated evaluations of the sum of digits function until $0\leq s(n)<9$.

Theorem 1

Theorem 1: For all $m,n\in \mathbb {N}$: $s(m)+s(n)\equiv s(m+n)$ mod 9 and $s(m)\cdot s(n)\equiv s(m\cdot n)$ mod 9.

Proof: Let $m,n\in \mathbb {N}$ be given, where m has non-negative digits $c_{0},c_{1},c_{2},\dotsb$ as defined above, and n has non-negative digits $d_{0},d_{1},d_{2},\dotsb$.

Then

$m=c_{0}+10\cdot c_{1}+100\cdot c_{2}+\dotsb =\sum _{k=0}^{\infty }10^{k}\cdot c_{k}$ (1)

and

$n=d_{0}+10\cdot d_{1}+100\cdot d_{2}+\dotsb =\sum _{k=0}^{\infty }10^{k}\cdot d_{k}$ (2)

hence, for addition,

$m+n=(c_{0}+d_{0})+10(c_{1}+d_{1})+100(c_{2}+d_{2})+\dotsb =\sum _{k=0}^{\infty }10^{k}\cdot (c_{k}+d_{k}).$ (3)

Then by Lemmas 2 and 3,

$s(m+n)=\sum _{k=0}^{\infty }(c_{k}+d_{k})=(c_{0}+d_{0})+(c_{1}+d_{1})+(c_{2}+d_{2})+\dotsb$

$=(c_{0}+c_{1}+c_{2}+\dotsb )+(d_{0}+d_{1}+d_{2}+\dotsb )$

$=\sum _{k=0}^{\infty }c_{k}+\sum _{k=0}^{\infty }d_{k}$

$=s(m)+s(n),$

which proves the first part of the theorem.

Similarly, for multiplication,

$s(m)=c_{0}+c_{1}+c_{2}+\dotsb =\sum _{k=0}^{\infty }c_{k}$

$s(n)=d_{0}+d_{1}+d_{2}+\dotsb =\sum _{k=0}^{\infty }d_{k}$

By Lemma 3, we can freely interchange x and s(x) and maintain equivalence mod 9, so

$s(m\times n)\equiv s(\sum _{k=0}^{\infty }10^{k}c_{k}\times \sum _{k=0}^{\infty }10^{k}d_{k})\mod 9$

$\equiv s(\sum _{k=0}^{\infty }c_{k}\times \sum _{k=0}^{\infty }d_{k})\mod 9$

$\equiv s(s(m)\times s(n))\mod 9$

$\equiv s(m)\times s(n)\mod 9$

hence,

$s(m\times n)=s(m)\times s(n)$

which proves part 2.$\Box$