67th Romanian Mathematical Olympiad

a) For instance, $m=4$, $n=2$.

b) Let $d$ be the greatest common divisor of $m$ and $n$, and $a,b\in {\mathbb{N}}^{\ast }$ be such that $m=da$, $n=db$, with $(a,b)=1$. The initial condition becomes: $d^{2016}{a}^{2016}+da+d^2{b}^2$ is divisible with $d^{2}ab$. So $dab$ divides $d^{2015}{a}^{2016}+a+d{b}^2$. Since $a$ divides $d^{2015}{a}^{2016}$, it follows that $a$ divides $d{b}^2$. But $(a,b)=1$, so $a$ divides $d$. On the other hand, $d$ divides $d^{2015}{a}^{2016}$ and $d{b}^2$, hence $d$ divides $a$. From the above $d=a$, hence $m=d^2$, therefore $m$ is a perfect square.