Results 1 to 4 of 4

Math Help - if ((2^n) -1 ) is prime, prove n is prime ?! >.<

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    6

    Exclamation if ((2^n) -1 ) is prime, prove n is prime ?! >.<

    Ok heres the question! :

    if (2^n) -1 ) is prime, prove n is prime

    i have attempted this question. However, i do not knw if i have started it off right, below is what i have done so far:

    Suppose n is COMPOSITE, and let n = rs, where r, s >1

    hence, ((2^n) -1 ) becomes if ((2^rs) -1 )

    then
    ((2^rs) -1 )=((2^s) -1 ) (1 + (2^s) +(2^2s)+(2^3s)+...+(2^s(r-1)) )

    so ((2^s) - 1) | ((2^n) -1 )

    since ((2^n) -1 ) is prime .....


    then after this i dont know what to do, if possible could someone please tell me how to continue please or a hint or something.

    thankyou very much in advance, CoCo_RoAcH ^^
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    14,973
    Thanks
    1121
    Use the fact that x^m-1= (x- 1)(x^{m-1}+ x^{m-2}+ \cdot\cdot\cdot+ x^2+ x+ 1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Remember that 2^n - 1 is prime which means its divisors are either 1 or itself.

    Since 2^s - 1 \Big| 2^n - 1.

    This means either 2^s - 1 = 1 or 2^s - 1 = 2^n - 1.

    Either way, what can you say about a and b ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    6
    Quote Originally Posted by o_O View Post
    Remember that 2^n - 1 is prime which means its divisors are either 1 or itself.

    Since 2^s - 1 \Big| 2^n - 1.

    This means either 2^s - 1 = 1 or 2^s - 1 = 2^n - 1.

    Either way, what can you say about a and b ?

    ok, im assuming when you mention a and b they are like my r and s.

    so then s = 1 or s = n, and r = 1 or r = n aswell

    hence, n = nx 1 or 1 x n

    therefore n is prime, when 2^n -1 is prime.


    Thankyou for the help! greatly appreciated! ^^
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 0
    Last Post: September 24th 2011, 11:23 AM
  3. Replies: 1
    Last Post: June 19th 2011, 12:56 PM
  4. Replies: 6
    Last Post: August 27th 2010, 11:44 PM
  5. Replies: 3
    Last Post: October 3rd 2009, 05:18 AM

Search Tags


/mathhelpforum @mathhelpforum