Maximum power of $2$ which divides $3^{1024}-1$

Question

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?

Answer 1

As requested in the comments:

We start by factoring the polynomial $x^{1024}-1$. To do that, we note that $1$ is a root, as is every $2^k-$root of $1$ for $k=0,\cdots 10$. For $k>0$ such a root of unity is also a $2^{k-1}-$st root of $-1$ so our polynomial is divisible by $$(x-1)\times \prod_{k=0}^9(x^{2^k}+1)$$

Comparing the lead terms shows that this is in fact equal to our polynomial.

Now, let $x=3$. We remark that $$3\equiv -1 \pmod 4 \implies 3^{2i}+1\equiv 2 \mod 4$$ so most of the terms in the product are divisible by $2$ but not by $4$. $3-1=2$, of course, and $3+1=4$ is the only term in the product divisible by a higher power of $2$. $(3-1)(3+1)$ then gives us a factor of $2^3$ and the other nine terms in the product each give us exactly one factor of $2$, making the answer $12$ as desired.

Answer 2

Just to give a different approach, since $3^4=81=1+80=1+5\cdot2^4$, we have

$$3^{1024}-1=(1+80)^{256}-1=256\cdot80+{256\choose2}80^2+{256\choose3}80^3+\cdots\\ =2^8(5\cdot2^4)+(2^7\cdot255)(5^2\cdot2^8)+(2^7\cdot85\cdot254)(5^3\cdot2^{12})+\cdots\\ \equiv5\cdot2^{12}\mod2^{13}$$

all terms after the first having higher and higher powers of $2$. Thus $3^{1024}-1$ is divisible by $2^{12}$ but not by $2^{13}$.

Answer 3

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$.

Answer 4

For $n\ge1$, $$ 3^{2^n}-1 =\underbrace{\left(3^{2^0}-1\right)}_2\underbrace{\left(3^{2^0}+1\right)}_4\underbrace{\left(3^{2^1}+1\right)}_{2\bmod4}\underbrace{\left(3^{2^2}+1\right)}_{2\bmod4}\cdots\underbrace{\left(3^{2^{n-1}}+1\right)}_{2\bmod4} $$ Thus, for $n\ge1$, $$ \left.2^{n+2}\,\middle|\,3^{2^n}-1\right. $$ but that $$ \left.2^{n+3}\not\,\middle|\,3^{2^n}-1\right. $$