Simple proof

  • Thread starter mae
  • Start date
  • #1
mae
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.
 

Answers and Replies

  • #2
NateTG
Science Advisor
Homework Helper
2,450
6
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:
[tex]2^{k \times k}-1[/tex]

There's an easy answer when k is even.
 
  • #3
mae
6
0
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
morphism
Science Advisor
Homework Helper
2,015
4
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
mae
6
0
*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
836
13
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
mae
6
0
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
mae
6
0
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
mae
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.
 
Last edited:
  • #10
NateTG
Science Advisor
Homework Helper
2,450
6
[tex]x-1=(x-1)(1)[/tex]
[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]
...
 

Related Threads on Simple proof

  • 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
Top