Number theory proof from AoPS http://www.artofproblemsolving.com/Resources/articles.php?page=htw.readers
In the above link, he gives a problem, namely 

Let $S(n)$ be the sum of the digits of $n$. Find
  $S(S(S(4444^{4444}))).$

Then in the lemma he presents is where I get confused. He states

Every integer $n$, written in decimal notation, is congruent to the sum of its digits modulo $9$.

And he goes on to present the proof. But by the same argument he uses I can also show that it works for mod $8$ as well. Also, how would I represent $18$? $19$?
 A: Let's define a $k$-digit number $n$ to have the decimal (base-10) digits $d_0, d_1, \ldots d_{k-1}$.  We can then write $n$ as:
$$n = 10^0d_0 + 10^1d_1 + \cdots + 10^{k-1}d_{k-1}$$
Note that we can re-arrange this as:
$$\begin{align}
n &= d_0 + 10^1d_1 + \cdots + 10^{k-1}d_{k-1}\\
&= d_0 + (9d_1+d_1) + \cdots + (10^{k-1}-1)d_{k-1} + d_{k-1}\\
&= (d_0 + d_1 + \cdots + d_{k-1}) + \underbrace{(9d_1 + 99d_2 + \cdots (10^{k-1}-1)d_{k-1})}_{\text{all this is a multiple of 9}}
\end{align}$$
Because anything that is a multiple of $9$ is congruent to $0 \pmod{9}$, we have:
$$\begin{align}
n &\equiv (d_0 + d_1 + \cdots + d_{k-1}) + 0 &\pmod{9}\\
&\equiv d_0 + d_1 + \cdots + d_{k-1} &\pmod{9}
\end{align}$$
An example may help.  Let's try $d_0=1, d_1=6,d_2=7,d_3=3,d_4=4$, which makes our $5$-digit number $16734$.  Then, we have:
$$\begin{align}
n &= 1 + 6\cdot10 + 7\cdot10^2 + 3\cdot10^3 + 4\cdot10^4\\
&= 1 + (6 + 6\cdot9) + (7 + 7\cdot99)+(3+3\cdot999) + (4+4\cdot9999)\\
&= (1+6+7+3+4) + (6\cdot9 + 7\cdot99 +3\cdot999+4\cdot9999)\\
&\equiv (1+6+7+3+4) + 0 &\pmod{9}\\
&\equiv 11 &\pmod{9}
\end{align}$$
A: Essentially the same way like anorton's answer, but with a different appearance, we can prove that as follows:
Note that: $$10^n =\displaystyle 9 \times \underbrace{1\cdots 1}_{\text{n times}}+1=\underbrace{9\cdots9}_{\text{n times}}+1$$
Therefore $10^{n} \equiv 1 \pmod{9}$
Now if you expand as $n=a_n10^n + a_{n-1}10^{n-1}+\cdots+a_110+a_0 $ and you calculate modulo $9$ you'll have:
$n \equiv a_n.1+a_{n-1}.1+a_{n-2}+\cdots+a_1.1+a_0 \pmod{9}$
because $\forall n \in \mathbb{N}:10^{n} \equiv 1 \pmod{9}$.
Notice that the same thing is true for modulo $3$ because $10^n \equiv 1 \pmod{3}$.
