Pattern for all the binary chains divisible by 5

We can use the happy face of five-divisibility!

enter image description here

Start in state $0$. Follow the appropriate arrows as you read digits from your binary number from left-to-right. If you end up in state $0$ again your number is divisible by $5$ (and if not, the state number gives you the remainder).


How does it work? Well if we're in state $k$ it means the digits we have read so far form the number $n$ with remainder $k \equiv n \mod 5$. If we then read another digit $b$, we effectively move to the new number $n' = 2n + b$. Thus we need to move to state $(2k + b) \bmod 5$, which is exactly what we do in the above graph. Thus if we end up in state $0$ in the end we know there is no remainder, and the number that we read is divisible by 5.

The state diagram above is just this logic graphically displayed. You could have it as a table instead as well:

\begin{array}{ccc} k & b & 2k + b & (2k + b) \bmod 5\\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 2 & 2 \\ 1 & 1 & 3 & 3 \\ 2 & 0 & 4 & 4 \\ 2 & 1 & 5 & 0 \\ 3 & 0 & 6 & 1 \\ 3 & 1 & 7 & 2 \\ 4 & 0 & 8 & 3 \\ 4 & 1 & 9 & 4 \\ \hline \end{array}


This also makes for a nice mental rule. You start with the number $0$ in your head and look at the digits from left-to-right. For each digit you multiply the number in your head by 2 and add the digit you just read. If the number goes to five or above you subtract five. If you end up with $0$ the number is divisible by 5.

As an example for the binary number $1111101000_2 = 1000$, you go:

              0 is our starting value
1111101000
^             2*0 + 1 = 1
1111101000
 ^            2*1 + 1 = 3
1111101000
  ^           2*3 + 1 = 7, is >= 5 so we subtract 5
              7 - 5   = 2
1111101000
   ^          2*2 + 1 = 5, is >= 5 so we subtract 5
              5 - 5   = 0
1111101000
    ^         2*0 + 1 = 1
1111101000
     ^        2*1 + 0 = 2
1111101000
      ^       2*2 + 1 = 5, is >= 5 so we subtract 5
              5 - 5   = 0
1111101000
       ^      2*0 + 0 = 0
1111101000
        ^     2*0 + 0 = 0
1111101000
         ^    2*0 + 0 = 0

Our remainder is $0$, thus we are divisible by five!


For example, for $1000$ decimal, represent it as $1111101000$. In base $4$, this is $33220$ (just group pairs of digits together; if there were an odd number of digits then add a $0$ at the front).

Then $3+2+0$ (the sum of the odd-position digits) and $3+2$ (the sum of the even-position digits) are equal, so the number is divisible by 5. This works in general in base $b$ if we are testing for divisibility by $b+1$. To see that, write $$n = \sum_{i=0}^k a_ib^i,$$ where $0\le a_i < b$; then $$(b+1)n = \sum_{i=0}^k a_ib^{i+1} + \sum_{i=0}^k a_ib^i = \sum_{i=1}^{k+1}a_{i-1}b^i + \sum_{i=0}^k a_ib^i = a_0b^0 + \sum_{i=1}^{k-1} (a_{i-1} + a_i)b^i + a_kb^{k+1}.$$ From this it is easy to see that the sum of the odd-position digits and the sum of the even-position digits are equal.