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$?
HINT: Suppose that you have a four-digit number $n$ that is written $abcd$. Then

$$\begin{align*}
n&amp;=10^3a+10^2b+10c+d\\
&amp;=(999+1)a+(99+1)b+(9+1)c+d\\
&amp;=(999a+99b+9c)+(a+b+c+d)\\
&amp;=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.)
This can be easily proven by "Digital Root" concept.

Digital root: A digit obtained by adding digits of number until a single digit is obtained.

All natural number is partitioned into 9 equivalence class by "Digital root".

Any number of Digital root 1 is represented by $1+9\times n$
 any number of Digital root 2 is represented by $2+9\times n$ and so on.

(the reason for writing like this is: 9 is identity in the case of finding digital root)

So a number whose sum is 3. i.e., Digital root is 3 can be written as $3+9*i$.
Which is divisible by 3.(It's clear from this representation).