Determine all pairs of positive integers $(m, n)$ such that$$\frac{m^3+n^3}{m^2+n^2+m+n}$$is an integer.
This is a simpler version of a problem that I made a few years ago. There are infinitely many solutions. Such as parametric forms for $(m, n)$ that @Ivan Neretin has provided.
Let us consider $m>n$ due to symmetry (There is no solution for $m=n$). Let $m=ad$ and $n=bd$ for co-prime positive integers $a$ and $b$ and $a>b$. We get$$d^2(a+b)\big(a^2+b^2-ab\big)=k\big[d(a^2+b^2)+a+b\big]. \tag{1}$$
After @Geoff Robinson's first comment, I was looking for possible values of$$D=\gcd\big(m+n, m^2+n^2+m+n\big),$$which is$$D=\gcd\big(m+n, (m+n)^2-2mn+m+n\big)=\gcd(m+n, 2mn).$$and$$D=\gcd\big(d(a+b), 2d^2ab)=d \gcd(a+b, 2d).$$ Since $\gcd(a+b, ab)=1$.
Then I used equation $(1)$ and the relation between $d$ and $\gcd(a+b, 2d)$, for finding a relation between $d$ and $a+b$. I think it can be the key for solving the problem.
After looking at patterns using a code, I realized that actually there is a relation between $d$ and $a+b$. It is interesting that for most of the solutions we get $\gcd(a+b, 2d)=2d$ and $\frac{d}{a+b}=\frac{1}{4}$.
I'll summarise progress here to prevent the comments becoming hard to read. I have made this community wiki, so feel free to add any progress made.
Parametric solutions found (by Ivan Neretin): $$\begin{align}m = k(2k+1), &\quad n=k(2k-1) \\ m = k(k-1)(k^2+k-1), &\quad n=k(k-1)(k+1)\end{align}$$ Solutions found outside of the above patterns (covers all solutions for $n \leq m \leq 2300000$):
Necessary conditions (by Geoff Robinson): Either $m$ and $n$ share a common factor, or they are both odd. If they are both odd, then $m+n \equiv 0$ mod $4$.
Moreover, $m$ and $n$ have the same parity. Proof: The denominator $B=m^2+n^2+m+n$ is even. The numerator $T=m^3+n^3$ is a multiple of $B$, so is even, so $m^3$ and $n^3$ have the same parity, so $m$ and $n$ have the same parity.
This means that if $d$ is odd, $a$ and $b$ are odd. I (Rosie F) notice that in most cases $d$ is even. But it is quite rare that either $a$ or $b$ is even.
We also can remark that the only coprime solution is $(m,n)=(3,1)$. To show this assume $(m,n)=1$. Also note that $m^3+n^3=(m+n)(m^2+n^2-mn)$, so the original quantity is an integer iff $$m^2+n^2+m+n\mid (m+n)(m+n+mn)$$ Of course this is true iff $m^2+n^2+m+n\mid \gcd(m^2+n^2+m+n, m+n)(m+n+mn)$, which simplifies to $m^2+n^2+m+n\mid \gcd(m+n, 2mn)(m+n+mn)$. Much like Geoff noted, this can only be the case when $\gcd(m+n, 2mn)>1$ since $m^2+n^2+m+n>m+n+mn$. However under the assumption that $\gcd(m,n)=1$, this is only the case when $m$ and $n$ are both odd and $\gcd(m+n, 2mn)=2$. Hence our original quantity is an integer only if $$m^2+n^2+m+n\mid 2(m+n+nm)$$ and $m$ and $n$ are odd. Assume $m^2+n^2+m+n\neq 2(m+n+nm)$, then for some prime $p$, $m^2+n^2+m+n\mid 2(m+n+nm)/p$ and thus $$m^2+n^2+m+n\le 2(m+n+nm)/p\le m+n+nm$$ which is false. Hence $m^2+n^2+m+n=2(m+n+nm)$ and $(m-n)^2=n+m$. This gives $m-n\mid n+m$ so $$m-n=\gcd(m-n,n+m)=\gcd(m+n, 2m)=2$$ Thus $m=n+2$. Subbing this into $(m-n)^2=m+n$ gives $(m,n)=(3,1)$. Thus if $\gcd(m,n)=1$ we must have $(m,n)=(3,1)$, which if we test works.