First we prove that the operations $(a, b)$ and $2^x-1$ commute: that is, $2^{(a, b)}-1=(2^a-1, 2^b-1)$ (where of course $(a, b)$ is the greatest common factor between $a$ and $b$). We know that $2^a-1|2^{ma}-1$ because $(2^a-1)(2^{m(a-1)}+2^{m(a-2)}+\ldots+1)=2^{ma}-1$. So $2^{(a, b)}-1$ is a factor of both $2^a-1$ and $2^b-1$. Now we need to know that if $x|2^a-1$ and $x|2^b-1$, then $x|2^{(a, b)}-1$. Clearly we can say that $x$ is odd. Now take the smallest integer $c(x)$ so that $2^{c(x)}\equiv1\mod x$. That is, find the order of $2\mod x$. Then $2^k$ is periodic $\mod x$ with period $c(x)$. Now this period must divide both $a$ and $b$, so $c(x)|(a, b)$. Hence $2^{(a, b)}\equiv1\mod x$. Thus $(2^a-1, 2^b-1)=2^{(a, b)}-1$. Now the problem is easy. We know that $2^n-1|2^{2m}-1=(2^m+1)(2^m-1)$, but also $(2^n-1, 2^m-1)=(2^n-1, 2^m+1-2)=(2^n-1, 2)=1$. So we need $(n, 2m)=n$ and $(n, m)=1$. Thus $n|2$, so $n=1$ or $n=2$. If $n=1$ then $m$ can be arbitrary. If $n=2$ then $m$ must be odd. So all solutions are $(1, k)$ and $(2, 2k+1)$.