Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
$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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.