Find n such that $2^{n} \equiv x\mod 3^{k}$

Question

It looks like for every $k \ge 1$ and x is not a multiple of 3, $2^{n} \equiv x\mod 3^{k}$ as a unique solution (modulo $2 \times 3^{k-1}$).

How to prove it? How to find such n given k and x?

Thanks.

Answer 1

You need to show that $2^{2*3^{k-1}}\ne1\pmod{3^{k+1}}$. That follows by induction by cubing $1+3^{k-1}+m*3^k\pmod{3^{k+1}}$.
To find $n$, write $x$ in base $3$. First, $n=0$ or $1$ depending on $x\pmod3$. Then add $0,2$ or $4$ to $n$ so that $2^n=x\pmod 9$; add $0,6$ or $12$ to get it correct mod $27$, and so on.