For those living under the scientist/math/geek/nerd radar, Pi Day is a celebration of the aforementioned famous constant that is hold on 14/03 every year (or as American would put it, 3/14 hence the catch). As always more information on the Wikipedia page.

To celebrate a bit, I rewrote from memory the demonstration I was given once that use congruence to demonstrate the well known division trick that says a number is divisible by 3 if the sum of its digit are also divisible by 3 (or vice versa).

So for instance, we know that 13905 is divisible by 3 because $latex 1 + 3 + 9 + 0 + 5 = 18 = 3 \times 6$. In modular arithmetic terms, we say that $latex 13905 \equiv 0 \mod 3$.

Following is the demonstration in a obfuscated way for a sample 4 digits number (can be generalized to any digit number):

Some more explanations:

  • The basis of the demonstration is to first say that any number is a sum of power of ten. If I take my previous number 13905, I can also say it’s $latex 1 \times 10^4 + 3 \times 10^3 + 9 \times 10^2 + 0 \times 10^1 + 5 \times 10^0$.
  • Then we start our equivalence chain by assuming we have a number n divisible by 3 and then walking our way by taking its power of ten sum representation
  • Due to the fact that 10 has a remainder of 1 when divided by 3 and using the properties of congruence, we reduce our initial expression to only use the initial number digits.
  • Then as the the initial number was divisible by 3, we come to the conclusion that the sum of its digit is also divisible by 3. Plus, since everything was made by equivalence, we know we can go the other way around too

That’s it. You can have a similar reasoning for the other well know multiplication trick that says a number divisible by 5 always ends up with 0 or 5 (this time based on the fact that any power of ten with a power superior to 0 is divisible by 5 and thus has a remainder of 0).