Division in natural numbers

Question

Let $n$ be a positive integer greater than $1$. Show that there exists an integer $m$ greater than $n^n$ such that $(n^m-m^n)/(n+m)$ is an integer.

Answer 1

Hint. $n^m-m^n\equiv n^m+(-1)^{n+1}n^n$

Hint 2. Try $m=a\cdot n^n-n$

${}$

Let $m=an^n-n$. We want $a\mid n^{m-n}+(-1)^{n+1}$. If $n$ is odd, we can take $a=2$. If $n>2$ is even, we can take any divisor of $n-1$ for $a$ (e.g. $n-1$).
Note that $(n-1)n^n-n>n^n$ for $n>2$.
If $n=2$, we can take $m=5$.