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 a_ra_r-1...a₁a₀. This then means that: n = a₀ + 10a₁ + ... + 10^r-1a_r-1 + 10^ra_r.

In order to proceed with our proof we must first prove a simpler fact, that aⁿ - bⁿ 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ⁿ ≡ bⁿ 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^ka_k ≡ a_k mod 3. It then follows from the additive law that n ≡ (a_r + a_r-1 + ... + a₁ + a₀) mod 3.

Therefore if 3|n then (a_r + a_r-1 + ... + a₁ + a₀) ≡ 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.