Question

If \(2^{n}-1\) is prime, prove that n is prime?

Answer 1

@satellite73

Answer 2

@KingGeorge

Answer 3

Well, suppose towards a contradiction that \(n=a\cdot b\) is composite with \(a,b>1\). Then, \[2^n-1=2^{ab}-1=(2^a)^b-1\]Now substitute \(2^a=x\) to get \(x^b-1\), and use the formula I helped you prove by induction earlier.

Make sense?

Answer 4

I understand all the way up to the former formula. I know that it would look like\[(x-1)(x^{b-1}+x^{b-2}+...+x^{2}+x+1)\]
but why does that make \(2^{n}-1\) not prime?

Answer 5

\[2^n-1=(2^a)^b-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+...+2^a+1)\]Since \(a>1\), \(2^a-1>1\), and so we have that \((2^a-1)|(2^n-1)\).

Answer 6

thank you so much i understand it now. Proof writing is a very difficult task for me :(

Answer 7

Proof writing is definitely an acquired skill :P