Sum of digits when $99$ divides $n$ Let $n$ be a natural number such that $99\mid n$. Show that $S(n)\ge 18$.
It is clear that $9 \mid S(n)$, but I cannot apply the divisibility rule of $11$. Please help!
 A: 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.
A: 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$.
A: 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$.
A: 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.
A: 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$.
