Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$2^3 - 1 = 7$ which is prime. –  user38268 Jan 31 '12 at 18:37
1  
@BenjaminLim I think that the statement should be "with k = ab, and $a \neq 1$ and $b \neq 1$. –  userxxxxx 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
2  
Theorems about Mersenne numbers –  pedja 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

4 Answers 4

up vote 6 down vote accepted

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

share|improve this answer
1  
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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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