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!

Prime Numbers: (2^n - 1) and (2^n + 1)

  1. Jul 25, 2007 #1
    1. The problem statement, all variables and given/known data

    I was able to prove both of these statements after getting some help from another website, but I am trying to find another way to prove them. Can you guys check my work and help me find another way to prove these, if possible? Thanks.

    Part A: Show that if 2^n - 1 is prime, then n must be prime.

    Part B: Show that if 2^n + 1 is prime, where n [tex]\geq[/tex] 1, then n must be of the form 2^k for some positive integer k.

    2. Relevant equations

    (x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)

    3. The attempt at a solution

    Part A:

    Write the contrapositive,
    n is not prime (a.k.a. n is composite) ==> 2^n - 1 is composite
    Assume n is composite. Let n = p*q, where neither p nor q are 1.
    Then,
    2^n - 1 = (2^p)^q - 1 = (2^p - 1)*((2^p)^(q-1) + (2^p)^(q-2) + ... + (2^p) + 1)

    Note that 2^p - 1 > 1. Also, ((2^p)^(q-1) + (2^p)^(q-2) + ... + (2^p) + 1) > 1. So we have factored 2^n - 1, thus it is not prime. We have proved the contrapositive, so the original statement is true.

    --------

    Part B:

    Note that if n is of the form 2^k, then n's prime factorization is only composed of 2's. Thus, the contrapositive of the original statement is as follows:

    n = b*(2^k), where b is a positive odd number ==> 2^n + 1 is composite.

    Let n = b*(2^k). Then,

    2^n + 1 = 2^(b*(2^k)) + 1 = ((2^(2^k))^b + 1 = (2^(2^k) + 1)*{[(2^(2^k)]^(k-1) + [2^(2^k)]^(k-2) + ... + [2^(2^k)] + 1}

    Observe that [2^(2^k) + 1)] > 1 and {[(2^(2^k)]^(k-1) + [2^(2^k)]^(k-2) + ... + [2^(2^k)] + 1} > 1. We have factored 2^n + 1, so it is composite. This proves the contrapositive of the original statement, so the original statement is true.

    -------

    Is there another way to prove either one of these statements?
     
  2. jcsd
  3. Jul 25, 2007 #2
    Why would you want to? This is both a short and elementary solution. That is often considered to be the nicest proof.
     
  4. Jul 25, 2007 #3
    I thought it would provide more insight as to why the statements are true.
     
  5. Jan 28, 2009 #4



    Should it state

    [tex][(2^{2^{k}})^{b}+1]=(2^{2^{k}} + 1)([2^{2^{k}}]^{b-1} + [2^{2^{k}}]^{b-2} + ... + [2^{2^{k}}] + 1)[/tex]?

    Can someone prove the general case of this expansion via Binomial Theorem for me?
     
    Last edited: Jan 28, 2009
  6. Feb 9, 2012 #5
    Where does this factorization come from? I just need a link or something. Thanks.
     
  7. Jul 11, 2012 #6
    the factorizations come fromm doing polynomial long division of [itex]x^n-1[/itex] and [itex]x^n+1[/itex] with [itex] x^p-1 [/itex] and [itex] x^p+1[/itex] if [itex]n=pq[/itex]

    [itex]x^n-1 = (x^p-1)(x^{p(q-1)}+x^{p(q-2)}+\cdots +x^p+1) [/itex]

    The other equation should read:

    [itex]x^n+1 = (x^p+1)(x^{p(q-1)}-x^{p(q-2)}+\cdots -x^p+1 )[/itex]

    With alternating signs.

    Again this comes from polynomial long division, taking [itex]x^n+1[/itex] and dividing by [itex]x^p+1[/itex]
     
  8. Jul 12, 2012 #7

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    For the first part I would start with setting out 2 =

    There is nothing more elementary in math, but I have found someone at least got stuck in thinking of anything that 2 =

    After that you do have to use the binomial theorem which was found easier.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?