Divisibility - Math Olympiad: $x|(y^2+m)$ and $y|(x^2+m) $

I lead off by settling the case $m=1$ by applying a technique from an old answer by Bill Dubuque. Only posting this, because I think this has useful, generalizable ideas (but won't take us the distance).

We observe that $(x,y)=(5,2)$ is a solution. In our case $m=1$ we can painlessly conclude that $\gcd(x,m)=\gcd(y,m)=1$. Therefore also $\gcd(x,x^2+m)=\gcd(y,y^2+m)=1$. Therefore the conditions ii)- iii) can be combined to read (keeping condition i) $$ xy\mid(x^2+1)(y^2+1), $$ which is equivalent to the requirement $$ xy\mid x^2+y^2+1. $$ Given that the single solution $(x,y)=(5,2)$ satisfies the equation $$ 3xy=x^2+y^2+1 \qquad(*) $$ we are lead to the conclusion that if equation $(*)$ has an infinite number of integer solutions (necessarily coprime), then that settles the claim in the case $m=1$.

Here's the key idea. If $(x,y)$ is a solution of $(*)$, then $(3x-y,x)$ is another. This follows immediately from the observation that for a fixed $x$ the two solutions for $y$ of the quadratic equation sum up to $3x$ (=the negative of the coefficient of the linear term). Using this recursively allows us to generate an infinite number of solutions: $$ (5,2)\mapsto (13,5)\mapsto (34,13)\mapsto (89,34)\mapsto\cdots $$

I leave it as an exercise for the reader to show that the numbers in this sequence also appear in the Fibonacci sequence.

To settle the general case we need a mechanism for finding a single solution $(x,y)$ such that both $x$ and $y$ are coprime to $m$. The above machinery most likely then spews out an infinite family of solutions.

Edit: $(x,y)=(1,1)$ should work as the initial solution as per suggestion by Ivan Loh! LOL :-) :D

We will also add the condition (4) that $ \gcd(xy , m) = 1$ (as pointed out by ThomasAndrews)

Observe that $ (x, y) = (m+1, (m+1)^2 + m) $ is a solution to the conditions.
Condition 1 is easy to verify.
Condition 2 is trivial.
Condition 3 follows easily. [You could also show that the polynomial $(m+1)$ is a factor of the polynomial $[ (m+1)^2 + m ] ^2 + m$ by substituting $m=-1$ to obtain $[ (-1 + 1)^2 + 1]^2 -1 = 0$ and applying the Remainder Factor Theorem.]
Condition 4 is trivial. Note: For $m=1$, we get $(x, y) = (2, 5)$.

We now proceed by Vieta's Root Jumping (as Jyrki suggested). Given any solution $(x, y)$, we know that $$xy \mid (x^2 + m)(y^2 + m) \Leftrightarrow xy \mid mx^2 + my^2 + m^2 \Leftrightarrow xy \mid x^2 + y^2 + m$$

Hence, there exists a $D$ such that $Dxy = x^2 + y^2 + m$.

Claim: $(y, Dx-y)$ is a another solution. You can either check this through algebraic manipulation, or realize that $Dx-y$ is the other integer root to the above equation (when viewed as a quadratic in $y$). Remember to check all the conditions.

As Ivan suggested, to show that we have distinct solutions, we will show that $x < y \Rightarrow y < Dy-x$, and thus the Veita jumping gives us a strictly increasing sequence. From the product of roots, we get that $(Dx-y) \times x = y^2 + m \geq y^2$. Hence, $x< y \Rightarrow Dy-x \geq \frac {y^2}{x} > \frac {y^2}{y} = y $.