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

  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.
    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. Why would you want to? This is both a short and elementary solution. That is often considered to be the nicest proof.
  4. I thought it would provide more insight as to why the statements are true.

  5. 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. Where does this factorization come from? I just need a link or something. Thanks.
  7. 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. epenguin

    epenguin 2,499
    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 thead via email, Google+, Twitter, or Facebook

Have something to add?