# Show that there are infinitely many solutions of distinct natural numbers $m,n$ such that $n^3+m^2\mid m^3+n^2$

Show that there are infinitely many solutions of distinct natural numbers $m,n$ such that $n^3+m^2\mid m^3+n^2$.

This question appeared in Round $2$ of British Math Olympiad $2007-08$. I have been trying this problem since two days. And got no sequence of numbers satisfying it.

-
This solution (thestudentroom.co.uk/showthread.php?t=1878411) is similar (if not identical) to the current one. I am still expecting something more intuitive –  lab bhattacharjee Jul 1 '13 at 16:03
@labbhattacharjee: I believe parametric form $n^5-n^2-1$ and $k=n^3-1$ is the smallest of a kind. I'm guessing there are more polynomials $p(n) \text{ and } q(n)$ for which it is true. Thanks for the link, btw. –  Inceptio Jul 2 '13 at 15:28
@labbhattacharjee I've added an intuitive explanation, and another family of solutions. –  Calvin Lin Jul 5 '13 at 16:51

Choose $a\in\mathbb{N}$, and set $m=an$. Then the condition becomes $n^3+a^2n^2|a^3n^3+n^2$, which is equivalent to $$n+a^2|a^3n+1$$

We now set $n=a^5-a^2-1$ and see that $$(a^3-1)(n+a^2)=(a^3-1)(a^5-1)=a^8-a^5-a^3+1=a^3n+1$$

Update, pulling back the veil: I looked for $k$ such that $k(n+a^2)=a^3n+1$ and I could solve for $n$. After one or two false attempts I tried $k=a^3-1$.

-
Wow! Was there anything in particular that led you to set $n$ to $a^5-a^2-1$? –  Milind Jul 1 '13 at 15:07
I recognized that $(m,n)=n$. I couldn't move anywhere after $n+k^2|k^3n+1$. Awesome observation(+1) –  Inceptio Jul 1 '13 at 15:13
@MilindHegde Here's an easier way to motivate the work (as a reasonable attempt during the competition). We want $n + a^2 | a^3n + 1$, which gives us $n+a^2 | a^3n + a^5 - a^5 + 1$, hence $n+a^2 | a^5 - 1$. An obvious try is $n = a^5 - a^2 - 1$. Another is $a^4 + a^3 + a + 1$. The rest do not work well. –  Calvin Lin Jul 5 '13 at 16:39

As Vadim showed, with $m=an$ yields

$$n + a^2 | a^3 n + 1$$

This implies that

$$a^5 - 1 \equiv a^5 + a^3 n - a^3n - 1 \equiv 0 \pmod{a^2 + n}$$

This suggests immediately to use $n = a^5 - a^2 - 1$, as in Vadim's solution. The advantage is that I don't need to do any guesswork, or expand the product.

In fact, since $a^5 - 1 = (a-1)(a^4+a^3+a^2+a+1)$, we could also use

$$n = a^4 + a^3 + a + 1$$

This also shows you how to characterize all solutions. Start with any positive integer $a$, calculate the factors of $a^5-1$ that are greater than $a^2$, and that determines the value of $n$.

Note: Because we want $n$ to be positive, none of the other factors (with integer coefficients) will work to generate a family of solutions.

-