Mongolian Mathematical Olympiad

Let $n,m>1$. $\phi (m)=2^{m_0}\cdot m_1$, $\phi (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^{\phi (n)}-1$ and $k\mid \phi (n)\Rightarrow k_0\ne n_0$. (1) Combining it with given condition we get $n\mid (2^{\phi (m)}-1)(2^{\phi (m)}+1)=2^{2\phi (m)}-1$ and $k\mid 2\phi (m)$. Since $n\nmid 2^{\phi (m)}-1$, from where follows $k\nmid \phi (m)$. From $k\mid 2\phi (m)$ and $k\nmid \phi (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)$.