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

I think that the only solutions are $n = 0,1,2,4$, but I have no idea on how to prove it.
I tried to write $3^n-1$ as $1+3+3^2+...+3^{n-1}$ and manipulate the sum but found my self at the equally hard problem of finding the power of two dividing $3^k+1$
 A: 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.
A: The result is clear for $n = 0$. For $ n = 1, 2, 3 \ldots$ let the highest power of $2$ that divides $3^n - 1$ be $2^{p(n)}$. If $n$ is odd, say $n = 2m + 1$, then $3^n - 1 = (3 - 1)(3^{2m} + 3^{2m - 1} + \cdots + 1)$. The sum has an odd number of terms, so $p(n) = 1$. If $n$ is even, say $n = 2m$, then $3^n - 1 = (3^m - 1)(3^m + 1)$. By induction, $3^m \equiv 1 \mod 8$ if $m$ is even and $3^m \equiv 3 \mod 8$ if $m$ is odd. Hence $p(2m) = p(m) + 1$ if $m$ is even, $p(m) + 2$ if m is odd. By applying this repeatedly we get that if $n = 2^ab$, where $a > 0$ and $b$ is odd, then $p(n) = a + 2$. It follows easily that for $n > 0$ we have $p(n) \ge n$ iff $n = 1, 2, 4$.
A: Let $\nu_2(n)=\max\{m\in\mathbb{N}: 2^m\mid n\}$. We may tackle the given problem by finding an explicit form  for (or, at least, an explicit recursive algorithm for the determination of) $\nu_2(3^n-1)$. By letting $a_n=3^n-1$ we have 
$$ a_{2k+1} = 3\cdot 9^k-1\equiv 2\pmod{8}$$
from which $\nu_2(a_{2k+1})=1$, and
$$ a_{2k} = a_k (3^k+1) $$
from which $\nu_2(a_{2k})=\nu_2(a_k)+\nu_2(3^k+1)$. On the other hand
$$ 3^{2m+1}+1 = 3\cdot 9^m+1 \equiv 4\pmod{8} $$
$$ 3^{2m}+1 = 9^m+1\equiv 2\pmod{8} $$
so $\nu_2(3^{2m+1}+1)=2$ and $\nu_2(3^{2m}+1)=1$.  In particular
$$ \nu_2(a_n) \leq 1+2\log_2(n) $$
and the only solutions of $2^n\mid (3^n-1)$ are associated to $n\leq 7$, hence they can be found by direct inspection. In explicit terms,
$$ \nu_2(a_n) = 2+\nu_2(n)-\mathbb{1}_{\text{odd}}(n).$$
A: I write this with two ad-hoc invented notations:


*

*define $[n:m]=1$ if $m|n \qquad$ and $[n:m]=0$ if $m\not |n \qquad$              ("Iverson-brackets")

*define $\{n,m\} = A $ if $n$ contains $m$ to the power of $A$; or "$n=x \cdot m^A$" (or "valuation" $v_m(n)$)


Evaluating Fermat's little theorem and Euler's totient theorem and the concept of "order of cyclic subgroups modulo prime" we can find:
 $$ A=\{3^n -1,2\} = 1 + [n:2] + \{ n:2 \} $$ 
which means also, that $A$ is logarithmic in $n$ and the number of solutions must be finite and occur in small $A$ and $n$. 
Actual enumeration of small cases gives
$$ \begin{array}{rr|l}
 n & 3^n-1 & A & (=1+ [n:2] + \{n,2\} ) \\ \hline 
 0 & 0 & \;^\dagger & \;^\dagger  \\
 1 & 2 & 1 &  1 + 0 + 0 \\
 2 & 8 & 3 &  1 + 1 + 1 \\
 3 & 26 & 1 &  1 + 0 + 0 \\
 4 & 80 & 4 &  1 + 1 + 2 \\
 5 & 242 & 1 &  1 + 0 + 0 \\
 6 & 728 & 3 &  1 + 1 + 1 \\
 \vdots \\
\end{array}$$
( $\;^\dagger$: this is not defined here and might be assumed zero or infinite)
From $n=5$ the smaller increase in $A$ than that of $n$ comes into account  and thus no more equality $A=n$ can occur.             
(For a more explicite discussion see a short text of mine)
