# Proof involving primes [duplicate]

Let n be a natural number. Prove that if 2^n -1 is prime, then n is prime.

I have considered proof by contradiction, as well as writing the converse and contrapositive of the statement out, but still cannot seem to come up with a proof.

Any help is appreciated

## marked as duplicate by lulu, JMoravitz, Jyrki LahtonenApr 17 '17 at 21:04

Prove it by the contrapositive. Suppose that $n$ is not prime, that is, $n=pq$, where $p$ and $q$ are integers greater than $1$. We proceed by using the notable product $$a^k-1=(a-1)(a^{k-1}+a^{k-2}+\dots+a+1),\ \forall a\geq0,$$ for any integer $k\geq 1$.
Note that \begin{align} 2^n-1=(2^{p})^q-1&=(2^p-1)((2^p)^{q-1}+(2^p)^{q-2}+\dots+2^p+1). \end{align} Since $p,q>1$, it is easy to see that the integers $2^p-1$ and $(2^p)^{q-1}+(2^p)^{q-2}+\dots+2^p+1$ are greater than $1$. Therefore, $2^n-1$ is not a prime number.