Find all natural numbers $n$ such that $2^n$ divides $3^n -1$

Well $3^n - 1 = (3-1)(1 + 3 + 3^2 + ... + 3^{n-1}) = 2(1 + 3 + 3^2 + ... + 3^{n-1})$

So $2^n|3^n - 1$ if and only if $2^{n-1}|(1 + 3 + 3^2 + ... + 3^{n-1})$.

If $n$ is odd and greater than one $(1+3 + 3^2 + .... + 3^{n-1})$ is odd so we can assume $n$ is even.

Let $n = 2m$ then $2^{2m}|3^{2m} - 1=(3^m -1)(3^m+1)$. So $3^m \pm 1$ are both even and only one of them is is divisible by $4$.

So $2^{2m-1}|3^m \pm 1$ so $2^{2m-1} \le 3^m \pm 1$.

But $2^{2m-1} = \frac 12*4^{m} \le 3^m \pm 1$

So $(\frac 43)^m \le 2 \pm \frac 2{3^m} < 2\frac 23$

If $m \ge 3$ then $(\frac 43)^m \ge 2 \frac {10}{27} > 2 \frac 2{3^3}\ge 2 + \frac 2{3^m}$

So $m < 3$

So if $n > 1$ then $n= 2m; m\le 2$.

So solutions must be a subset of $\{0,1,2,4\}$.

And you have already determined that $\{0,1,2,4\}$ are all solutions.

====

There's probably a more elegant way.

My first thought was FTL that as $\gcd(3, 2^n) = 1$ and $\phi(2^n) = 2^{n-1}$ then $3^{2^{n-1}}\equiv 1 \mod 2^n$. So

If $3^m \equiv 1 \mod 2^n$ then $m$ is a multiple of a non-trivial factor of $2^{n-1}$ .i.e. even

but that didn't really get me closer.

Likewise $3^n = (2 + 1)^n = 2^n + \sum{n\choose k} 2^k$ and for $2^n|\sum{n\choose k} 2^k$ seemed like it should yeild something relevent but I wasn't able to put my finger on it exactly.

Similarly $3^n = (4 -1)^n$.

Its a enough to convince me the answers are related to powers of $2$ but not enough to actually prove it.