All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
How high? (Posted on 2014-03-25) Difficulty: 2 of 5
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.)
Solution 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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information