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?
 A: There are no primes with this property other than $p=2$ and $p=5$; here is a proof.
Suppose that $m,n>1$ and $p=m^2+n^2$ is a prime dividing $m^3+n^3-4$. As you have observed, we have then 
  $$ mn(m+n) \equiv -4 \pmod p. $$ 
We apply two operations to this congruence: squaring and multiplying by $m+n$; keeping in mind that $(m+n)^2\equiv 2mn\pmod p$, this gives
\begin{align*}
  2m^3n^3 &\equiv 16\pmod p, \\
  2m^2n^2 &\equiv -4(m+n)\pmod p;
\end{align*}
that is,
\begin{align*}
  m^3n^3 &\equiv 8\pmod p, \tag{1} \\
  m^2n^2 &\equiv -2(m+n)\pmod p. \tag{2}
\end{align*}
In view of $m^3n^3-8=(mn-2)(m^2n^2+2mn+4)$, from (1) we conclude that either $mn\equiv 2\pmod p$, or $m^2n^2+2mn+4\equiv 0\pmod p$. In the former case (2) leads to $p\mid m+n+2$, and as a result to $p=m^2+n^2\le m+n+2$, which is easily seen to be possible only if $m=2$ and $n=1$, or vice versa, contradicting the assumption $m,n>1$. Suppose thus that
  $$ m^2n^2+2mn+4\equiv 0\pmod p. $$
Combined with (2), this gives
  $$ m+n \equiv mn+2\pmod p, $$
whence 
  $$ p = m^2+n^2 \le mn-m-n+2. $$
But, recalling that $m,n>1$,
  $$ m^2+n^2 \ge 2mn = mn - m - n + 2 + ((m+1)(n+1) - 3) > mn -m -n + 2, $$
a contradiction.
A: 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.
