 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  How high? (Posted on 2014-03-25) What is the highest power of 2 that divides 32048-1 ?

 No Solution Yet Submitted by Ady TZIDON Rating: 4.0000 (2 votes) Comments: ( Back to comment list | You must be logged in to post comments.) Recursive Proof | Comment 3 of 4 | observe
3^2 - 1 = 8 = 2^3
3^4 - 1 = 80 = 5*2^4
3^8 - 1 = 6560 = 205*2^5
conjecture if n≥1, the highest power of 2 that divides 3^(2^n) is n+2
Recursive proof:

Assume for n
3^(2^n)-1=2^(n+2)*C
Square both sides
(3^(2^n)-1)^2=(2^(n+2)*C)^2

3^(2^(n+1)) - 2*3^(2^n) + 1 = 2^(2n+4)*C^2
3^(2^(n+1)) - 1 = 2^(2n+4)*C^2 +2*3^(2^n) - 2
= 2[2^(2n+3)*C^2 + 3^(2^n) - 1]
= 2[2^(2n+3)*C^2 + 2^(n+2)*C]
= 2[2^(n+2)*C(2^(n+1)*C + 1)]

On the LHS the n was increased to n+1, on the RHS the greatest factor of 2 is 2^(n+3)
So we have shown if the pattern works for n, it works for n+1

***I forgot to mention in the above that C is odd.
I also forgot the solution:
Since 2048=2^11, n=11 the greatest power of 2 is n+2=13

Edited on March 25, 2014, 12:07 pm
 Posted by Jer on 2014-03-25 12:03:38 Please log in:

 Search: Search body:
Forums (0)