Silk Road Mathematics Competition

Considering all integers $|m|,|n|\le 3$ we can get the solutions $2=1^2+1^2$, $5=1^2+2^2$ and $13=(-3{)}^2+(-2{)}^2$. Now, let's prove that there is no other prime numbers satisfying the statement. We have $$p=m^2+n^2\Rightarrow p=(m+n{)}^2-2mn\Rightarrow mn=\frac{(m+n{)}^2-p}{2},$$ $$m^3+n^3-4=(m+n{)}^3-3mn(m+n)-4=\frac{-(m+n{)}^3+3p(m+n)-8}{2},$$ $$p\mid m^3+n^3-4\Rightarrow p\mid (m+n{)}^3+8.$$ Hence, $p\mid m+n+2$ or $p\mid (m+n{)}^2-2(m+n)+4$, and from last we conclude that $p\mid mn-m-n+2$, if we set $p>2$. In a first case we have: $$p\mid m+n+2\Rightarrow m^2+n^2\le |m+n+2|,$$ i.e. $$m^2+n^2\le m+n+2\Rightarrow (2m-1{)}^2+(2n-1{)}^2\le 10\Rightarrow -1\le m,n\le 2.$$ $$m^2+n^2\le -(m+n+2)\Rightarrow (2m+1{)}^2+(2n+1{)}^2\le -6,$$ which is a contradiction. In a second case: $$p\mid mn-m-n+2\Rightarrow m^2+n^2\le |mn-m-n+2|,$$ i.e. $$m^2+n^2\le mn-m-n+2\Rightarrow (2m-n+1{)}^2+3(n+1{)}^2\le 12\Rightarrow -3\le m,n\le 1.$$ $$m^2+n^2\le -(mn-m-n+2)\Rightarrow (2m+n-1{)}^2+3(n-1/3{)}^2\le -20/3,$$ which is a contradiction.