# $(2^m -1)(2^n-1)$ divides $(2^{mn} -1)$ if and only if $\gcd(m,n) = 1$.

If $\gcd(m,n) = 1$ then $(2^m-1)(2^n-1)$ divides $2^{mn} - 1$ because each of $2^m-1$, $2^n-1$ divide $2^{mn}-1$ and $\gcd(2^m-1, 2^n-1) = 2^{\gcd(m,n)}-1 = 1$. How about the converse? If $\gcd(m,n) > 1$, can one show that $(2^m-1)(2^n-1)$ does not divide $(2^{mn}-1)$?

-

I'm going to write this proof in the style in which I found it and leave it to someone else to translate it into more usual number-theoretic language.

We have

$$(2^{mn}-1)/(2^m-1)=1+2^m+2^{2m}+\dotso+2^{(n-1)m}=1\overbrace{\underbrace{0\ldots0}_{m-1}1\ldots1\underbrace{0\ldots0}_{m-1}1}^{n-1}{}_2$$

and

$$2^n-1=\overbrace{1\ldots1}^n{}_2\;.$$

The question is whether the first of these is divisible by the second. Adding the second pattern into the first such that its least significant digit is aligned with a $1$ shifts that $1$ upward by $n$ digits.

Now if $\gcd(m,n)$, then successively shifting all $1$s except the most significant $1$ past the latter puts them all into different digits. That leaves $n$ consecutive $1$s, i.e. a power of $2$ times $2^n-1$.

This won't work if $\gcd(m,n)\gt1$ because in that case some of the $1$s would land on top of each other. So what we want to show is that if the first number were divisible by the second one, it would have to be possible to gather all the $1$s together.

So assume that $k\cdot\overbrace{1\ldots1}^n{}_2=1\overbrace{\underbrace{0\ldots0}_{m-1}1\ldots1\underbrace{0\ldots0}_{m-1}1}^{n-1}{}_2$. Let $r=2^s$ be some power of $2$ greater than $k$. Then $(r-k)\cdot\overbrace{1\ldots1}^n{}_2+1\overbrace{\underbrace{0\ldots0}_{m-1}1\ldots1\underbrace{0\ldots0}_{m-1}1}^{n-1}{}_2=r\cdot\overbrace{1\ldots1}^n{}_2=\overbrace{0\ldots0}^s\overbrace{1\dotso1}^n{}_2$. Now consider the binary representation of $r-k$. Each of its digits represents adding $n$ consecutive $1s$ at the corresponding digit of the result. Going from the least to the most significant digit, each of these additions must move the least significant remaining $1$ upward by $n$ digits, because if it skips a $1$, that $1$ can never be cancelled again, and if it adds to a $0$ instead, the resulting $1$ can also never be cancelled again. Also, a $1$ may never land on another $1$, since that would reduce the number of $1$s and the process can't generate any new ones, so we couldn't end up with $n$ consecutive $1$s anymore.

Thus, the additions would have to move the $1s$ in a manner that's impossible if $\gcd(m,n)\gt1$, so in this case $(2^{mn}-1)/(2^m-1)$ is not divisible by $2^n-1$, and hence $2^{mn}-1$ is not divisible by $(2^m-1)(2^n-1)$.

-
"...translate it into more usual number-theoretic language." Prepare for Dubuque's two liners. +1 – Pedro Tamaroff Oct 30 '12 at 4:05

Here's another proof I found. First we need the following:

Lemma If $m,n$ are positive integers with $m > n$, then $(2^m - 1)(2^n-1) \mid (2^{mn}-1)$ implies $(2^{m-n}-1)(2^n-1) \mid (2^{(m-n)n} - 1)$.

Proof of lemma. $(2^m-1)(2^n-1) \mid (2^{mn}-1)$ is equivalent to $(2^{mn} - 1)/(2^m-1) \equiv 0 \pmod{2^n-1}$. Using $2^m \equiv 2^{m-n} \pmod{2^n-1}$ we have $(2^{mn} - 1)/(2^m-1) \equiv 2^{m(n-1)} + 2^{m(n-2)} + \cdots 2^m + 1 \equiv 2^{(m-n)(n-1)} + 2^{(m-n)(n-2)} + \cdots 2^{m-n} + 1 \equiv (2^{(m-n)n} - 1) / (2^{m-n}-1) \pmod{2^n-1}$. Thus $(2^{(m-n)n} - 1) / (2^{m-n}-1) \equiv 0 \pmod{2^n-1}$ which is equivalent to the stated conclusion.

Now to our main task. Suppose $m$, $n$ are positive integers with $\gcd(m,n) = d$. By a well-known algorithm to compute the greatest common divisor, there is a sequence $(m_1,n_1), (m_2, n_2), \ldots, (m_k, n_k)$ such that: $(m_1, n_1) = (m, n)$, $(m_k, n_k) = (d, d)$, $m_i \not= n_i$ for $1 < i < k$ and $(m_{j+1}, n_{j+1}) = (m_j-n_j,n_j)$ if $m_j > n_j$, $(m_{j+1}, n_{j+1}) = (m_j, n_j-m_j)$ if $n_j > m_j$ for $1 \leq j < k$.

If $(2^m-1)(2^n-1) \mid (2^{mn}-1)$ then using the lemma one shows by induction $(2^{m_j}-1)(2^{n_j}-1) \mid (2^{m_jn_j}-1)$ for all $j$ in the range $1 \leq j \leq k$. For $j =k$, this means $(2^d-1)(2^d-1) \mid (2^{d^2}-1)$ which is equivalent to $(2^{d^2}-1)/(2^d-1) \equiv 0 \pmod{2^d-1}$. But $(2^{d^2}-1)/(2^d-1) \equiv 2^{d(d-1)} + 2^{d(d-2)} + \cdots + 2^{d} + 1$. Since $2^d \equiv 1 \pmod{2^d-1}$, the latter sum is $\equiv d \pmod{2^d-1}$, and we conclude $d \equiv 0 \pmod{2^d-1}$, which happens only when $d = 1$. End of proof.

-

The following generalization can be proved by a straightforward adaptation of the proof I gave above:

Given integer $a \geq 2$, positive integers $m,n$, and $k$ a positive integer that is a common divisor of $m$, $n$, then

$(a^m-1)(a^n-1)/(a^k-1)$ divides $a^{mn}-1$ if and only if $k = \gcd(m,n)$.

-