I always find myself doing tests with binary numbers (without a calculator, I'm now developing automatas) and I've always asked myself if there was a fast trick to check whether a generic number is divisible by another binary number.
Let's say I need to test if 100111011 is divisible by 3 or by 11, is there a "common" way to deal with these kind of problems? Or checking one by one is the only possible way to do it?
I know that to check if a number is divisible by 3 you have to look for a certain thing, by 11 you have to look for some other things, is that really the fastest and easiest way?
Best Answer
I'm going to start with an example for how to derive divisibility rules for base 10 first because I feel it's easier to understand. Suppose we have $n$ which is divisible by $7$ and we want to prove it, write it in the form $n=10k+j$ so $j$. Notice that $j$ is the last digit in the decimal expansion. Now here's the trick, because $7\vert n$ we know $7\vert (n-21j)$ so $7\vert 10(k-2j)$. $10$ and $7$ are relatively prime so we get that $7\vert (k-2j)$. Put in words we can take the last digit from $n$ and subtract twice the quantity from the rest of the digits of $n$ then our new number is divisible by 7 if and only if $n$ was. For example let's check $252$: $$252 \to 25 - 2 \times 2 = 21 \to 2 - 2 \times 1 = 0.$$ Note that you don't have to reach $0$, we could have stopped at $21$ if we recognized it's divisible by $7$.
Now we can use the same trick to come up with divisibility rules for base 2. Write $n$ in the form $$n=2k+j$$ and assume $3\vert n$. Now we have $n-3j=2(k-j)$ which is also divisible by 3, so $3\vert (k-j)$. This rule is really nice because it ends up being reduced to the alternating sum. So if the alternating sum of the binary expansion of $n$ is divisible by 3 then $n$ is. For example let's check $228;11100100$ $$ \matrix{+&-&+&-&+&-&+&-\\1&1&1&0&0&1&0&0\\ \hline \\1&-1&+1 & & & -1 & & & =0} $$ So we see $228$ is divisible by $3$.
For divisibility by $11$ we write $n+11j=2(k+6j)$ so $11\vert(k+6j)$ if $11\vert n$. The most efficient way I can come up with to use this is to take the binary expansion of $n$, cut off all trailing $0$s and the last $1$ and add $110$ ($6$). For example $2992;101110110000$, I put vertical bars to show where I cut the number off: $$1011101\vert10000\to 1011101+110=110001\vert 1\to 110001+110=11011\vert 1 \to$$ $$11011+110=10000\vert 1\to 10000+110=101\vert 10\to 101+110=1011$$ We reached the binary expansion for $11$ so we have shown $2992$ to be divisible by 11.
Other rules can be derived using the same trick.