Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 2

up vote 2 down vote accepted

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

share|improve this answer
    
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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.