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}^*$ be such that $m = d a$, $n = d b$, with $(a, b) = 1$.
The initial condition becomes: $d^{2016} a^{2016} + d a + d^2 b^2$ is divisible with $d^2 a b$. So $d a b$ 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.