Divisible by 3

You probably know the rule of thumb to check if a number is divisible by three: add the digits and see if that number is divisible by three. E.g. 3627 is divisible by three since 3+6+2+7=18, which is divisible by three.

Here is a short proof of this, as well as some extensions. Note that $3627=3*10^3+6*10^2+2*10+7$; if we consider $p(x)=3x^3+6x^2+2x+7$, then $3627=p(10)$. Finding the sum of the digits is equivalent to finding $p(1)$. Our claim is that $p(10)$ is divisible by three if and only if $p(1)$ is divisble by three.

A more general theorem holds, in fact: if $a\equiv b \bmod m$ then $p(a)\equiv p(b) \bmod m$ for any polynomial $p$. A colloquial phrasing is "if a and b have the same remainder after dividing by m, then $p(a)$ and $p(b)$ have the same remainder after dividing by m." In our case, we're just interested in the case where the remainder is zero. The proof of this follows directly from the properties of modular arithmetic, so I won't bore you with it.

Using this theorem, we find that $10\equiv 1 \bmod 3$, so $p(10)\equiv p(1) \bmod 3$, just like we wanted. Note that $10\equiv 1\bmod 9$ as well, so the same "add up the digits" shortcut works with division by 9.

We can extend this to more complicated shortcuts. You might know the trick for divisibility by 11: alternately add and subtract the digits. For example, $1-2+1=0$ so $121$ is divisible by 11.

This is just another instance of our theorem. Since $10\equiv -1 \bmod 11$, $p(10)\equiv p(-1)\bmod 11$ and $p(-1)$ is just alternately adding and subtracting the digits.

Wikipedia has an extensive list of divisibility "shortcuts", some of which seem more complex than just doing long division, but hopefully this illuminates the reasoning behind some of them.