Proving that (2^n) - 1 is Not Prime for Perfect Squares

[mae]

Prove that if n is a perfect square, then (2^n) -1 is not prime.

All I can get is that 2^n is some even number. I can't work in the perfect square part.

 

[NateTG]

Well, you could try a couple and see ...
2^4-1=15=3*5
2^9-1=511=7*73
2^16-1=323767=7*31*151

You could at least write the expression as:
2^{k \times k}-1

There's an easy answer when k is even.

 

[mae]

Unfortunately I have to prove it for every perfect square, and there are a lot of them.

I feel like I've tried everything. The last thing I tried was contrapositive : If (2^n)-1 is prime, then n is not a perfect square. No dice... at least for me.

 

[morphism]

You could write it as (2^k)^k - 1. Can you think of a way to factorize it now?

By the way, primes of the form 2^n - 1 are called Mersenne primes. They're relatively well-known, and have many unsolved problems associated to them. For example, are there infinitely many Mersenne primes?

 

[mae]

*sigh* honestly I can't think of a way to factor it =(

I've been up all night and I can't really think straight anymore. I'm not sure that would help anyway though.

 

[qspeechc]

Just some thoughts, btw I know zero number theory.

n = k^2
It is true for k=1, k=2. Assume it is true for some k. So 2^(k^2)-1 is not prime
For the next number k+1, n = k^2 + 2k +1, we have:

2^n - 1= 2^(k^2 + 2k +1) - 1 = 2^(k^2) + 2^(2k) + 1 = 2^n -1 + 2^(2k) +2

Er, then, I don't know what.

 

[mae]

Good ol' induction... I didn't try that before. But I took what you started and didn't really end up anywhere... just like everything else I've tried =( Thanks for the thought though.

 

[mae]

And I apologize for not showing my work, but most (nearly all) of it has been erased at this point, and it all was deadends. Thanks for your help guys. I'll let you know if/when I get an answer. Or you could put me at peace before that.

 

[mae]

Holy crap, I think I just got it.

Edit: I did not.


This is for contrapositive, which seems more promising.
I have 2^n -1 = p (some prime)
so... 2^n = p+1 (some even)
now, if only log[2](p+1) was something easy and neat.

 

[NateTG]

x-1=(x-1)(1)
x^2-1=(x-1)(x+1)
x^3-1=(x-1)(x^2+x+1)
x^4-1=(x-1)(x^3+x^2+x+1)
...