1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple proof

  1. Feb 5, 2008 #1

    mae

    User Avatar

    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. jcsd
  3. Feb 5, 2008 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Feb 5, 2008 #3

    mae

    User Avatar

    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.
     
  5. Feb 5, 2008 #4

    morphism

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  6. Feb 5, 2008 #5

    mae

    User Avatar

    *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.
     
  7. Feb 5, 2008 #6
    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.
     
  8. Feb 5, 2008 #7

    mae

    User Avatar

    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.
     
  9. Feb 5, 2008 #8

    mae

    User Avatar

    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.
     
  10. Feb 5, 2008 #9

    mae

    User Avatar

    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
  11. Feb 5, 2008 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    [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]
    ...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Simple proof
  1. Simple Proof (Replies: 1)

  2. Simple Proof (Replies: 7)

  3. Simple proof ? (Replies: 4)

  4. Simple Proof? (Replies: 10)

  5. Simple Proof (Replies: 2)

Loading...