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.

Once upon a time, number theory was both decried and revered as being “pure mathematics” with no practical applications. That is no longer remotely true. There are oblique applications in error correction (e.g. how CDs still play when scratched), but one overwhelming, direct application is in encryption. help me with maths

ReplyDelete