# Homework Help: Simple proof

1. Feb 5, 2008

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

2. Feb 5, 2008

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

3. Feb 5, 2008

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

4. Feb 5, 2008

### 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?

5. Feb 5, 2008

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

6. Feb 5, 2008

### 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 dunno what.

7. Feb 5, 2008

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

8. Feb 5, 2008

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

9. Feb 5, 2008

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

Last edited: Feb 5, 2008
10. Feb 5, 2008

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