Digit-sum test for divisibility by 9 (and 3)

Step 1. Show by induction that $10^i \equiv 1 \pmod 9$ for every $i\ge0$. Base case $i=0$: $10^0=1\equiv1\pmod9$. Inductive step: if $10^i\equiv1\pmod9$, then $10^{i+1}=10\cdot10^i\equiv10\cdot1=10\equiv1\pmod9$ (using $10 \equiv 1 \pmod 9$). So $10^i\equiv1\pmod9$ for all $i$.

Step 2. Substitute into the place-value expansion: $n=\sum_i d_i 10^i \equiv \sum_i d_i\cdot1 = \sum_i d_i \pmod9$. So $n$ and its digit sum always leave the same remainder upon division by $9$.

Step 3. Conclude: $9\mid n$ exactly when $n\equiv0\pmod9$, which by Step 2 happens exactly when $\sum_i d_i\equiv0\pmod9$, i.e. exactly when $9$ divides the digit sum. Since $9=3\times3$ and the same congruence $10\equiv1\pmod3$ also holds, the identical argument with $3$ in place of $9$ throughout proves the divisibility-by-$3$ version.