Proof of the divisibility rule for 3

Proof

1. Let $n = \sum_{i=0}^{k} d_i 10^i$ with decimal digits $d_0, \dots, d_k$. Let $S = d_0 + d_1 + \dots + d_k$ be the digit sum.
2. Since $10 - 1 = 9 = 3 \cdot 3$, the number $3$ divides $10 - 1$. So $10 \equiv 1 \pmod 3$ by the definition of congruence.
3. Let $0 \le i \le k$. By step 2 and compatibility with powers, $10^i \equiv 1^i = 1 \pmod 3$.
4. Since $d_i \equiv d_i \pmod 3$, step 3 and compatibility with multiplication give $d_i 10^i \equiv d_i \pmod 3$.
5. Apply compatibility with addition $k$ times to the $k + 1$ congruences of step 4. This gives $n \equiv S \pmod 3$.
6. So there is an integer $t$ with $n - S = 3 t$.
7. If $3 \mid S$, say $S = 3 s$, then $n = S + 3 t = 3 (s + t)$, so $3 \mid n$.
8. If $3 \mid n$, say $n = 3 m$, then $S = n - 3 t = 3 (m - t)$, so $3 \mid S$.
9. By steps 7 and 8, $3 \mid n$ if and only if $3 \mid d_0 + d_1 + \dots + d_k$.