<s>[INST] Determine whether or not a binary number is divisible by $3$ Let $K$ be a natural number with $n$ binary digits.
Is there an $O(n)$ method for deciding whether or not $K$ is divisible by $3$?
$3|K \iff d_1-d_2+d_3-d_4\dots\pm d_n=0$ works correctly up to $20$, but fails for $21$.
 [/INST] Another way to prove the accepted answer without using the congruence relation. First, note that we have:
$$
\frac{1}{3} \text{ = } 0+\frac{1}{3} \\ 
\frac{2}{3} \text{ = } 1-\frac{1}{3} \\
\frac{4}{3} \text{ = } 1+\frac{1}{3} \\
\frac{8}{3} \text{ = } 3-\frac{1}{3} \\ 
\\ \vdots
$$ And, generally:
$$
\frac{2^k}{3}= \begin{cases}
  p - \frac{1}{3} & \text{if } k \text{ is odd}  \\
  q + \frac{1}{3} & \text{if } k \text{ is even} .
\end{cases}
$$
Where $p$ and $q$ are some integers. It can be proved using induction. In order to check whether a binary integer $N$ with $n$ digits is divisble by $3$ we can write $\frac{N}{3}$ as follows:
$$
\begin{split}
\frac{N}{3} = \frac{\sum_{i=0}^{n-1}b_{i}2^{i}}{3} = (\frac{2^0}{3}b_0+\frac{2^2}{3}b_2+\frac{2^4}{3}b_4+\ldots+\frac{2^{2r}}{3}b_{2r}) \\
+ (\frac{2^1}{3}b_1+\frac{2^3}{3}b_3+\frac{2^5}{3}b_5+\ldots+\frac{2^{2s-1}}{3}b_{2s-1}).
\end{split}
$$
Where $r= \left \lfloor \frac{n-1}{2} \right \rfloor$, $s=\left \lfloor \frac{n}{2}  \right \rfloor$. Now replacing the $\frac{2^k}{3}$ terms yields:
$$
\begin{align}
\frac{N}{3} & = ((q_0+\frac{1}{3})b_0+(q_2+\frac{1}{3})b_2+\ldots+(q_{2r}+\frac{1}{3})b_{2r})
\\ & \quad + ((p_1-\frac{1}{3})b_1+(p_3-\frac{1}{3})b_3+\ldots+(p_{2s-1}-\frac{1}{3})b_{2s-1}) \\
& = l + \frac{b_0-b_1+b_2-b_3+\ldots+(-1)^{n-1}b_{n-1}}{3}.
\end{align}
$$
Where $l$ is the sum of $p_ib_i$s and $q_ib_i$s and is already an integer. So in order for $N$ to be divisible by $3$ (i.e., the quotient to be an integer), $b_0-b_1+b_2-b_3+\ldots+(-1)^{n-1}b_{n-1}$ must be divisible by $3$.
</s>