(adsbygoogle = window.adsbygoogle || []).push({}); 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?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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)

Have something to add?

**Physics Forums - The Fusion of Science and Community**