## anonymous 3 years ago If $$2^{n}-1$$ is prime, prove that n is prime?

1. anonymous

@satellite73

2. anonymous

@KingGeorge

3. KingGeorge

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?

4. anonymous

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?

5. KingGeorge

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

6. anonymous

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

7. KingGeorge

Proof writing is definitely an acquired skill :P