2
$\begingroup$

This question already has an answer here:

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

$\endgroup$

marked as duplicate by lulu, JMoravitz, Jyrki Lahtonen Apr 17 '17 at 21:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

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.

$\endgroup$