Nicer proof that $2^{n+2}$ divides $3^m-1$ if and only if $2^{n}$ divides $m$ (I've accepted Carl's answer because he was first, but robjohn and sirous each gave very nice answers as well.)

I'm interested in the highest power of two that divides $3^m-1$ for even $m \geq 2$. In fact, I can show that this is exactly four times the largest power of two dividing $m$. I.e., $2^{n+2}$ divides $3^m-1$ if and only if $2^{n}$ divides $m$ for $n \geq 1$.
But, my proof seems too tedious for such a nice fact. I've written it up below, but since I want a better proof, you might want to just ignore it. (My motivation comes from finite fields, but the question seems interesting regardless.)

Suppose that $2^{n+2}$ divides $3^m-1$. The proof proceeds in two steps. First, we show that the result holds when $m$ is itself a power of two. I.e., $2^{n+2}$ divides $3^{2^{n'}}-1$ if and only if $n \leq n'$. Next, we show that for any $m$ such that $3^m-1$ is divisible by $2^{n+2}$, we must have $\gcd(m,2^{n}) = 2^{n}$.
For the first part, we observe the factorization
$$
3^{2^{n'}} - 1 = (3^{2^{n'-1}} +1) (3^{2^{n'-2}} + 1) \cdots (3^2+1)(3+1)(3-1)
\;. 
$$
(This is just the factorization of the $2^{n'}$th cyclotomic polynomial and does not use any properties of the number 3.) Since $3^a + 1 = 2 \bmod 4$ for all even $a$, the largest power of two dividing this is exactly $2^{n'+2}$, as needed. (There are $n'+1$ terms, each even. The only term divisible by $4$ is the term $3+1=4$.)
For the second part, we notice that if $2^{n+2}$ divides $3^m-1$, since $2^{n+2}$ also divides $3^{2^{n}} - 1$, $2^{n+2}$ must divide their difference $3^{\min(2^{n},m)}(3^{|m-2^{n}|}-1)$. Since $3^{\min(2^{n},m)}$ is odd, this in turn implies that $3^{|m-2^n|}-1$ is divisible by $2^{n+2}$. We can repeat this procedure many times to simulate the Euclidean algorithm in the exponent, eventually showing that $3^{\gcd(m,2^{n})} - 1 $ is divisible by $2^{n+2}$. Of course, $\gcd(m,2^{n})$ must be a power of two, and therefore the previous argument implies that it $\gcd(m,2^{n}) = 2^{n}$, as needed.
 A: Given a prime $p$ and positive integer $k$, define $\nu_p(k)$ to be the exponent of $p$ in the prime factorization of $k$. We want to show that
$$\nu_2\left(3^n-1\right)=\begin{cases} 1&\mathrm{\ if\ }k\equiv 1\bmod 2\\ 2+\nu_2(n)&\mathrm{otherwise}.\end{cases}$$
We use strong induction to simplify calculations:
If $n$ is odd, then $3^n-1\equiv 2\bmod 4$, so the claim is true. Assume the claim is not true for all even $n$, and consider the smallest such $n=2m$. We have
$$3^{2m}-1=\left(3^m-1\right)\left(3^m+1\right).$$
If $m$ is even, then $\nu_2(3^m-1)=2+\nu_2(m)$ (by our strong inductive hypothesis) and $3^m+1\equiv 2\bmod 4$ so $\nu_2(3^m+1)=1$, which gives
$$\nu_2\left(3^{2m}-1\right)=3+\nu_2(m)$$
as desired. If $m$ is odd then $\nu_2(3^m-1)=1$ and $3^m+1\equiv 4\bmod 8$, so 
$$\nu_2\left(3^{2m}-1\right)=1+2=3=2+\nu_2(2m),$$
as desired.
This isn't really different from your argument, it's just a more compact way of phrasing it. Similar results can be proven for any $p>2$; the most general form that looks nice is that if $p$ is an odd prime so that $p|a-b$ while $p\nmid a,b$, then
$$\nu_p\left(a^n-b^n\right)=\nu_p(a-b)+\nu_p(n).$$
(as user236182 mentioned, this is called Lifting the Exponent).
A: For $k\ge0$ and odd $p$,
$$
3^{p2^k}-1=\left(3^{2^k}-1\right)\overbrace{\left(3^{(p-1)2^k}+3^{(p-2)2^k}+\cdots+1\right)}^\text{$p$ terms}
$$
For $k\ge2$,
$$
3^{2^k}-1=\left(3^{2^{k-1}}-1\right)\overbrace{\left(3^{2^{k-1}}+1\right)}^{2\pmod4}
$$
A: You can use binomial theorem; we may write:
$3^m-1=(4-1)^m-1$
Now if m is even then $3^m-1=(4-1)^m-1=(2^2)^m+M(m,4)$
Where M(m, 4) mean a polynomial having factors m and 4:
$M(m, 4)= (^m_1) 4^{m-1}(-1)^1 + . . .(^m_{m-1}) 4^1 (-1)^{m-1}=4mk$; $k∈   N$ 
Now we must have:
$2^{n+2} | 3^m -1$
Or:
$(2^2)(2^n) | (2^2)^m +M(m, 2^2)$
One common divisor of both sides of this relation is $2^2$, since the least power of $4$ on RHS is 1, then the relation can be reduced to:
$2^n | 2^{m-1}+ k m$
$2^n$ divides $2^{m-1}$ if $m-1>n$.Therefore the condition of holding the relation is if and only if  $2^n |C^m_i $ for $i=1$ to $i=m-1$ or $2^n | m$. 
