SOLUTION: ) Show that if n is a natural number such that 2n-1 is prime, thenn n is a prime. Is the concerse true? Explain? B) Show that if n is a natural number such that 2n+1 is prime, t

Algebra ->  Complex Numbers Imaginary Numbers Solvers and Lesson -> SOLUTION: ) Show that if n is a natural number such that 2n-1 is prime, thenn n is a prime. Is the concerse true? Explain? B) Show that if n is a natural number such that 2n+1 is prime, t      Log On


   

Question 409839: ) Show that if n is a natural number such that 2n-1 is prime, thenn n is a prime. Is the concerse true? Explain?
B) Show that if n is a natural number such that 2n+1 is prime, thenn n is a power of 2. Is the concerse true? Explain?

Answer by richard1234(7193) About Me  (Show Source):
You can put this solution on YOUR website!
I sure hope you mean 2%5En+-+1 instead of 2n-1. In fact I am working on a mathematics project regarding odd perfect numbers, and such a prime in the form 2%5En+-+1 is important since there is a one-to-one correlation between these primes (called Mersenne primes) and the *even* perfect numbers.

Suppose that n is not prime, i.e. n = ab for positive integers a and b, where a and b are not equal to 1. Then, 2%5En+-+1+=+2%5Eab+-+1, and this can be factored as %282%5Ea+-+1%29%2Asum%282%5Eai%2C+i+=+1%2C+b-1%29 (this comes from the geometric series). Since neither factor is 1, then 2%5En+-+1 can be factored as a product of two integers, hence it is not prime. The contrapositive is true, i.e. if 2%5En+-+1 is prime, then n is prime. The converse is not necessarily true, and we can find counterexamples, such as n = 11, as 2%5E11+-+1+=+23%2A89.

Part b is a little tricky, I spent a bit of time on the problem and couldn't come with a full solution. Perhaps you could use an inductive argument, or show that 2%5E%282%5Ek%29+%2B+1 cannot be factored for any k (which might also use induction).