# Multiples of $5$ in base $2$

As a follow-up question, what can be said about multiples of $5$ in base 2?

I think I must look at the last two digits, but I am not sure what the whole idea might be.

-

A starting point for a divisibility test (by 5) in binary would be the observation that $2^4\equiv1\pmod5$. Therefore also $2^{4n}\equiv1\pmod5$ for all natural numbers $n$. From that point on it is quite similar to the familiar "casting nines" method of testing divisibility by nine in base 10.

For example: $$110101001000_2=1101_2\cdot(16)^2+0100_2\cdot16^1+1000\equiv 1101_2+0100_2+1000_2=13+4+8=25\equiv0\pmod5.$$

In other words, you study groups of four bits at a time (starting from the least significant), and add the hexadecimal digits formed by these groups together. The result is divisible by five if and only if the original number is.

-
we can further utilize $2^2=4\equiv-1\pmod 5,$ right? –  lab bhattacharjee Feb 24 '13 at 11:50
@lab: Correct, then the algorithm will look like the usual test for divisibility by eleven, IOW we look at an alternating sum. –  Jyrki Lahtonen Feb 24 '13 at 11:52