- #1

- 6

- 0

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

- Thread starter mae
- Start date

- #1

- 6

- 0

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

- #2

NateTG

Science Advisor

Homework Helper

- 2,450

- 6

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:

[tex]2^{k \times k}-1[/tex]

There's an easy answer when k is even.

- #3

- 6

- 0

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

morphism

Science Advisor

Homework Helper

- 2,015

- 4

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

- 6

- 0

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

- #6

- 836

- 13

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

- 6

- 0

- #8

- 6

- 0

- #9

- 6

- 0

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.

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:

- #10

NateTG

Science Advisor

Homework Helper

- 2,450

- 6

[tex]x^2-1=(x-1)(x+1)[/tex]

[tex]x^3-1=(x-1)(x^2+x+1)[/tex]

[tex]x^4-1=(x-1)(x^3+x^2+x+1)[/tex]

...

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 7

- Views
- 2K

- Last Post

- Replies
- 19

- Views
- 3K

- Last Post

- Replies
- 7

- Views
- 803

- Last Post

- Replies
- 2

- Views
- 1K

- Last Post

- Replies
- 10

- Views
- 875

- Last Post

- Replies
- 4

- Views
- 1K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 1K

- Last Post

- Replies
- 9

- Views
- 2K