10
$\begingroup$

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

I've looked at https://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?

  • 0
    6k+2 and 6k+4 can't be prime because they are divisible by 2. 6k+3 is divisible by 3.2012-08-25

3 Answers 3

10

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.

  • 0
    @RossMillikan: Your answer addresses the question much more directly than mine.2012-08-25
8

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 $

  • 0
    nbubis: You can generalize to $\frac{k^n-1}{k-1}$ if you like to.2012-08-25
1

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.