I'm trying to teach myself some number theory. In my textbook, this proof is given:
Example (2.3.1) Show that an integer is divisible by 3 if and only if the sum of its digits is a multiple of 3.
Let $n=a_0a_1\ldots a_k$ be the decimal representation of an integer $n$. Thus $n=a_k+a_{k-1}10+a_{k-2}10^2+\cdots+a_010^k$ where $0\le a_i<10$ The key observation is that $10\equiv1\pmod3$, i.e., $[10]=[1]$. Hence $[10^i]=[10]^i=[1]$, i.e., $10^i\equiv1\pmod 3$. The assertion is an immediate consequence of this congruence.
I don't understand the last statement. Why does it follow from that congruence?
Best Answer
A simple way to see this (that actually generalizes nicely to Fermat's little theorem):
$$10 - 1 = 9 = 9 \times 1$$ $$100 - 1 = 99 = 9 \times 11$$ $$1000 - 1 = 999 = 9 \times 111$$ In general $$10^n - 1 = 9 \times \underbrace{111...111}_\mbox{$n$ times}.$$ This is just the algebraic identity $$x^n - 1 = (x - 1)(x^{n-1} + x^{n - 2} + ... + x + 1)$$ when $x = 10$. The identity is easy to prove - just multiply it out term by term. All but the first and last terms cancel. Thus any power of $10$ less $1$ is divisible by $9$, and therefore also by $3$.
Now consider a multi-digit natural number, $43617$ for example. $$\begin{align} 43617 &= 4\times 10^4 + 3 \times 10^3 + 6 \times 10^2 + 1 \times 10 + 7 \\ &= 4\times 9999 + 3 \times 999 + 6 \times 99 + 1 \times 9 + (4 + 3 + 6 + 1 + 7) \end{align}$$
Every term on the right other than the sum of the digits is divisible by $3$. So the remainder when dividing the original number by $3$ and the sum of the digits by $3$ must be the same.