What Is the Largest Natural Number $n$ Such That $2^n$ Divides $3^{2016}-1$?

[anemone]

Here is this week's POTW:

-----

Find the largest natural number $n$ for which $3^{2016}-1$ is divisible by $2^n$.

-----

 

[anemone]

Congratulations to Opalg for his correct solution (Cool) , which you can find below:

Spoiler

$$\begin{aligned}3^{2016} - 1 &= (3^{1008} + 1)(3^{1008} - 1) \\ &= (3^{1008} + 1)(3^{504} + 1)(3^{504} - 1) \\ &= (3^{1008} + 1)(3^{504} + 1)(3^{252} + 1)(3^{252} - 1) \\ &= (3^{1008} + 1)(3^{504} + 1)(3^{252} + 1)(3^{126} + 1)(3^{126} - 1) \\ &= (3^{1008} + 1)(3^{504} + 1)(3^{252} + 1)(3^{126} + 1)(9^{63} - 1) \end{aligned}$$ Expand that last factor binomially: $$\begin{aligned}9^{63} - 1 = (1 + 2^3)^{63} - 1 &= \textstyle{63\choose1}2^3 + {63\choose2}2^6 + \ldots \\ &= 63*2^3 + \{\text{multiples of higher powers of }2\}.\end{aligned}$$ That is an odd multiple of $2^3$, so the highest power of $2$ that divides $9^{63} - 1$ is $2^3$.

Next, if $3^k - 1$ is a multiple of $4$ then $3^k + 1$ will be an odd multiple of $2$. Therefore $2$ is the highest power of $2$ that divides each of $3^{1008} + 1$, $3^{504} + 1$, $3^{252} + 1$ and $3^{126} + 1$. It follows that the highest power of $2$ that divides $3^{2016} - 1$ is $2*2*2*2*2^3 = 2^7 = 128$.