Find all integers $m,\ n$ such that $m^2+4n$ and $n^2+4m$ are both squares.

We will prove that @David G.’s set of solutions is complete.

We can suppose without loss of generality that $|m|\geq|n|$, as the system of equations is symmetric in both variables. For every solution $(m,n)$ that we find, $(n,m)$ will be valid too.

We separate the problem into four cases:


If $\mathbf{n>0}$:

$$\left(|m|+2\right)^2>m^2+4n>\left(|m|\right)^2,$$ so that $$m^2+4n=\left(|m|+1\right)^2\Rightarrow$$ $$4n=2|m|+1.$$ This is, however, impossible, as both sides have distinct parities.


If $\mathbf{n=0}$:

$4m$ must be a square, so that $m$ is a square too. It’s then easy to see that $\boxed{(k^2,0)}$ is a solution for any $k\in\mathbb N_0$.


If $\mathbf{-4\leq n\leq -1}$:

We know that $m^2$ must be either $4$, $8$, $12$ or $16$ more than a square ($m^2+4n$). It’s easy to find all pairs of squares with a certain difference, by using $$x^2-y^2=d\Leftrightarrow$$ $$(x-y)(x+y)=d,$$ and going through all factors of $d$. In this manner, we arrive at the following candidates for $(m,n)$: $$(-2,-1),\,(2,-1),\,(-3,-2),\,(-3,2),\,(-4,-3),\,(-4,3),\,(-4,-4),\,(4,-4),\,(-5,-4),\,(5,-4).$$ From these, the ones that work are $$\boxed{(2,-1),\,(3,-2),\,(4,-3),\,(5,-4),\,(-4,-4)}.$$


If $\mathbf{n\leq-5}$:

We have $$\left(|m|-3\right)^2\leq m^2+6n+9<m^2+4n<\left(|m|\right)^2.$$ This leaves two possibilities. If $$m^2+4n=\left(|m|-1\right)^2,$$ we get that $$4n=-2|m|+1,$$ which leaves us with the same contradiction from earlier. Therefore, $$m^2+4n=\left(|m|-2\right)^2\Rightarrow$$ $$4n=4-4|m|\Rightarrow$$ $$m\in\{1-n,n-1\}.$$ $n^2+4m$ must also be a square. In the former case, this implies $n^2-4n+4$ to be a square, and in the latter, ditto with $n^2+4n-4$. The former expression is the square $(n-2)^2$, while the latter is $8$ less than the square $(n+2)^2$. Using the method from our previous case, it’s easy to prove that the only two squares at distance $8$ are $1$ and $9$. In total, this case gives the solutions $\boxed{(k+1,-k)}$ for $k\geq5$, and the solution $\boxed{(-6,-5)}$ (which are easy to check).

$\blacksquare$


I've found several infinite families of solutions. For any integer $k$ :

  • $m=k$ and $n=1-k$
  • $m=k^2$ and $n=0$
  • $m=0$ and $n=k^2$

Additionally, I've found:

  • $m = -4$ and $n = -4$
  • $m = -6$ and $n = -5$
  • $m = -5$ and $n = -6$