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.
Prove that $n=2^k -1$ is not a prime number, with $k=ab$. (Edit: $a\not=1$ and $b\not=1$)
-
0I'm sorry I didn't state that $ab$ is a non-trivial factorisation. – 2012-01-31
4 Answers
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.
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....
-
0@Javi No problems. – 2012-02-01
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.)