Register to reply

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

by smithg86
Tags: numbers, prime
Share this thread:
smithg86
#1
Jul25-07, 10:50 AM
P: 60
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?
Phys.Org News Partner Science news on Phys.org
Suddenly, the sun is eerily quiet: Where did the sunspots go?
'Moral victories' might spare you from losing again
Mammoth and mastodon behavior was less roam, more stay at home
Kummer
#2
Jul25-07, 11:08 AM
P: 291
Is there another way to prove either one of these statements?
Why would you want to? This is both a short and elementary solution. That is often considered to be the nicest proof.
smithg86
#3
Jul25-07, 12:14 PM
P: 60
Quote Quote by Kummer View Post
Why would you want to? This is both a short and elementary solution. That is often considered to be the nicest proof.
I thought it would provide more insight as to why the statements are true.

americanforest
#4
Jan28-09, 08:19 PM
P: 218
Prime Numbers: (2^n - 1) and (2^n + 1)

Quote Quote by smithg86 View Post
[b]
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.

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?
General_Sax
#5
Feb9-12, 09:21 PM
P: 450
(x^k) - 1 = (x - 1)*(x^(k-1) + x^(k-2) + ... + x + 1)
Where does this factorization come from? I just need a link or something. Thanks.
Eigenstates
#6
Jul11-12, 09:29 PM
P: 1
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]
epenguin
#7
Jul12-12, 06:46 AM
HW Helper
epenguin's Avatar
P: 1,965
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.


Register to reply

Related Discussions
A prime number which equals prime numbers General Math 10
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number. Linear & Abstract Algebra 0
Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime Linear & Abstract Algebra 5
Prime Numbers Linear & Abstract Algebra 44
Prime numbers General Discussion 1