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.
 A: Sorry for waking up old post...
Anyway, I think the following works.
Since $p\mid m(m^2+n^2)$ and $p\mid n(m^2+n^2)$ we have $p|3(m^3+m^2n+n^2m+n^3)$ Since \begin{align}3(m^3+m^2n+n^2m+n^3)&=(m+n)^3+2(m^3+n^3)\\&=(m+n)^3+8+ 2(m^3+n^3-4)\end{align}
we obtain $p|(m+n)^3+8$，while $$(m+n)^3+8=(m+n+2)(m^2+n^2+2mn-2m-2n+4)$$
Since $p$ is prime, it divides one of the factors.
The case $p|(m+n+2)$ is easily dealt and gives $p=2,5$.
The latter case reduces to $p|2(mn-m-n+2)$, and to $p|(mn-m-n+2)$ if $p\neq 2$.
Now $m^2+n^2\leq mn-m-n+2$, but $m^2+n^2\geq 2|mn|$, so some simple comparison gives the only possibility $m=-2,n=-3,p=13$.
Hence the answer $p=2,5,13$.
A: 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}$.
