When does a prime $p=m^2+n^2$ divide the term $ m^3+n^3-4$? I came across a math olympiad type question that goes like this:
For what primes $p$ will $p=m^2+n^2$ and $p$ divide $m^3+n^3-4$?
I tried a few examples and think that $p=5$ is the only solution but am unable to prove it. The property that $p \equiv 1 \mod 4$ seems to not be helpful so far. Any clues or solutions are welcome.

Not an answer!!! Work in progress.
We can use the Gaussian integers. Assume that $m^2 + n^2$ divids $m^3 + n^3 - 4$.
Note that $m^2 + n^2 = (m + in)(m - in)$, and since $m^2 + n^2$ is prime in $\mathbb{Z}$, both of these are prime in $\mathbb{Z}[i]$.
Additionally, by this result, as $m,n$ are relatively prime here, $\mathbb{Z}[i] / (m+in) \cong \mathbb{Z}/(m^2 + n^2) \mathbb{Z}$.
So we work in the field $\mathbb{Z}[i] / (m+in)$, getting
$$
m^3 + n^3 - 4 \equiv (-in)^3 + n^3 - 4 = (i+1)n^3 - 4 \equiv 0 \pmod{m+in}
$$
Thus
$$
(1+i) n^3 \equiv -4 =  -(1+i)^4 \pmod{m+in}.
$$
If $m = n = 1$, we have a solution $\boxed{p=2}$.
Otherwise, $1+i$ is not zero, and we divide by it to get
$$
n^3 = -(1+i)^3 \pmod{m+in}.
$$
So the question now is to solve a cubic in $\mathbb{Z}[i]/(m+in)$. It definitely has one solution, $n \equiv -(1 + i)$. It may have two other soutions, if $1$ has three cube roots in $\mathbb{Z}[i](m+in)$, which happens exactly when $m^2 + n^2 \equiv 1 \pmod{3}$ (see here).
If so, then there is a Gaussian integer $\omega$, $\omega \ne 1$, such that $\omega$ and $\omega^2$ are the two nontrivial cube roots of $1$ in $\mathbb{Z}[i] / (m+in)$. Otherwise, let $\omega = 1$.
Either way, we have $n \equiv -\omega^a (1+i) \pmod{m+in}$, for $a \in \{0,1,2\}$.
Using the isomorphism between $\mathbb{Z}[i]/(m+in)$ and $\mathbb{Z}[i]/(m-in)$ given by conjugation, of course $n \equiv -(\overline{\omega})^a (1-i) \pmod{m-in}$.
