Highest power of 2

Question

Highest power of two that divided $3^{1024}-1$

I did from binomial and expansion but is there a smarter way ?

My approach : $ 3^{1024}-1 $ can be $(3^{512} + 1)$ and $(3^{512} – 1)$

Again$ ( 3^{512} – 1 )$ is written as $( 3^{256} + 1 )$ and $( 3^{256} – 1)$ Again $( 3^{256} – 1 ) $is written as $( 3^{128} + 1 )$ and $( 3^{128} – 1)$ Again $( 3 ^{128} – 1 )$ is written as $( 3^{64} + 1 )$ and $( 3^{64} – 1)$ Again $( 3^{64} – 1 )$ is written as $( 3^{32} + 1 )$ and $( 3^{32} – 1)$ Again $( 3^{32} – 1 )$ is written as $( 3^{16}+ 1 )$ and $( 3^{16} – 1)$ Again $( 3^{16}– 1 )$ is written as $( 3^{8}+ 1 )$ and $( 3^{8} – 1)$ Again $( 3^(8) – 1 )$ is written as $( 3^{4} + 1 )$ and $( 3^{4}– 1)$ Again $( 3^{4}– 1)$ is written as $(3^{2} + 1)$ and $( 3^{2} – 1)$ Again $( 3^{2} – 1)$ is written as $( 3^{1} + 1 )$ and $( 3^{1} – 1)$ or$ 2^(2) $and$ 2^(1)$

Now it can be observed that each of $( 3^{512} + 1), ( 3^{256} + 1) , ( 3^{128} + 1) , ( 3^{64} + 1) , ( 3^{32} + 1) , (3^{16} + 1) , (3^{8} + 1) , (3^{4} + 1) and ( 3^{2} + 1$is divisible by 2 not $ 2^{2}$. In other words, maximum power of 2 that can divided each of $( 3^{512}+ 1), ( 3^{256}+ 1) , ( 3^{128} + 1) , ( 3^{64}+ 1) , ( 3^{32} + 1) , (3^{16} + 1) , (3^{8} + 1) , (3^{4} + 1) and ( 3^{2} + 1)$ is 1. As they are total 9 terms hence expression is divisible by 2^9 and rest two terms 2^2 and 2^1 will be divisible by 2^3. Hence, maximum power of 2 that can divide 3^(1024) – 1 is 12. $

Answer 1

Using the notation $\{m,p\}$ for the highest power of a prime p dividing m and the "iverson-bracket" ($[n:p]=1$ if p divides n and $[n:p]=0$ if not) we can write:
$$\{3^n-1,2\}=1+ [n:2] + \{n,2\} \tag1 $$ for n=1024 this is $$ \{3^{1024}-1,2\} = 2 + \{1024,2\} = 2+ 10 = 12 $$ The aspect of being "a smarter method" lays in a small framework for the description of the more general problem of composition by primefactors of expressions $f_{b,a}(n)=b^n-a^n$ (for some fixed a and b but dependend on varying n) using the Fermat's/Euler's observations of cyclicityness of the residues modulo some prime p. Then (1) has a form which is pretty general for any base b, a=1 and primefactors p. I've a small treatize on this method in case this is interesting (which I personally find "smarter", so this appears here in an answer to your question).

[added, a neat example]: For instance, that scheme allows iteration; assume that n itself is of the form $n = 3^m - 1$ then $$ \begin{eqnarray} \{3^{3^m-1}-1,2\} &=& \{3^n-1,2\} \\ &=& 1 + [n:2] + \{n,2\} \\ &=& 1+1+(\{3^m-1,2\}) \\ &=& 1+1+(1+ [m:2] + \{m,2\}) \\ &=& 3+ [m:2] + \{m,2\} \end{eqnarray} $$
and in general, for a powertower of height h with topmost coefficient n $$ = 2 h - 1 + [n:2] + \{n,2\} $$ which I find an amazing example of reduction of big numbers ...

Answer 2

Let $2^a||(3^{2^b}-1)\implies 3^{2^b}=1+c2^a$ where $c$ is odd.

$3^{2^{b+1}}=(3^{2^b})^2=(1+c2^a)^2=1+c2^{a+1}+c^22^{2a}=1+c2^{a+1}(1+c2^{a-1})$ if $a>1$

$\implies 2^{a+1}||(3^{2^{b+1}}-1)$

Now, $3^2=1+2^3$ here $a=3,b=1$, i.e, $2^3||(3^{2^1}-1)\implies 2^{k+2}||(3^{2^k}-1)$

Here in this problem, $k=10$