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

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

I've looked at http://math.stackexchange.com/a/19998

It is known that $2^n-1$ can only be prime if $n$ is prime. This is because if $jk=n$, $2^n-1=\sum_{i=0}^{n-1}2^i=\sum_{i=0}^{j-1} 2^i \sum_{i=0}^{k-1} 2^{ij}$ So they will only continue to alternate at twin primes. In particular, $2^{6k+2}-1, 2^{6k+3}-1$ and $2^{6k+4}-1$ will all be composite

What I dont understand is how do I get:

$$\sum_{i=0}^{n-1}2^i=\sum_{i=0}^{j-1} 2^i \sum_{i=0}^{k-1} 2^{ij}$$

If I am looking at the wrong answer, how can I proof the above?

Then again, maybe I am indeed looking at the wrong thing?

In particular, $2^{6k+2}-1, 2^{6k+3}-1$ and $2^{6k+4}-1$ will all be composite

This doesnt say why $2^{6k+2}-1$ is composite?

-
$2^{6k+2}-1=(n+1)(n-1)$ where $n=2^{3k+1}$ - it's a difference of two squares. – Gerry Myerson Aug 25 '12 at 3:09
6k+2 and 6k+4 can't be prime because they are divisible by 2. 6k+3 is divisible by 3. – Ross Millikan Aug 25 '12 at 3:15

## 3 Answers

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.

-
Amusing how different our answers are. I hope the combination helps OP. – Ross Millikan Aug 25 '12 at 3:13
@RossMillikan: Your answer addresses the question much more directly than mine. – André Nicolas Aug 25 '12 at 3:21

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

-
number theory for computer scientists.. – nbubis Aug 25 '12 at 12:07
nbubis: You can generalize to $\frac{k^n-1}{k-1}$ if you like to. – Henning Makholm Aug 25 '12 at 12:09

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.

-