Prove that if $2^n - 1$ is prime, then $n$ is prime for $n$ being a natural number

Solution 1:

If $2^n-1$ is prime, then $n$ cannot be $1$. We show that $n$ cannot be composite.

Suppose to the contrary that $n=ab$, where $a$ and $b$ are greater than $1$. Then $$2^n-1=2^{ab}-1=(2^a)^b-1.$$

Let $x=2^a$. Then $2^n-1=x^b-1$.

But $$x^b-1=(x-1)(x^{b-1}+x^{b-2}+\cdots +x+1.\tag{$1$})$$ To see this, just multiply out: almost everything cancels.

Now $x=2^a \ge 4$, so $x-1\gt 1$. It is easy to see that $x^{b-1}+x^{b-2}+\cdots +x+1\gt 1$. It follows from $(1)$ that $x^b-1$, that is, $2^n-1$, is the product of two numbers that are $\gt 1$. This contradicts the given fact that $2^n-1$ is prime.

Solution 2:

Consider what $2^n-1$ looks like when written in base 2: $$ \underbrace{111\cdots\cdots\cdots\cdots1}_{n} $$ If $n$ is not a prime, say $n=ab$, then $2^n-1$ is clearly the product of $$ \underbrace{111\cdots1}_{a} $$ with $$ 1\underbrace{\underbrace{00\cdots 0}_{a-1}1 \underbrace{00\cdots 0}_{a-1}1\cdots1 \underbrace{00\cdots 0}_{a-1} }_{b-1}1 $$

Solution 3:

If you work through the sums, all the terms on the left are matched to a term on the right. The first check is that you have the right number. There are $n$ terms on the left and $jk$ on the right. Since the right sum is inside the left sum, $i$ is fixed, so it has $2^{i(k-1)}$ to $2^{ik-1}$ and the next term picks up at $2^{ik}$. My point in the last thing you quote comes from the fact that $6k+2, 6k+3, \text{and} 6k+4$ are all composite, so these will be, too.