Show that for any positive integer $m$, there is an infinite number of pairs of integers $(x,y)$ satisfying the conditions:

i) $\gcd(x,y)=1$;

ii) $y \mid x^2+m$;

iii) $x \mid y^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

-
So, just to prove that $x^2+y^2+m=dxy$ has infinite comprime solutions, for any $d$... How to do this? – leticia Mar 15 '13 at 22:59
@Jyrki Lahtonen $(x,y)=(1,1)$ works... – Ivan Loh Mar 16 '13 at 0:13
This method is also known as Vieta Jumping In this case, we are not looking for a contradiction. Rather, we descend to the base case, then reverse the descent to get all solutions. So in fact you have found all positive integer solutions, assuming you start with $(1,1)$. – Ivan Loh Mar 16 '13 at 0:20
@leticiamat If you read the history of Vieta jumping at the link I provided above, this method was introduced to Olympiad mathematics via IMO 1988 Q6. It has since become a standard technique for solving such Olympiad number theory questions, so this is probably how you are meant to solve it. – Ivan Loh Mar 16 '13 at 0:27
@Ivan: Thanks for the link. I would suggest that the techniques was useful already at IMO1981 (Georgetown), when the equation $(m^2-mn-n^2)^2=1$ was studied. Then the sequence of solutions was formed by pairs of consecutive Fibonacci numbers. Don't remember the number of the question, but "I was there!" – Jyrki Lahtonen Mar 16 '13 at 5:37

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$.

-
(+1) but can't you just start with $(1,1)$? Take $x \leq y$ so since the product of roots is $y^2+m \geq x^2+1$ the other root is bigger. – Ivan Loh Mar 16 '13 at 0:51
Of course you can, and you can get to $(1, 1)$ by 'backwards' Vieta jumping. I actually started off with $(1, 1)$ and got $(1, m+1)$ and then $(m+1, m^2+3m+1)$. – Calvin Lin Mar 16 '13 at 0:59
there's one step you assume $(xy,m)=1$. It's true, but don't you have to prove that it is true that $(Dx-y,m)=1$? Specifically, when you have $xy|(x^2+m)(y^2+m)$ and deduce that $xy|(x^2+y^2+m)$ you are using that $(xy,m)=1$. – Thomas Andrews Mar 26 '13 at 14:28
@ThomasAndrews Agreed. Will edit. – Calvin Lin Mar 26 '13 at 15:24
Also, isn't $Dx-y = \frac{x^2+m}{y}$? If so, how is $(Dx-y)\times x = y^2 +m$? Should that be $(Dx-y)\times y = x^2 + m$? – Thomas Andrews Mar 26 '13 at 15:28