*To test the divisibility of a number N by 3, recursively sum the digits that make up the number till you reach a manageable number whose divisibility of 3 can be inferred trivially.*

For example if we're testing the divisibility of $3423$ by $3$. We'll add up $3+4+2+3$ and get $12$. We know that $12$ is divisible by $3$, hence the number $3423$ is divisible by $3$ (If we did not know that $12$ was divisible by $3$ we would have summed up the digits of $12$ and so on).

### Proof for theorem:

The main crux of the proof is representing the number as a specific set of additions and multiplications and your work is almost done. If we have a number $N$ with $n$ digits $a_{1}a_{2} \ldots a_{n}$, then the number N can also be represented as follows

\[N = a_1 \cdot 10^{n-1} + a_2 \cdot 10^{n-2} + ... + a_n \cdot 1\]

With out proof in mind let's separate the sum of all the digits of $N$ i.e, $a_1 + a_2 + \ldots + a_n$ and see what we get.

\[N = \left(\underbrace{99\ldots9}_{n\text{-times}} \cdot a_1 + \underbrace{99\ldots9}_{n-1\text{-times}} \cdot a_2 + \ldots 9 \cdot a_{n-1} \right) + \left( a_1 + a_2 + \ldots + a_n \right)\]

Now if we can prove that the right glob we have here is divisible by 3 then our job is done (We'll know that the if the sum of its digits is divisible by $3$ then $N$ is divisible by $3$).

### Corollary #1:

*A number with just 9 as its digits is divisble by 3*

### Proof for Corollary #1:

We know that any number which is divisible by 9 is divisible by 3 as well $\left(3 * 3 = 9\right)$. So a number $M$ which has $m$ digits in it and all $m$ digits are 9 can be represented as

\[ \underbrace{99\ldots9}_{m\text{-times}} = 9 \cdot 10^{m-1} + 9 \cdot 10^{m-2} + ... + 9\]

On further simplification we get

\[ \underbrace{99\ldots9}_{m\text{-times}} = 9 \left(10^{m-1} + 10^{m-2} + ... + 1\right) \]

The above proves the corollary. With the corollary proven we can concur that the sum of the digits of a number should also be divisible by $3$ if a number is divisible by $3$ and vice versa.

**Acknowledgement:**I first saw this proof on the One Mathematical Cat website, but the instructor just proved it for a specific case of 3 digits. This was my effort in generalizing the proof for any arbitrary number of digits.