Binary Representation of 3 to some Power of 2

140 Views Asked by At

I believe the following is a well-known result.

The lowest ($i+3$) bits in the binary representation of $3^{2^i}$ ($i>0$) has the form "$10..01$", namely, all bits are zeros except the first and the last in the lowest ($i+3$) bits.

For example, the lowest 6 bits of $3^{2^3}$, which is $3^8$, is "$100001$". I have computed numerically, up to $i = 20$, to verify this result.

When I was trying to understand why this is true, I found this is not obvious. I have tried using Lucas's theorem, such as the following form.

$$3^{2^i} = \sum_{j=0}^{p}{d_j2^j} =\sum_{j = 0}^{p}{\left[{3^{2^i} \choose 2^j}\mod{2}\right]2^j}$$

For $j = 0$, $\left[{3^{2^i} \choose 2^j}\mod{2}\right]$ is 1, which says $3^{2^i}$ is odd. However, for $0 \lt j \le (i+3)$, the result doesn't seem to be obvious.

How do I prove this result?