0
$\begingroup$

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.

  • 0
    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.2012-12-22

5 Answers 5

3

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

14

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.

9

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

  • 0
    And what would be the factored form of $2^{ab} - 1$? :-) P.S.: Hey Brian!2012-12-22
  • 3
    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.2012-12-22
  • 0
    @DumbCow - try using the factorisation you have given in the question with an appropriate choice of $x$2012-12-22
  • 0
    @Markbennet: Oh yes, thanks.2012-12-22
5

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.

  • 0
    It is a proof...2012-12-22
  • 3
    @DumbCow This is a proof!2012-12-22
  • 0
    It should be a formal proof :)2012-12-22
  • 0
    @DumbCow I believe I now fully justified why this is a rigorous proof2012-12-22
4

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

  • 0
    I like it :-). So, the main point of our proof is that it is not prime since it has factors.2012-12-22