Direct proof using summation

Question

I'm trying to provide a general proof for the following theorem.

Let $0 < n < 1000$ be an integer. If the sum of the digits of $n$ is divisible by $9$, then $n$ is divisible by $9$.

The book showed us how to do this in the following way.

$n = 100a + 10b +c\,(1)$

$a + b+ c = 9k, k\in \mathbb{Z}\,(2)$

Add $99a + 9b$ to both sides of $(2)$ to make the left side match $(1)$

$a + b + c + 99a + 9b = 9k + 99a + 9b$

$100a + 10b + c = n = 9(k+11a+b)$

Since integers are closed by addition and $k, a, b \in \mathbb{Z}$, $(k+11a+b) \in \mathbb{Z}$

QED.

Now it asks us to generalize this proof to any integer.

I started off by giving the following representation to $n$.

$n = \sum_{i=0}^{k-1} 10^ia_i\,(1)$ where $a_i$ is a digit

$\sum_{i=1}^{k-1}a_i=9q, \in \mathbb{Z}\,(2)$

$\sum_{i=1}^{k-1}(10^i - 1)a_i + \sum_{i=1}^{k-1}a_i = \sum_{i=1}^{k-1}(10^i-1)a_i + 9q\,(3)$

After this, I'm unsure of how to show that the LHS of $(3)$ is the same as the RHS of $(1)$ and how the RHS of $(3)$ is divisible by $9$. I think there's some sort of sequences/series trick involved that isn't coming to mind.

---

Attempt at Proof

Lemma 1: $(\forall i \in \mathbb{Z})(i \geq 0)(9 \mid 10^i -1)$

Proof by Contradiction

Assume: $(\forall i \in \mathbb{Z})(i \geq 0)(9 \not \mid 10^i -1)$

Let $i = 1$

$9 \not \mid 10^1 - 1 \implies 9 \not \mid 9$. Contradiction.

---

Theorem 1: $(\forall n \in \mathbb{Z})$($9 \mid$sum of digits in $n$ $\implies 9 \mid n$)

$n = \sum_{i=0}^{k-1} 10^ia_i\,(1)$ where $a_i$ is a digit

$\sum_{i=1}^{k-1}a_i=9q, q \in \mathbb{Z}\,(2)$

$\sum_{i=1}^{k-1}(10^i - 1)a_i + \sum_{i=1}^{k-1}a_i = \sum_{i=1}^{k-1}(10^i-1)a_i + 9q_3\,(3)$

By Lemma 1, $9 \mid \sum_{i=1}^{k-1}(10^i - 1)a_i$. The above statement can be rewritten as.

$\sum_{i=1}^{k-1}9q_ia_i + \sum_{i=1}^{k-1}a_i = 9q_x + 9q_y$ where $q_i,q_x,q_y \in \mathbb{Z}$

$\sum_{i=1}^{k-1}9q_ia_i + \sum_{i=1}^{k-1}a_i = 9(q_x+q_y)$

So I have a few problems with this:

• Is Lemma 1 strong enough? Since the claim is $\forall i$ and I found one $i$ that breaks it, I figured it would work.

• At the end of my partial proof, I've proved that the RHS is divisible by $9$ but I don't know how to show the LHS is equal to $n$.

Answer 1

$$\mathring{n} : \mbox{ multiple of }n$$ $$ 9k = \sum_{i=0}^{n} 10^i a_i = \sum_{i=0}^{n} (9+1)^i a_i = \sum_{i=0}^{n} (\mathring{9} + 1) a_i = \mathring{9}+ \sum_{i=0}^{n} a_i = 9k \iff \sum_{i=0}^{n} a_i = \mathring{9} $$

Answer 2

Indeed,

$$m=\sum_{k=0}^{n} 10^ka_k$$

$$=\sum_{k=0}^{n} (10^k-1+1)a_k$$

$$=\sum_{k=0}^{n} (10^k-1)a_k+\text{sum of digits of number}$$

Note that $10^k-1$ is divisible by $9$ for all $k$ nonnegative integers because for $k \geq 2$:

$$\frac{10^k-1}{10-1}=\sum_{i=0}^{k-1} 10^i=\text{ sum of some integers}=\text{some integer}$$

Where the formula used is that of geometric sums. Of course it also holds for $k=0$ and $k=1$. And if $m$ nonnegative is divisible by $9$ it follows the digit sum of $m$ is divisible by $9$ :

$$\sum_{k=0}^{n} a_k=m-\sum_{k=0}^{n} (10^k-1)a_k=9w-9s$$

For some integers $w$ and $s$. We also easily see it works the other way: if the sum of the digits of $m$ is divisible by $9$ because $\sum_{k=0}^{n} (10^k-1)a_k$ is also, them $m$ must be divisible by $9$.

Answer 3

This can be easily shown by congruency. $$10\equiv 1 \pmod9 $$ Thus $$10^i\equiv 1 \pmod9 \forall i\in \mathbb N $$ Thus we can obtain that a number congruences to the sum of the digits in modulo 9. Thus we get the result.

Answer 4

For reference, here is a proof given in A.J.M. van Gasteren's dissertation, "On the shape of mathematical arguments" (Technische Universiteit Eindhoven, 1988, http://dx.doi.org/10.6100/IR337809, Open Access from TUE, later published by Springer in LNCS under the same title):

with $\;r(n)\;$ being defined as the sum of the digits of natural number $\;n\;$'s decimal representation

(p. 30)

We adopt the decimal positional system, dropping, however, the constraint that each digit be less than $10$. We start with the decimal number having $\;n\;$ as its only significant "digit" —and, hence, having digit sum $\;n\;$—, and by repeated carries transform it into $\;n\;$'s standard decimal representation —which has digit sum $\;r( n)\;$— . A carry consists in subtracting $10$ from a digit $\;\ge 10\;$ and adding, or creating, $1$ at the position to the immediate left. Each carry, hence, changes the digit sum by $\;-9\:$ . The process terminates because the digit sum is at least $0$ and decreases at each carry. Hence $\;r( n) = n + \text{multiple of } 9\;$.

(pp. 32-33, end of Chapter 5, "On a proof by Arbib, Kfoury, and Moll")

The entire chapter is well worth a read, as is the entire booklet, if you want to learn about finding, designing, and writing down proofs.