What is the highest power of 2 that divides 3²⁰⁴⁸-1 ?

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