Team Selection Test for IMO

The answer is $(2,2)$ and $(2,4)$.

For $n=1$, we have $2+1=2$ which yields a contradiction.

If $n$ is a prime number, then $\varphi (n)=n-1$ and hence $2^n=n^m$. Therefore $m=n=2$.

If $n=p^2$ where $p$ is a prime number, then $\varphi (n)=p^2-p$ and we get $2^{p^2}+(p-1)!=p^{2m}+1$. For $p>2$ we have $(p-1)!\equiv 2(\mathrm{mod}4)$ which is possible only when $p=3$ but $2^9+2=514=3^{2m}+1$ has no solution in integers. For $p=2$, we get $m=2$.

In all the other cases, let $p$ be the smallest prime factor of $n$. As $1<p<2p<\cdots <p^2<n$, we have $n-1-\varphi (n)\ge p$ and therefore $p$ divides $(n-\varphi (n)-1)!$. Thus, $p|2^n-1$ and $p$ is odd. As $p|2^{p-1}-1$, $p|2^d-1$ where $d=\gcd (n,p-1)$. Since $p$ is the smallest prime factor of $n$, we get $d=1$ and hence $p|1$ which is a contradiction.