The Rule of Three or More

I remember learning as a kid, that if a number is divisible by three, then the sum of the digits must be divisible by three. Ever wondered how this rule works and how someone must have discovered it. The proof is really simple and franckly quite amazing. I have been wanting to share it for a long long time now.

Well, lets use this theorem with b=3. Lets take a number 'a' for which we need to figure out divisibility by 3. Lets take an example, say 1021. We can rewrite 1021 as 1x1000+0x100+2x10+1.

Now try using mod 3 for the numbers above (Use Fermat's Little Theorem if you have to - more on that in the blogs to follow).

Any power of 10 mod 3 is 1. 10 mod 3 = 1, 100 mod 3 = 10 mod 3 x 10 mod 3 = 1 x 1 = 1. Thats a simple proof - right?

Now, in our example

1021 mod 3 = 1 mod 3 + 0 mod 3 + 2 mod 3 + 1 mod 3 (remember all powers of 10 mod 3 is 1, hence we are reduced to multiplying the digits with 1)

This is further equal to (1+0+2+1) mod 3 == 1 (Thanks Vinay!).

The proof should be trivial to extend to any generic number, by splitting it into powers of 10 and the digits and summing them up. All powers of 10 mod 3 yeild one, hence we need to use only the sum of the digits mod 3.