7
$\begingroup$

For instance, $x = 101$ is divisible by $5$ because it is the integer 5. Same thing for $x=1111$ is also divisible by 5 as it is the integer 15. However, $x=1100$ is not divisible by $5$ as it is the integer 12.

Is there a pattern the recognise the binary chains divisible by 5?

$\endgroup$
3
  • 3
    $\begingroup$ Convert the number to base 4 (i.e. look at pairs of digits) and then apply the same divisibility test as the test for divisibility by 11 in base 10 (since $5 = 4+1$, as $11 = 10+1$). $\endgroup$
    – rogerl
    Feb 16, 2021 at 15:21
  • 2
    $\begingroup$ You can multiply the digits with $1,2,-1,-2$ repeatedly from right to left and look at if the sum is divisible by $5$. $\endgroup$
    – Tan
    Feb 16, 2021 at 15:29
  • $\begingroup$ If you want detailed explanation, you can check this answer. $\endgroup$ Jun 13, 2022 at 17:09

4 Answers 4

14
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ If you can make an example, e.g. the integer $1000$, I will accept your answer. $\endgroup$
    – Alex
    Feb 16, 2021 at 16:29
  • $\begingroup$ @Alex Added an example for the binary integer $1000_2 = 8$. $\endgroup$
    – orlp
    Feb 16, 2021 at 16:33
  • $\begingroup$ I meant the integer $1000$, not the binary $1000$ $\endgroup$
    – Alex
    Feb 16, 2021 at 16:37
  • $\begingroup$ @Alex It's a bit laborious but sure. $\endgroup$
    – orlp
    Feb 16, 2021 at 16:37
  • $\begingroup$ Mark Jason Dominus has made similar diagrams for divisibilty of integers written in base 10: blog.plover.com/math/divisibility-by-7.html $\endgroup$ Feb 16, 2021 at 16:44
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

$5 = 2^2 +1$ so whatever rule we can use in base $10$ to tell if a number is divisible by $10^2 + 1 = 101$ should be similar.

But .... consider this.

$2^4 \equiv 1 \pmod 5$

So $2^{4k+1}\equiv 2^1\equiv 2 \pmod 5$.

$2^{4k+2}\equiv 2^2\equiv 4 \equiv -1 \pmod 5$

$2^{4k+3}\equiv 2^3\equiv 8\equiv - 2\pmod 5$

$2^{4k}\equiv 1^k\equiv 1\pmod 5$.

So consider the digits in position. Subtract the digits in the $4k+2$ positions for the one in the $4k$ positions. Subtract the $4^k+3$ from the $4^k+1$ positions. Multiply result from the odd positions by $2$ and add to the even; and mod by $5$.

Example: I'm typing at random: $101110101000111010111$

Group it into four sections:

$\color{blue}1\color{orange}0\color{purple}1\color{red}1\color{blue}1\color{orange}0\color{purple}1\color{red}0\color{blue}1\color{orange}0\color{purple}0\color{red}0\color{blue}1\color{orange}1\color{purple}1\color{red}0\color{blue}1\color{orange}0\color{purple}1\color{red}1\color{blue}1$

The $\color{blue}{4k}$ positions (these are all $\equiv 1\pmod 5$) I count/add: $\color{blue}6$.

In the $\color{purple}{4k+2}$ positions (these are all $\equiv -1\pmod 5$) I count/add $\color{purple}4$. Subtracting I get $6-4\equiv 2\pmod 5$.

In the $\color{red}{4k+1}$ positions (these are all $\equiv 2\pmod 5$) I count: $\color{red}2$.

And int the $\color{orange}{4k+3}$ positions ($\equiv -2\pmod 5$) I get: $\color{orange}1$. Subtracting I get $2-1=1$ which is equiv $1\times 2\equiv 2\pmod 5$.

So multiply tho odd positions by $2$ to get $2$ and add to the even positions of $2$ to get $2+2 = 4$ and I conclude:

$101110101000111010111_2\equiv 4\pmod 5$.

I google for "binary decimal converter" and find this cute little page: https://www.rapidtables.com/convert/number/binary-to-decimal.html

And I see $101110101000111010111_2 = 1528279$ which is $\equiv 4\pmod 5$.

....

This is essentially the "casting out every other digit" rule to determine if a number in base $10$ is divisible by $11$.

.....

To show how quick this can be:

I convert $35765$ to $1000101110110101$ and do

$1000|1011|1011|0101$ and calculate $(3-1) + 2(2-3)=2+(-2)=0$ so it is divisible by $5$.

$\endgroup$
1
$\begingroup$

I use a similar approach to rogerl, but using hexadecimal (base 16), rather than base 4. The divisibility test for 5 in base 16 works like the divisibility test for 3 in base 10, because 3 divides (10-1) and 5 divides (16-1).

The base 16 representation of a positive integer $n$ is of the form $$n = a_0 + a_1\cdot16 + a_2\cdot16^2 + a_3\cdot16^3 + a_4\cdot16^4 + \dots$$ with $0 \le a_i<16$.

But $16\equiv 1 \pmod{15}$, so $$n \equiv a_0 + a_1 + a_2 + a_3 + a_4 + \dots \pmod{15}$$ And because 3 and 5 both divide 15, we also have $$n \equiv a_0 + a_1 + a_2 + a_3 + a_4 + \dots \pmod{3}$$ $$n \equiv a_0 + a_1 + a_2 + a_3 + a_4 + \dots \pmod{5}$$

Thus we can test divisibility by 5 of a hex number by simply adding its hex digits, mod 5. (And of course we can get the hex digits of a binary number by grouping the bits in blocks of 4).

For example, $123_{10}$ is $$0111 1011_2$$ in binary and $$\mathrm{7b}_{16}$$ in hex. The values of those two blocks are $7$ and $11$. $7 + 11 = 18 \equiv 3\pmod{5}$, so $$0111 1011_2$$ leaves a remainder of 3 when divided by 5.

Here are some larger examples.


dec 1000
bin 0011 1110 1000 
val    3   14    8 
sums   3    2    0 mod 5
remainder = 0
    
19136214
0001 0010 0011 1111 1110 1101 0110
   1    2    3   15   14   13    6
   1    3    1    1    0    3    4
remainder 4

Here's a link to a small live Python script which does these calculations.

As I said earlier, you can also use this method for divisibility by 3, just add mod 3 instead of 5. Or add mod 15, and test divisibility by 15, 5, and 3 at the same time.

Note that you can do this test in any order, but if you start from the left, don't forget to pad the bit string with zeroes (if necessary) to make the total number of bits divisible by 4.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .