show that if $2^n -1$ is prime than n is also prime

Question

How to prove the above statement?

Do you have to use Fermat's little theorem where $a^p = a (\mod p)$

I cannot see how to use the above here

I tried to factorise $2^n -1 = (2-1)(2^{n-1} + 2^{n-2} + 2^{n-3} +......+1)$

does this help?

Answer 1

It is easy to prove the contrapositive, i.e., if $n$ is composite, then $2^n-1$ is also composite. We have $n=ab$ for $1<a,b < n$. Hence, $$2^n-1 = 2^{ab}-1 = (2^a)^b-1 = (2^a-1)((2^a)^{b-1} + (2^a)^{b-2} + \cdots + 1)$$ Hence, $2^a-1$, which is greater than $1$ divides $2^n-1$.