Show that $3^{-n}$ have the interesting property that one half of their repeating binary string is the inverse of the other.

Question

$3^{-n}$ have the interesting property that one half of their repeating binary string is the inverse of the other. Prove it!

$3^{-1}=\overline{0\color{red}{1}}_2$

$3^{-2}=\overline{000\color{red}{111}}_2$

$3^{-3}=\overline{000010010\color{red}{111101101}}_2$

$\ldots$

These are the binary representations - add a minus sign to the left hand side and the right hand side is the 2-adic representation.

Answer 1

In general, the period of $2$ in $\Bbb Z/(3^{N+1})^\times$ is $2\cdot3^N$. And we expect that the $2$-adic expansion of $-3^{N+1}$ should be purely periodic, period $2\cdot3^N$.

Indeed, since $3^{N+1}|(2^{2\cdot3^N}-1)$, say with quotient $Q_N$, we get the results \begin{align} Q_N&=\frac{2^{2\cdot3^N}-1}{3^{N+1}}\\ -\frac1{3^{N+1}}&=\frac{Q_N}{1-2^{2\cdot3^n}}\,, \end{align}

in which the second line says that the number of binary digits in the repeating block of the $2$-adic expansion of $-3^{-N-1}$ is $2\cdot3^N$, and what’s in the block is the number $q_N$.

What we know is that $2^{2\cdot3^N}-1\equiv0\pmod{3^{N+1}}$, so we can factor $$ \left(2^{3^N}-1\right)\left(2^{3^N}+1\right)\equiv0\pmod{3^{N+1}}\,, $$ but please note that since $3^{N+1}$ is odd, we see that the left-hand factor above is $\equiv1\pmod3$, in particular relatively prime to $3$, and thus to $3^{N+1}$ as well. Thus $3^{N+1}$ divides the right-hand factor, i.e. $3^{N+1}\mid(2^{3^N}+1)$, and once again to make typing easier for myself, I’ll call the quotient $\Omega$. Thus we have: \begin{align} \Omega&=\frac{2^{3^N}+1}{3^{N+1}}\\ 0&<\Omega<2^{3^N}\\ Q_N&=\Omega\left(2^{3^N}-1\right)\\ &=2^{3^N}(\Omega-1)+\left(2^{3^N}-\Omega\right)\\ \text{where we note }0&<2^{3^N}-\Omega<2^{3^N}\,. \end{align}

And that gives us our expression for $Q_N=2^{3^N}a+b$ with both $a$ and $b$ in the interval $\langle0,2^{3^N}\rangle$, namely $a=\Omega-1$ and $b=2^{3^N}-\Omega$. And surenough, $a+b=2^{3^N}-1$, as we desired.

Answer 2

Lemma: For any sequence of $k$ digits $A$, where $B$ is the opposite sequence of digits: $$0.\overline{AB}_2 = \frac{A + 1}{2^k + 1}.$$

Proof: Let $x = 0.\overline{AB}$. Then $$ 2^{k} x = A.\overline{BA}. $$ Therefore, $$ x + 2^k x = A.\overline{11\ldots 1} = A + 1 \quad \implies \quad x = \frac{A + 1}{2^k + 1}. $$

---

So we have to show that $3^{-n} = \frac{1}{3^n}$ has this form, $\frac{A+1}{2^k + 1}$, where $A$ is between $0$ and $2^{k} - 1$. Because $3^{-n}$ is definitely between $0$ and $1$, this is equivalent to just finding $k$ such that $3^n \mid 2^{k} + 1$.

From the pattern in the examples in your question, we guess that we should pick $$ k = 3^{n-1}. $$ So we show by induction that $$ 3^n \mid 2^{3^{n-1}} + 1. $$

Base case: $3^1 \mid 2 + 1 = 3$.

Inductive step: Let's assume that $3^n \mid 2^{3^{n-1}} + 1$, for some $n$. Specifically, let $2^{3^{n-1}} = a \cdot 3^n - 1$. Then \begin{align*} 2^{3^n} + 1 &= \left(2^{3^{n-1}}\right)^3 + 1 \\ &= \left(a \cdot 3^n - 1\right)^3 + 1 \\ &= a^3 3^{3n} - 3 a^2 3^{2n} + 3 a 3^n - 1 + 1 \\ &\equiv 0 - 0 + 0 - 1 + 1 \pmod{3^{n+1}} \\ &= 0. \end{align*} So $2^{3^n} + 1$ is divisible by $3^{n+1}$, and the induction is complete.