# Highest power of 2

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. $- And where did you use the binomial ? – Belgi Oct 4 '12 at 9:57$3^{2^n } \equiv 1 \ \ \ (2^{n+1})$– PAD Oct 4 '12 at 10:10 This was another approach binomial was other – Arpit Bajpai Oct 4 '12 at 10:25 But from this explanation n = 11 – Arpit Bajpai Oct 4 '12 at 10:26 This explanation says that$2^{11}$divides the expression. It does not prove that it is the highest such power. – PAD Oct 4 '12 at 11:10 ## 2 Answers 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 ... - Interesting method! – PAD Oct 4 '12 at 13:44 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\$

-
Elegant solution! +1 – RFZ Jun 20 at 16:38