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
Physical constant is constant even in strong gravitational fields
Montreal VR headset team turns to crowdfunding for Totem
Researchers study vital 'on/off switches' that control when bacteria turn deadly
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,991
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