Mongolian Mathematical Olympiad

Let $n, m > 1$. $\varphi(m) = 2^{m_0} \cdot m_1$, $\varphi(n) = 2^{n_0} \cdot n_1$ ($m_0, n_0 \ge 0$, $m_1, n_1$-odd natural numbers.) Assume that $m_0 \ge n_0$ and let $n$ be the least number such that $n \mid 2^k - 1$.
Set $k = 2^{k_0} \cdot k_1$, where ($k_0$ is nonnegative whole number, $k_1$ is odd natural number). Since $n$ is divisor of odd number, $n$ is odd too.
Now by Euler's theorem $n \mid 2^{\varphi(n)} - 1$ and $k \mid \varphi(n) \Rightarrow k_0 \neq n_0$. (1)
Combining it with given condition we get $n \mid (2^{\varphi(m)} - 1)(2^{\varphi(m)} + 1) = 2^{2\varphi(m)} - 1$ and $k \mid 2\varphi(m)$. Since $n \nmid 2^{\varphi(m)} - 1$, from where follows $k \nmid \varphi(m)$.
From $k \mid 2\varphi(m)$ and $k \nmid \varphi(m)$ it follows $k_0 = m_0 + 1$. By (1) we get
$n_0 \ge m_0 + 1$ but it contradicts to $m_0 \le n_0$.
Since the case that $n_0 > m_0$ leads also to contradiction, we conclude that
$m = 1$ or $n = 1$.

If $m=1$ then $n \mid 3 \Rightarrow n=3$ or $n=1$.
Consequently we get 3 solutions: $(m, n) = (1, 1), (1, 3), (3, 1)$.
If $n=1$ then $(m, n) = (3, 1), (1, 1)$. Finally, we conclude that there are
only 3 solutions $(m, n) = (1, 1), (1, 3), (3, 1)$.