Register to reply 
Prime Numbers: (2^n  1) and (2^n + 1) 
Share this thread: 
#1
Jul2507, 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^(k1) + x^(k2) + ... + 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)^(q1) + (2^p)^(q2) + ... + (2^p) + 1) Note that 2^p  1 > 1. Also, ((2^p)^(q1) + (2^p)^(q2) + ... + (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)]^(k1) + [2^(2^k)]^(k2) + ... + [2^(2^k)] + 1} Observe that [2^(2^k) + 1)] > 1 and {[(2^(2^k)]^(k1) + [2^(2^k)]^(k2) + ... + [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
Jul2507, 11:08 AM

P: 291




#3
Jul2507, 12:14 PM

P: 60




#4
Jan2809, 08:19 PM

P: 218

Prime Numbers: (2^n  1) and (2^n + 1)
Should it state [tex][(2^{2^{k}})^{b}+1]=(2^{2^{k}} + 1)([2^{2^{k}}]^{b1} + [2^{2^{k}}]^{b2} + ... + [2^{2^{k}}] + 1)[/tex]? Can someone prove the general case of this expansion via Binomial Theorem for me? 


#5
Feb912, 09:21 PM

P: 450




#6
Jul1112, 09:29 PM

P: 1

the factorizations come fromm doing polynomial long division of [itex]x^n1[/itex] and [itex]x^n+1[/itex] with [itex] x^p1 [/itex] and [itex] x^p+1[/itex] if [itex]n=pq[/itex]
[itex]x^n1 = (x^p1)(x^{p(q1)}+x^{p(q2)}+\cdots +x^p+1) [/itex] The other equation should read: [itex]x^n+1 = (x^p+1)(x^{p(q1)}x^{p(q2)}+\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] 


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 