To begin we need to very precisely decide what our question really is. We start by defining some integer, n, with digits a

_{r}a

_{r-1}...a

_{1}a

_{0}. This then means that: n = a

_{0}+ 10a

_{1}+ ... + 10

^{r-1}a

_{r-1}+ 10

^{r}a

_{r}.

In order to proceed with our proof we must first prove a simpler fact, that a

^{n}- b

^{n}is always divisible by a - b. We will use induction to prove this lemma.

What this lemma means is that if a ≡ b mod m that a

^{n}≡ b

^{n}mod m, for any integer n, too. With this fact ready we can now proceed with our proof.

It is clear that 10 ≡ 1 mod 3 (10 - 1 can be perfectly divided by 3), utilising our lemma it is clear that 10

^{k}≡ 1 mod 3. If a ≡ b mod m and c ≡ d mod m then ac ≡ bd mod m (the multiplicative law) and that (a + c) ≡ (b + d) mod m (the additive law), read the proofs here.

0 is obviously divisible by 3, hence a

_{k}- a

_{k}(the k

^{kt}n minus the same digit) is divisible by 3 too - this means that a

_{k}≡ a

_{k}mod 3. Utilising the rules of modular arithmetic we have that 10

^{k}a

_{k}≡ a

_{k}mod 3. It then follows from the additive law that n ≡ (a

_{r}+ a

_{r-1}+ ... + a

_{1}+ a

_{0}) mod 3.

Therefore if 3|n then (a

_{r}+ a

_{r-1}+ ... + a

_{1}+ a

_{0}) ≡ 0 mod 3, or in English, the sum of the digits of a number that is divisible by 3 will also be divisible by 3. The rule of 3 is proven.

There are also similar laws for division by 9 and 11 but I will leave these proofs up to the reader of this post, you use the exact same techniques and facts as I have used here. Leave any comments on any problems (or successes!) you have with this.