binary representation of integers congruent 1 and 3 modulo 4

Question

Let $k=b_nb_{n-1}\ldots b_3b_2b_1b_0$ be the binary representation of an odd positive integer.

Prove:

If $k\equiv 1 \mod 4$ then $b_1=0$.

If $k\equiv 3 \mod 4$ then $b_1=1$.

I think that to prove the above I need to use $k=1 +4q$ or $k=3 +4q$ for $q\geq 0$. Any suggestions?

Answer 1

Hint

Think of the binary number $k=b_{n}b_{n-1}...b_{2}b_{1}b_{0}$ as $k=b_{0}(1)+b_{1}(2)+b_{2}(4)+b_{3}(8)+b_{4}(16)+b_{5}(32)+...$

If $b_{0}$ and $b_{1}$ are both equal to zero, then every other term in that sum is divisible by $4$.

Answer 2

Consider the value $k' = b_nb_{n-1}b_{n-2}...b_3b_200$. This value is divisible by 4 (specifically, it is $4 \times b_nb_{n-1}b_{n-2}...b_3b_2$), and therefore it is equal to zero, modulo 4.

But $k = k' + b_1b_0$

So

$$k \mod 4 = (k' + b_1b_0) \mod 4$$ $$ = ((k' \mod 4) + (b_1b_0 \mod 4)) \mod 4$$ $$ = (0 + b_1b_0) \mod 4$$ $$ = b_1b_0$$

Now since $k$ is odd, $b_0 = 1$, and the only two possibilities for $b_1b_0$ are $01$ and $11$ (that is, 1 and 3). The result follows immediately.

Answer 3

Thank you for the suggestion. Here is my proof.

If $k=1 +4q$ for some $q>0$, then

$$bin(k)=bin(1)+bin(4)\cdot bin(q)$$

$$b_n b_{n-1}\ldots b_2b_1b_0=001 +100 \times a_ta_{t-1}\ldots a_2a_1a_0$$

$$b_n b_{n-1}\ldots b_2b_1 1=001 + a_ta_{t-1}\ldots a_2a_1a_0 0 0$$

$$b_n b_{n-1}\ldots b_2b_1 1=001 + a_ta_{t-1}\ldots a_2a_1a_0 0 0$$

$$b_n b_{n-1}\ldots b_2b_1 1= a_ta_{t-1}\ldots a_2a_1a_0 0 1$$

Therefore, $b_1=0$.

Similar proof can be obtained for the case $k\equiv 3 \mod 4$.