<s>[INST] Maximum power of $2$ which divides $3^{1024}-1$ What is the maximum power of $2$ which completely divides $3^{1024}-1$?
I proceeded thus:
$\phi(2^n)=2^{n-1}$ for all $n\ge1$
$$3^{1024}=3^{2^{10}}\equiv1\pmod {2^{11}}$$
$$3^{1024}-1\equiv0\pmod {2^{11}}$$
Since $\phi(2^{11})=2^{10}$.  So, maximum power of $2$ must be $11$.
But the answer says it is $12$.
Where am I wrong and how to solve it correctly? 
 [/INST] If $2^n$ divides $3^{1024}-1$, then $3$ has order at most $1024=2^{10}$, mod $2^n$.
Now, $3$ has order $2^{n-2}$ mod $2^n$. (*)
So, $n-2=10$ is the maximum possible, that is, $n=12$.
(*) By induction, $3^{2^{n-3}} \equiv 1+2^{n-1} \bmod 2^n$ and $3^{2^{n-2}} \equiv 1 \bmod 2^n$ for $n\ge 4$.
</s>