Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
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 $.

share|cite|improve this answer
(+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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.