Friday, 26 October 2012

Modular Arithmetic: Rule of 3

Did you know that if a number is divisible by 3 then the sum of its digits are also divisible by 3? Have you ever wondered why? The answer to this problem lies within the field of modular arithmetic.

To begin we need to very precisely decide what our question really is. We start by defining some integer, n, with digits arar-1...a1a0. This then means that: n = a0 + 10a1 + ... + 10r-1ar-1 + 10rar.

In order to proceed with our proof we must first prove a simpler fact, that an - bn 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 an ≡ bn 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 10k ≡ 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 ak - ak (the kkt n minus the same digit) is divisible by 3 too - this means that ak ≡ ak mod 3. Utilising the rules of modular arithmetic we have that 10kak ≡ ak mod 3. It then follows from the additive law that n ≡ (ar + ar-1 + ... + a1 + a0) mod 3.

Therefore if 3|n then (ar + ar-1 + ... + a1 + a0) ≡ 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.

1 comment:

  1. 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