How to prove the divisibility rule for $3\, $ [casting out threes]

The divisibility rule for $3$ is well-known: if you add up the digits of $n$ and the sum is divisible by $3$, then $n$ is divisible by three. This is quite helpful for determining if really large numbers are multiples of three, because we can recursively apply this rule:

$$1212582439 \rightarrow 37 \rightarrow 10\rightarrow 1 \implies 3\not\mid 1212582439$$ $$124524 \rightarrow 18 \rightarrow 9 \implies 3\mid 124524$$

This works for as many numbers as I've tried. However, I'm not sure how this may be proven. Thus, my question is:

Given a positive integer $n$ and that $3\mid\text{(the sum of the digits of $n$)}$, how may we prove that $3\mid n$?

Solution 1:

HINT: Suppose that you have a four-digit number $n$ that is written $abcd$. Then

$$\begin{align*} n&=10^3a+10^2b+10c+d\\ &=(999+1)a+(99+1)b+(9+1)c+d\\ &=(999a+99b+9c)+(a+b+c+d)\\ &=3(333a+33b+3c)+(a+b+c+d)\;, \end{align*}$$

so when you divide $n$ by $3$, you’ll get

$$333a+33b+3c+\frac{a+b+c+d}3\;.$$

The remainder is clearly going to come from the division $\frac{a+b+c+d}3$, since $333a+33b+3c$ is an integer.

Now generalize: make a similar argument for any number of digits, not just four. (If you know about congruences and modular arithmetic, you can do it very compactly.)

Solution 2:

$\begin{eqnarray} \rm{\bf Hint}\ \ &&\rm3\ \ divides\ \ a\! +\! 10\,b\! +\! 100\, c\! +\! 1000\,d\! + \cdots\\ \iff &&\rm 3\ \ divides\ \ a\! +\! b\! +\! c\! +\! d\! +\! \cdots +\color{#c00}9\,b\! +\! \color{#c00}{99}\,c\! +\! \color{#c00}{999}\,d\! + \cdots\\ \iff &&\rm3\ \ divides\ \ a\! +\! b\! +\! c\! +\! d + \cdots\ \ by\ \ 3\ \ divides\ \ \color{#c00}{9,\ 99,\ 999,\,\ldots}\end{eqnarray}$

Above we used that $\rm\ n + 3m\ $ is divisible by $\rm\,3\iff n\:$ is divisible by $\,3.$