If $2^{n}-1$ is prime, prove that n is prime?

Question

anonymous · Answer

@satellite73

anonymous · Answer

@KingGeorge

kinggeorge · Answer

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?

anonymous · Answer

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?

kinggeorge · Answer

$$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)$.

anonymous · Answer

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

kinggeorge · Answer

Proof writing is definitely an acquired skill :P