# How can I algebraically prove that $2^n - 1$ is not always prime?

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.

-
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

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

-
And what would be the factored form of $2^{ab} - 1$? :-) P.S.: Hey Brian! –  Parth Kohli Dec 22 '12 at 10:40
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

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.

-

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.

-
It is a proof... –  Parth Kohli Dec 22 '12 at 10:37
@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

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

-
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

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

-