Results 1 to 4 of 4

Math Help - Prime Number Proof

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    7

    Arrow Prime Number Proof

    How should i start off this proof?

    If (2^n -1) is prime, prove that n is prime.

    So far I've only got 2 things written down:

    1. If 2^n -1 is prime then using divisor notation. 1|(2^n -1) and (2^n -1)|(2^n -1). But I dont think this helps.

    2. To prove this we can prove gcd((2^n -1),n) = 1 (i.e relatively prime)

    Other than that not much idea at all.

    Any suggestions would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Let: n = ab

    We're going to use the fact that: x^{y} - 1 = \left(x - 1\right)\left(x^{y-1} + x^{y-2} + \cdots + x + 1\right)

    So we then have: 2^{n} - 1 = 2^{ab} - 1 = \left(2^a\right)^b - 1 = \left(2^a - 1\right)\left( \left(2^a\right)^{b-1} + \left(2^a\right)^{b-2} + \cdots + 2^a + 1\right)

    This means that: \left( 2^a - 1\right) \Big| \left(2^n - 1\right)

    But 2^n - 1 is prime. So what can you conclude about its divisor 2^a - 1 ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    7

    Talking

    Quote Originally Posted by o_O View Post
    So what can you conclude about its divisor 2^a - 1 ?
    Is it that:

    Since (2^n -1) is prime anything that divides it must be (2^n -1) or 1 itself so (2^a -1)|(2^n -1) implies that

    (2^a -1) = (2^n -1) or (2^a -1)=1

    => a = n or => a = 1

    so since n=ab then b = 1 or b = n.

    Therfore if (2^n -1) is prime then n=ab=n x 1 so n is also prime.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime number proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 29th 2012, 02:43 PM
  2. induction..prime number proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 30th 2010, 09:47 AM
  3. Prime number Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 23rd 2009, 08:47 PM
  4. Proof of Prime number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 05:19 AM
  5. Prime Number Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 9th 2008, 01:22 PM

Search Tags


/mathhelpforum @mathhelpforum