How do we show that $2^m - 1$ is a composite number if m is composite?

Question

While we can do it algebraically by factorizing some $2^b - 1$ out of the expression, how do we show it's composite in another way?

One solution that is known is $2^m - 1= (2^b - 1)(2^{m-b} + 2^{m-2b}...+2^{m-ab})$ which is composite. However, does this relation hold when m is not composite? I have always assumed it would, since it's similar to factorizing $x-1$ out of $x^3 - 1$.

Answer 1

We use the fact that $$x^n-1=(x-1)(x^{n-1}+x^{n-2}+\cdots+x+1)$$ to obtain $$\begin{align}2^{ab}-1&=(2^a)^b-1\\&=(2^a-1)(2^{ab-1}+2^{ab-2}+\cdots+1)\end{align}$$

Setting $m=ab$ ends the problem.

Setting $m=p$ where $p$ is an arbitrary prime will give you the answer to your other question.

Answer 2

When $p$ is prime you can still factor $x^p -1 = (x-1)(\text{other stuff)}$ but then substituting $2$ for $x$ gives you a factor of $2-1 = 1$ which is obvious and useless.

To address the first part of your question: I don't know another way to prove this, and haven't been tempted to look for one since this way is so natural and easy.

Answer 3

Use the following $$ {\rm gcd}(2^n-1,2^m-1)=2^{\rm gcd(n,m)}-1 $$