3
$\begingroup$

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.

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

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

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

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.