Question

Prove that if 2^n − 1 is prime, then n is prime for n being a natural number.

Answer 1

can't be factored

Answer 2

http://primes.utm.edu/notes/proofs/Theorem2.html

"Let r and s be positive integers, then the polynomial xrs-1 is xs-1 times xs(r-1) + xs(r-2) + ... + xs + 1. So if n is composite (say r.s with 1<s<n), then 2n-1 is also composite (because it is divisible by 2s-1)."

Answer 3

Let n = ab (ie composite)

2^ab-1 = (2^a-1)(1+2^a +2^(2a)+ .....2^(a(b-1)) and a can be swapped for b as well.

Since u can factor when n = ab, n must be prime for 2^n-1 to be prime.

Answer 4

i don't get what linjaaho is trying to say. it's stated that 2^(n) -1 is prime and not composite. and why does the proof involves 2^(n) -1 to be composite?

Answer 5

estudier. i get this part "2^ab-1 = (2^a-1)(1+2^a +2^(2a)+ .....2^(a(b-1)) and a can be swapped for b as well. " but i'm lost after that.

Answer 6

It's saying that if n is composite then 2^ab-1 is not prime, so for it to be prime n must be prime.

Answer 7

thanks