If $99\mid n$ for $n\in\mathbb{N}$, then the digit sum is $\geq 18$

Question

I have the following task:

If $99\mid n$ for $n\in\mathbb{N}$, then the digit sum $S(n)$ fulfills $S(n)\geq 18$.

It is clear that $9 \mid 99n \Leftrightarrow 9\mid S(99n)$, but I cannot apply the divisibility rule $11 \mid 99n \Leftrightarrow 11\mid S^*(99n)$ of $11$ for the alternating digit sum $S^*$. Please help!

Answer 1

Let the sum of the even-numbered digits, reading from left to right, be $s$ and the sum of the odd-numbered digits be $t$. Since the number is divisible by $9,\space s+t$ is divisible by $9$ and since the number is divisible by $11,\space s-t$ is divisible by $11$. If $s+t=9,$ then we must have $s-t=0$ but that would make $s+t$ even, contradiction.

Answer 2

Suppose that $S(n) = 9$. From the divisibility rule of $11$, we must have(since the ordinary sum is $< 11$)

$$a_0 - a_1 + \ldots + (-1)^k a_k = 0$$

Adding this to

$$a_0 + a_1 + \ldots + a_k = 9m$$

We get

$$2(a_0 + a_2 + \ldots + a_{k \text{ or } k-1}) = 9m$$

Thus, $m$ is even, so let $m = 2k$. We conclude with

$$a_0 + a_1 + \ldots + a_k =18n$$

Contradiction, so $S(n) = 9j$ where $j > 1$.

Answer 3

Assume the claim is false. Then there exist positive multiples of $99$ with digit sum $9$. Let $n$ be minimal with this property. Clearly, $n$ has at least three digits, $n=\overline{a_ka_{k-1}\ldots a_1a_0}$ with $k\ge 2$, $a_i\in\{0,\ldots, 9\}$, $a_k>0$. From the digit sum, we conclude that $a_{k-2}<9$. Then $n-99\cdot 10^{k-2}$ has the same digit sum as $n$ (only $a_k$ is decreased and $a_{k-2}$ increased by $1$), contradicting minimality of $n$.

Answer 4

More broadly, the sum of the digits must be an even number (since divisibility by $9$ tells us that the sum of the digits is a non-zero multiple of $9$ this implies your claim).

To see this, let the digits be $\{a_i\}$. Then, divisibility by $11$ implies that $$\sum (-1)^ia_i=0$$ But then $$N=\sum a_i=\sum (-1)^ia_i+\sum a_i=2\times\left(\sum_{\text {even indices}}a_i\right)$$

Whence $N$ is divisible by $2$ and we are done.

Answer 5

If $99|n$ then $9|n$ and $11|n$.

Two well known rules.

1) If $9|n$ then $9|S(n)$.

So $S(n) = 9, 18,27,.... $ etc. So the the only way $S(n) \ge 18$ can be false is if $S(n) = 9$.

2) If $11|S(n)$ then the sum of the even positioned digits plus the sum of the odd positions digits are either equal, or off by a multiple of $11$.

So if $S_e$ the sum of the even positioned digits and $S_o$ is the sum of the odd positioned digits.

Then $S(n) = S_o + S_e = \begin{cases}2S_o &\text{if } S_o = S_e \\ 2S_o +11k &\text{if } S_e = S_o + 11k\text{ for some }k \ge 1 \\ 2S_e + 11k &\text{if } S_o = S_e + 11k\text{ for some }k \ge 1\end{cases}$

So either $S(n)$ is even. Or $S(n) \ge 11$ And $S(n) = 9,18,27,....$ so $S(n) \ge 18$.

====

Remains to prove those two basic rules.

You've seen proofs a million times, haven't you?

Well, here they are for the million + 1 time:

If $n = \sum\limits_{k=0}^m d_k 10^k$ where $d_k$ are the digits of $n$ then

1) $n = \sum\limits_{k=0}^m d_k (10^k - 1) + \sum\limits_{k=0}^m d_k$

$= \sum\limits_{k=0}^m d_k (10^k - 1) + S(n)$.

Now $10^k -1 = 9999....9$ and is divisible by $9$ so $\sum\limits_{k=0}^m d_k (10^k - 1)$ is divisible by $9$.

[Actually $(a^{k-1} + a^{k-2} + .... + a + 1)(a-1) = a^k - 1$ means $a-1$ always divides $a^k -1$ so $10-1=9$ always divides $10^k -1$; is a more sophisticated proof.]

So $9|n$ if and only if $9|S(n)$.

2) $n = \sum\limits_{k=0}^m d_k 10^k = \sum\limits_{k=0; k\text{ even}}^m d_k 10^k + \sum\limits_{k=0; k\text{ odd}}^m d_k 10^k$

$\sum\limits_{k=0; k\text{ even}}^m d_k (10^k -1) + \sum\limits_{k=0; k\text{ even}}^m d_k + \sum\limits_{k=0; k\text{ odd}}^m d_k (10^k + 1) -\sum\limits_{k=0; k\text{ odd}}^m d_k$

$= \sum\limits_{k=0; k\text{ even}}^m d_k (10^k -1)+ \sum\limits_{k=0; k\text{ odd}}^m d_k (10^k + 1)+S_e - S_o$.

Claim: $11|10^k - 1$ if $k$ is even and $11|10^k + 1$ if $k$ is odd.

If $k$ is even then $(a^{k-1} - a^{k-2} + a^{k-3} -....+a^3-a^2 +a -1)(a + 1) = a^k - 1$ so $a+1|a^k - 1$ if $k$ is even. So $10 + 1 = 11$ divides $10^k-1$ if $k$ is even.

If $k$ is odd then $(a^{k-1} - a^{k-2} + a^{k-3} -.... - a^3 +a^2 -a + 1)(a +1)=a^k + 1$ so $a+1|a^k + 1$ if $k$ is odd. So $10 + 1 = 11$ divides $10^k +1$ if $k$ is odd.

So $11|n$ if and only if $11$ divides $S_e - S_o$. Or in other words if $S_o$ and $S_e$ have a difference of a multiple of $11$.

Answer 6

Each multiple of $99$ has the form $$ 99n=9\cdot 11\cdot n, \, n\in\mathbb{N}. $$ Now for the digit sum $S$ $$ 9\mid 99n \quad \Leftrightarrow \quad 9\mid S(99n) $$ and for the alternating digit sum $S^*$ $$ 11\mid 99n \quad \Leftrightarrow \quad 11\mid S^*(99n). $$ Let $a$ be the sum of the odd digits of $99n$ and $b$ be the sum of the even digits. Then the following must hold in total $$ a+b=9k,\quad a-b=11m, \, m\in\mathbb{N}. $$ It is clear that $0< a,b\leq 9$. The proof is given if $k \neq 1$ is shown, because then $a+b\geq 9\cdot 2=18.$ Assuming that $k=1$ holds, it follows that $$ a=\frac{1}{2}(9+11 m) \quad \text { and } \quad b=\frac{1}{2}(9-11 m). $$ Since $a$ is nonnegative and integer, it just follows $m \geq 1$ from the formula for $a$. Since $b$ is also nonnegative and integer, $m \leq-1$ follows simultaneously from the formula for $b$. However, these two conditions for $m$ are incompatible with each other.