# Prove that $n=2^k -1$ is not a prime number, with $k=ab$. (Edit: $a\not=1$ and $b\not=1$)

My initial idea is to prove that $2^k-1$ can be written with at least two factors. My feeling is that having $k=ab$ helps with the factorization. But I don't know how to go from there.

• $2^3 - 1 = 7$ which is prime. – user38268 Jan 31 '12 at 18:37
• @BenjaminLim I think that the statement should be "with k = ab, and $a \neq 1$ and $b \neq 1$. – Charles Jan 31 '12 at 18:43
• @CharlesMorisset Sorry been thinking too much about commutative rings. The statement should have been a non-trivial factorisation for $k$. – user38268 Jan 31 '12 at 18:47
• Theorems about Mersenne numbers – Peđa Terzić Jan 31 '12 at 18:53
• I'm sorry I didn't state that $ab$ is a non-trivial factorisation. – Javi Jan 31 '12 at 19:17

If $k = 2m$, you can write $2^{2m} - 1$ as the difference of two squares:

$2^{2m} - 1 = (2^m - 1)(2^m +1)$

which is a non-trivial factorisation if $m > 1$. Now when $k$ is odd I don't think it is necessarily true that $2^k -1$ is not prime. For example we have $2^5 - 1 = 31$ which is prime.

However if you can write down a non-trivial factorisation for $k$ (i.e. writing $k = ab$ for some $a,b$ both not equal to 1) then you can use the formula for the geometric series. Now how do you do this??

Consider the formula

$$\frac{(2^a)^{b} - 1}{(2^a) -1 } = 1 + 2^a + ({2^a})^{2} + \ldots ({2^a})^{b-1}.$$

Then all you need to do now is....

• Nice, much simpler than $x^a-1$ divides $x^{ab}-1$. – André Nicolas Jan 31 '12 at 18:41
• Got it. Thank you very much. – Javi Jan 31 '12 at 19:23
• @Javi No problems. – user38268 Feb 1 '12 at 2:23

I am assuming $a,b$ are positive integers strictly greater than 1. Now using the factorization formula, $x^n - y^n = (x - y)(x^{n-1} + x^{n-2}y + \cdots+y^{n-1}),$ we can write $2^{ab}-1=(2^{a})^b-1=(2^a-1)((2^a)^{b-1}+(2^a)^{b-1}+\cdots+1)$. Since $a\neq1$, this clearly implies $2^a-1$ is factor.

One of the easiest ways is to realize that if you write $2^k-1$ in binary, it’s a string of $k$ $1$’s. If $k=ab$, you can divide that string into $b$ blocks, each containing $a$ $1$’s. Now think about dividing $2^k-1$ by $2^a-1$, using the standard long division algorithm: you’ll get a $1$, then $(a-1)$ $0$’s and a $1$, and so on $-$ altogether $b$ $1$’s, with $(a-1)$ $0$’s between adjacent $1$’s, and there will be no remainder. (Note that this is really just a different way of looking at the argument given by Benjamin and Suresh.)

On this page, you can find the following theorem: if $2^k - 1$ is prime, then $k$ is prime. So if by $k = ab$, you mean that $k$ is not prime, then you can deduce that $2^k - 1$ is not prime either.

EDIT: note that the proof of this theorem uses the decomposition given in the other answers.