0
$\begingroup$

I was reading about how to know if a number is divisible by 3 given binary representation of the number.

After googling a bit I read a statement and I am puzzled how is this correct.

we have to just count the number of 1's (set bits) at even position and number of 1's (set bits) at the odd positions. If the difference is divisible by 3, the number is divisible by 3.

Can anyone please help in understanding the logic behind this.

$\endgroup$
1
$\begingroup$

If we start counting from $0$ the bits in even position are worth $1,4,16,\ldots 2^{2k}$. When you divide any of these by $3$ you leave a remainder $1$. The bits in odd position are worth $2,8,32,\ldots 2^{2k+1}$. When you divide any of these by $3$ you leave a remainder of $2$ or, equivalently, $-1$. The remainder of dividing by $3$ is then the number of bits in even position minus the number of bits in odd position.

$\endgroup$
1
$\begingroup$

Hint: Look at the powers of $2$ modulo $3$. They are alternately $1$ and $-1$. Now write out the binary expansion as a sum of powers of $2$ and reduce modulo $3$.

This is just the base $2$ version of the well known divisibility test for $11$ when writing numbers in base $10$.

$\endgroup$
1
$\begingroup$

That's because $2^n\equiv-1\pmod3$ if $n$ is odd and $2^n\equiv1\pmod3$ otherwise. So, if $a=2^{n_1}+\cdots+2^{n_k}+2^{m_1}+\cdots+2^{m_l}$, $n_1,\ldots,n_l$ even and $m_1,\ldots,m_l$ odd, then$$a\equiv\overbrace{1+1+\cdots+1}^{k\text{ times}}+\overbrace{(-1)+(-1)+\cdots+(-1)}^{l\text{ times}}\pmod3.$$In other words, $a\equiv k-l\pmod3$.

$\endgroup$
  • 1
    $\begingroup$ @hardmath Done, but I don't think anyone will find it interesting. $\endgroup$ – José Carlos Santos Apr 8 '18 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.