Using mathematical induction to prove divisibility of a number and its binary reverse by 3.

Question

Prove using Mathematical induction that, For any given number $X$ : $X$ is divisible by 3 if and only if $r(X)$ is divisible by 3. where $r(X)$ is value of the reverse of $X$ treated as a binary string (with no leading zeroes)

e.g. if $X$ is 10 (decimal) i.e. 1010 (binary) then $r(X)$ is 0101 (binary) i.e. 5 (decimal)

e.g. if $X$ is 19 (decimal) i.e. 10011(binary) then $r(X)$ is 11001 (binary) i.e. 25 (decimal)

[$Note:$ Binary string of $X$ cannot have leading zeroes. So all the zeroes, if any, are truncated before reversing the binary string.]

I tried doing it(inducting on the bit length of binary of $X$) but in the case when $X_k$ $mod$ 3 = $1$ and $X_{k+1}$ = $X_k1$, I got stuck because $r(X_{k+1})$ = $1r(X_k)$ = $2^k$ + $r(X_k)$ and since $X_{k+1}$ = $2X_k$ + $1$ $\implies X_{k+1}$ $mod$ 3 = $0$ $i.e.$ I need to prove that $r(X_{k+1})$ is also divisible by 3 which I can't(I have tried taking two cases for k being even and odd but that didn't work).

Please help!

Answer 1

If you are familiar with the divisibility test for $11$ in base $10$, then we can build on that.

Let $X$ have binary expansion $\sum_{k=1}^n b_k2^k.$ Since $2\equiv -1 \pmod{3},$, we have

$$X \equiv \sum_{k=1}^n b_k(-1)^k \pmod{3}.$$

So a test for divisibility by $3$ is to find the alternating sum of the digits. If that alternating sum is $0 \pmod{3}$, then so is the alternating sum of the digits of the reverse, eh?

It doesn't use induction, unless you use induction to prove the divisibility test, so maybe this isn't what you're looking for.

Answer 2

I suggest proving something slightly stronger—namely, that $r(X_k) \equiv X_k \pmod 3$ when $k$ is odd, while $r(X_k) \equiv -X_k \pmod 3$ when $k$ is even. (This is closely related to the divisibility test described in B. Goddard's answer.) This includes your desired equivalence as a special case, and I think the inductive step will be more evident to you.

(By the way, nothing changes in this problem even if we assume that integers can have leading zeros.)

Answer 3

Let the binary representation of your number be $ab$ and its reverse is $ba$

Then these two numbers in decimal are $a+2b$ and $b+2a$ which are congruent to $a-b$ and $b-a$, $\mod (3)$ respectively.

For the case of $abc$ and $cba$, we get $a+2b+4c$ and $c+2b+4a$ which are congruent to $a-b+c$ and $c-b+a$ $ \mod (3)$, respectively.

Since powers of $2$ are congruent $\pm 1$, $ \mod (3)$ the decimal values of a binary number and its revers are either identical or opposite $\mod (3)$.

Thus if one is a multiple of $3$, the other is also a multiple of $3$