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.

This question is from Elementary Number Theory by W. Edwin Clark.

Is $2^n - 1$ always prime, or not? Prove.

Is this a start? $x^n - 1 = ( x - 1)(1 + x + x^2 \cdots x^{n - 1})$. So, $2^n - 1 = \sum \limits _{i = 0}^{n - 1} 2^i.$

Will I reach a solution through the above, or is there any other way?

I know that the property doesn't hold true for $n = 1,4,6$ et al but I want an algebraic proof.

share|improve this question
    
I think the question can be interpreted as "prove that there are infinitely many $n$ such that $2^n-1$ is not prime". Otherwise, as @Hurkyl mentioned, you have already proved your own statement. –  akkkk Dec 22 '12 at 10:40
add comment

5 Answers

up vote 8 down vote accepted

HINT: If $n=ab$, then $2^a-1$ is a factor of $2^n-1$.

share|improve this answer
    
And what would be the factored form of $2^{ab} - 1$? :-) P.S.: Hey Brian! –  Parth Kohli Dec 22 '12 at 10:40
2  
Gee, I wonder: $2^{ab}-1=\left(2^a\right)^b-1^b=\ldots~$ nope, too hard for me. :-) Actually, the really cute way to see it is to write the numbers in binary: $2^{ab}$ is a string of $ab$ $1$’s. –  Brian M. Scott Dec 22 '12 at 10:43
    
@DumbCow - try using the factorisation you have given in the question with an appropriate choice of $x$ –  Mark Bennet Dec 22 '12 at 10:43
    
@Markbennet: Oh yes, thanks. –  Parth Kohli Dec 22 '12 at 10:44
add comment

I know that the property doesn't hold true for n=1,4,6 et al.

I just want to clearly point out that this statement all by itself (or possibly with a calculation demonstrating the truth of the statement) constitutes a proof of the question asked.

share|improve this answer
add comment

Take $n=4$. Then $2^n-1=16-1=15=3\cdot 5$ which is not a prime. The statement is proven, that is $2^n-1$ is not always a prime.

EDIT: Why this is a formal proof: We want to prove that $$\neg (\forall n\in \mathbb{N})(2^n-1\in \mathbb{P})$$ or equivalently that $$(\exists n\in \mathbb{N})\neg (2^n-1\in \mathbb{P})$$ or even $$(\exists n\in \mathbb{N})(2^n-1\notin \mathbb{P})$$ Since $\exists 4\in \mathbb{N}$ and $2^4-1\notin \mathbb{P}$, the statement is proven.

share|improve this answer
    
It is a proof... –  Parth Kohli Dec 22 '12 at 10:37
3  
@DumbCow This is a proof! –  Nameless Dec 22 '12 at 10:37
    
It should be a formal proof :) –  Parth Kohli Dec 22 '12 at 10:37
    
@DumbCow I believe I now fully justified why this is a rigorous proof –  Nameless Dec 22 '12 at 10:46
    
Looks legit pretty much :) –  Parth Kohli Dec 22 '12 at 10:51
add comment

If $n$ is even say $n = 2m$ then $2^n - 1 = 2^{2m } -1 = (2^m + 1)(2^m - 1) $ which is not prime. More generally if $n$ is composite then by the formula for the sum of a geometric series we get that...

share|improve this answer
    
I like it :-). So, the main point of our proof is that it is not prime since it has factors. –  Parth Kohli Dec 22 '12 at 10:38
add comment

You might like to ponder why $2047 = 23 \times 89$ is a different kind of example from those already given in previous answers.

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.