Very nice problem although easy. My solution: Trying smaller cases we see that nearly always $n|m$ so we try to find solutions in the form $m=kn$ for $k\in \mathbb N$. Now lets rewrite $\frac{n^m-m^n}{m+n}$ as $\frac{n^m-m^n}{m+n}=\frac{n^{kn}-(kn)^n}{n(k+1)}=\frac{n^{n-1}(n^{(k-1)n}-k^n)}{k+1}$. Now we require that $k+1|n^{n-1}(n^{(k-1)n}-k^n)$. First case is when $n\equiv 1(mod 2)$.We have $n^{n-1}(n^{(k-1)n}-k^n)\equiv n^{n-1}(n^{(k-1)n}+1)(mod (k+1))$. Condition $m>n^n$ implies $k>n^{n-1}$.But since $2|n^{(k-1)n}+1$ we see that $k+1=2n^{n-1}$ works. So for odd $n$ we have $\boxed{m=(2n^{n-1}-1)n}$. Second case is when $n\equiv 0(mod2)$,$n>2$. We have $n^{n-1}(n^{(k-1)n}-k^n)\equiv n^{n-1}(n^{(k-1)n}-1)(mod (k+1))$. Condition $m>n^n$ implies $k>n^{n-1}$.But since $p|n-1$ $\implies$ $(p,n)=1$ and $p|n^{(k-1)n}-1$ where $p$ is some prime. We see that $k+1=pn^{n-1}$ works, where $p$ is prime divisor of $n-1$. So for $n>2$ even $\boxed{m=(pn^{n-1}-1)n}$ where $p$ is prime divisor of $n-1$. For $n=2$,$m=5$ works.

Wolowizard wrote: Very nice problem although easy. My solution: What is your solution? Mine is: For odd $n $ we take $m=2n^n-n$, and for $n $ even, we take $m=(n-1)n^n $. It's not so hard to prove that these accualy work. The number is positive as $a^b >b^a $ for $b>a>2$, and we just have to find solution for $n=2, m=10$ for example.

Very nice solution. Also $n=2$, $m=5$ Works fine. For $n$ even just use $m= n^{np+1}-2n$ where $p$ Is a prime factor in $n^n-3$. For $n$ odd use $m=q \cdot n^n-n$ where $q$ is a prime factor of $n^{n^n-2n}-1$. Little Fermat theorem does the job.

My solution: Let $m=(n-1)n^n-n$ with $n>2$ $\Longrightarrow$ $m>n^n$ and $m+n=(n-1)n^n$, but it is easy to see that $n^n|n^m$ and $n^n|m^n$ $\Longrightarrow$ $n^n|{n^m-m^n}...(\star)$ Also that $n^m\equiv (-1)^m\pmod {n-1}$ and $m^n\equiv (-1)^n\pmod {n-1}$ since $m\equiv n\pmod 2$ we get $(-1)^m\equiv (-1)^n\pmod {n-1}$ $\Longrightarrow$ $n-1|n^m-m^n...( \star\star)$. Since $n-1$ and $n^n$ are coprime and combining $(\star)$ and $(\star\star)$ we get $(n-1)n^n|n^m-m^n$ $\Longrightarrow$ $m+n|n^m-m^n$ for all $n>2$ and $n^m-m^n$ is a positive since $m^n >n^m$ for $m>n>2$ For $n=2$ we choose $m = 5>2^2$ since $2+5|2^5-5^2$. Hence for all $n>1$ exist $m>n^n$ such that $\frac {n^m-m^n}{m+n} $ is a positive integer.

FabrizioFelen wrote: My solution: Let $m=(n-1)n^n-n$ why $m=(n-1)n^n-n$ can you explain for me?

FabrizioFelen wrote: Also that $n^m\equiv (-1)^m\pmod {n-1}$. This is incorrect for odd m and $ n>3 $ since $ n\equiv1\pmod {n-1} $.

$m=n^{n+1}-n-1$ also works for the even case: $$n^{n+1}-2n-1\equiv(-1)^{n+1}-2n-1\equiv-2n-2\equiv0\pmod{n+1}$$which means $n+1$ divides $n^{n+1}-2n-1=m-n$, and so $n^{n+1}-1=m+n$ divides $n^{m-n}-1$. $$n^{m-n}-1\equiv0\pmod{m+n}\implies n^m-n^n\equiv0\pmod{m+n}\implies n^m-m^n\equiv0\pmod{m+n}$$