Prove that for any $m,n\in\mathbb{Z}^+$, the number $2^n-1$ is divisible by $(2^m-1)^2$ iff the number $n$ is divisible by $m(2^m-1)$.

My work so far:

It's an if and only if statement, so the common approach is to split the proof into two "if then" proofs ($A\rightarrow B \text{ and } B\rightarrow A$).

Starting with $A\rightarrow B$, for a direct proof, I would assume $A$ and prove $B$. I can use the definition of divisibility:

Assume $n=m(2^m-1)k$ for some integer $k$

Then I need to prove that $2^n-1=(2^m-1)^2h$ for some integer $h$

So I'm thinking I need to start with the expression $2^n-1$ and transform it to $(2^m-1)^2h$, or vice versa, and I need to use the assumption $n=m(2^m-1)k$ somehow.

I notice that the LS of the equality contains the variable $n$ while the RS contains $m$, and the assumption relates $n$ to $m$, so that could be a way forward. For example, simple substitution gives $2^{m(2^m-1)k}-1$, but I'm not sure what I could do from here. Perhaps there's a divisibility theorem that could help?

Other things I notice: $2^n-1$ and $(2^m-1)^2$ are always odd. Also, the divisors in both cases are multiples of $2^m-1$.

Any help/hints appreciated.


Hints. $$\gcd(2^n-1,2^m-1) = 2^{\gcd(m,n)}-1,\tag{1} $$ hence in order that $(2^m-1)\mid (2^n-1)$, we must have $m\mid n$, and this is a sufficient condition, too, since: $$ y^a-1 = (y-1)\cdot(y^{a-1}+\ldots+y+1).\tag{2} $$ Suppose now that $n=mh$. We have: $$ 2^n-1 = (2^m-1)\cdot\left(2^{m(h-1)}+\ldots+2^{m}+1\right)\tag{3} $$ and: $$ 2^{mu}=\left((2^m-1)+1\right)^{u}\equiv 1\pmod{(2^m-1)}\tag{4} $$ hence in order that $(2^m-1)^2\mid (2^n-1)$ we must have $(2^m-1)\mid h$, and it is also a sufficient condition. Putting all together: $$ (2^m-1)^2\mid (2^n-1)\quad\Longleftrightarrow\quad m(2^m-1)\mid n. \tag{5} $$

  • 1
    $\begingroup$ Thanks very much Jack. I don't know what rule justifies (1)? $\endgroup$ – yroc Feb 7 '15 at 22:15
  • 1
    $\begingroup$ @yroc: if you like, write $n$ as $km+r$, then apply $(4)$. $\endgroup$ – Jack D'Aurizio Feb 7 '15 at 23:29
  • 1
    $\begingroup$ @yroc See also this or more generally, this $\endgroup$ – punctured dusk Apr 9 '15 at 14:33

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.