Prime numbers of the form $p=m^2+n^2$ such that $p \mid m^3+n^3-4$ 
Find all prime numbers $p$, for which there are positive integers $m$ and $n$ such that $p=m^2+n^2$ and $p \mid m^3+n^3-4$.

I simplified this a little bit.
$$m^2+n^2 \mid m^3+n^3-4 =(m+n)(m^2+n^2-mn)-4 \\ \Longrightarrow m^2+n^2 \mid (m+n)mn+4 $$
The only case that $m$ and $n$ can both be odd is $m=n=1$, which leads to $p=2$. If one of $m$ and $n$ is $1$ (For example $n=1$), then $p=m^2+1$ and 
$$m^2+1 \mid m^2+m+4 \Longrightarrow m^2+1 \mid m+3 \Longrightarrow m=2$$
Which gives $p=5$.
For $m,n>1$ with different parity, I could not find a strong argument. Can you guys give it a try?

This problem is from 2004 Silkroad Mathematical Competition. By the way, if you are into this problems, I think you should really visit AoPS forums, audience here at stack exchange are not very experienced with olympiadic problems.
Here is a short reasoning (similar to above). Check that, $p=2,5$ indeed works. Suppose now $p>5$. Note that, $m^3+n^3=(m+n)(m^2-mn+n^2)$. Notice that, $m^2-mn+n^2\equiv -mn\pmod{p}$. This yields, $p\mid mn(m+n)+4$. Next, note also that, $p=m^2+n^2$ implies, $(m+n)^2\equiv 2mn\pmod{p}$, and thus, $mn\equiv \frac{(m+n)^2}{2}\pmod{p}$. This yields, $p\mid (m+n)^3+8=(m+n+2)((m+n)^2+2(m+n)+4)$. Now, if $p\mid m+n$, we have $m^2+n^2\mid m+n$ with $m,n$ not simultaneously one, which is not sound. Similarly, if $p\mid m^2+2mn+n^2+2(m+n)+4$, then note that, $p\mid 2mn+2(m+n)+4$, or equivalently, $p\mid mn+m+n+2$, since $p>2$. This yields $m^2+n^2\leq mn+m+n+2$. Now, using AM-GM inequality, we also have $m^2+n^2\geq 2mn$, which implies, $mn-m-n+1\leq 3$, that is, $(m-1)(n-1)\leq 3$. In particular, either $(m-1)(n-1)=1$, which is not possible, or $(m-1)(n-1)=2$, yielding $m=3,n=2$, and $p=13$, for which the condition does not hold, or $(m-1)(n-1)=3$, yielding $m=4,n=2$, for which, again, $m^2+n^2$ is not prime.
