# Number Theory Problem Germany 2003

Prove that there exist infinitely many pairs $$(a,b)$$ of relatively prime positive integers such that $$\frac{a^2-5}{b}, \frac{b^2-5}{a}$$ are both positive integers.

I saw that this problem came from Germany 2003, but was unable to find a corresponding solution online. I tried performing casework on $$a$$ and $$b\mod 4$$, but came up with nothing.

• Have you tried: $a^2\equiv 5\pmod{b}\;\&\;b^2\equiv 5\pmod{a}$ ? Mar 5, 2020 at 13:08
• This a a prototypical "Vieta jump" problem. If you search with that buzzword here and on AoPS you will find many worked examples using this method (likely including this specific case). Mar 5, 2020 at 16:08

Hint. Show the infinitude of positive integer solutions $$(a,b)$$ to the divisibility condition $$ab\mid a^2+b^2-5$$. In fact, for a positive integer $$k$$, there exists $$(a,b)\in\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}$$ such that $$a^2+b^2-5=kab\tag{*}$$ if and only if $$k=3$$, in which case there are infinitely many choices of $$(a,b)$$. When $$k=3$$, amongst the positive integer solutions $$(a,b)$$ such that $$a\geq b$$, the smallest of which is $$(a,b)=(4,1)$$.

The idea is the technique known as Vieta jumping. If you do this correctly, then you will see that all positive integer solutions $$(a,b)$$ with $$a\geq b$$ to (*) with $$k=3$$ are of the form $$(a,b)=(x_n,x_{n-1})$$ for some positive integer $$n$$, where $$(x_n)_{n=0}^\infty$$ are given by $$x_0=1$$, $$x_1=4$$, and $$x_n=3x_{n-1}-x_{n-2}$$ for every integer $$n\geq 2$$. Here is a closed form of $$\left(x_n\right)_{n=0}^\infty$$: $$x_n=\left(\frac{1+\sqrt5}{2}\right)^{2n+1}+\left(\frac{1-\sqrt5}{2}\right)^{2n+1}=L_{2n+1}$$ for all $$n=0,1,2,\ldots$$, where $$(L_r)_{r=0}^\infty$$ is the sequence of Lucas numbers. The first few terms of $$(x_n)_{n=0}^\infty$$ are $$1,4,11,29,76,199,521,1364,3571,9349,24476,\ldots\,.$$ Compare the list above with the answer by Arthur.

• How did you arrive at $ab | a^2+b^2-5$ Mar 5, 2020 at 15:24
• For relatively prime positive integers $a$ and $b$, $a\mid b^2-5$ and $b\mid a^2-5$ if and only if $ab\mid a^2+b^2-5$. Mar 5, 2020 at 15:57
• How did you deduce that, maybe I am not understanding a step Mar 5, 2020 at 15:57
• I think you replied to quickly to really spend time thinking about it, but here we go. Suppose that $a\mid b^2-5$ and $b\mid a^2-5$. Then, $a\mid a^2+b^2-5$ because $a^2+b^2-5=a^2+(b^2-5)$, where $a^2$ and $b^2-5$ are both multiples of $a$. Similarly, $b\mid a^2+b^2-5$. Because $a$ and $b$ are relatively prime, the conditions $a\mid a^2+b^2-5$ and $b\mid a^2+b^2-5$ mean that $ab\mid a^2+b^2-5$. Mar 5, 2020 at 16:04
• Conversely, assume that $ab\mid a^2+b^2-5$. Then, $a\mid a^2+b^2-5$. This means $a\mid b^2-5$ because $b^2-5=(a^2+b^2-5)-a^2$, in which both $a^2+b^2-5$ and $a^2$ are multiples of $a$. Similarly, $b\mid a^2-5$. Mar 5, 2020 at 16:04

Partial answer: After writing a quick program that checks for solutions, I found, among others, the following pairs that work: $$4, 11\\ 11, 29\\ 29, 76\\ 76, 199\\ 199, 521\\ 521, 1364$$ They seem like a chain of pairs, each constructed from the previous pair in some way.

To see that these do indeed work, note that we have $$\frac{4^2 - 5}{11} = 1, \quad \frac{11^2-5}4 = 29\\ \frac{11^2 - 5}{29} = 4, \quad\frac{29^2-5}{11} = 76\\ \frac{29^2-5}{76} = 11, \quad \frac{76^2 - 5}{29} = 199$$ Hang on a moment. This looks like a really big coincidence. Let's put words on it, and then see if we can't prove that it is true:

Given a pair $$a, b$$ that fulfills the criteria of the problem, the pair $$b, \frac{b^2 - 5}{a}$$ also fulfills the criteria of the problem.

We check: $$\cfrac{b^2-5}{\frac{b^2-5}a} = a$$ is clearly an integer. I'm stuck at the other one: $$\frac{\left(\frac{b^2-5}a\right)^2 - 5}b$$

• Note: Entering these numbers into OEIS also gave some hints as to how these numbers can come about. Mar 5, 2020 at 13:40
• But you don't have OEIS on contest... :( Mar 5, 2020 at 13:42
• @Aqua But you do when trying to squeeze out a solution 17 years later. But the Lucas numbers is a famous enough sequence that someone could recognize it during a contest. I did, however, leave it as a comment, not as a part of the answer for the exact reason that you mention. Mar 5, 2020 at 13:57

This is from Batominovski's anwer, make this CW. Worth remembering

Suppose we have constant integers $$V,W$$ and nonzero integer variables $$x,y$$ with the requirement that we always have $$\gcd(x,y) = 1.$$ Given the two conditions $$x \;| \; y^2 + Ty + U \; , \;$$ $$y \; | \; x^2 + Vx + U \; , \;$$ then $$xy \; | \; \mbox{stuff}$$

Proof: First, since $$x \; | \; x^2 + Vx,$$ we get $$x \; | \; x^2 + Vx + y^2 + Ty + U \; , \;$$ or $$x \; | \; x^2 + y^2 + Vx + Ty + U \; . \;$$

Second, since $$y \; | \; y^2 + Ty,$$ we get $$y \; | \; y^2 + Ty + x^2 + Vx + U \; , \;$$ or $$y \; | \; x^2 + y^2 + Vx + Ty + U \; . \;$$

As $$x,y$$ are coprime, we reach $$xy \; | \; x^2 + y^2 + Vx + Ty + U \; . \;$$ To reverse is easier, given that $$xy$$ divides the thing, ignore the $$y$$ on the left side and erase the $$x$$ terms on the right side, we get back to the condition on $$x.$$ This also repeats the need for matching constant terms.

So far, it appears that the constant terms must match. I kept the coefficients 1 on $$x^2, y^2$$ since that is traditional for Vieta questions. This all generalizes to quadratic forms.

• This follows trivially by CRT as I explained in comments on Batominovski's answer. Here we get \large \begin{align}z-u&\equiv\, y(y+t)\pmod{x}\\ z-u&\equiv\, x(x\!+\!v)\!\pmod{y}\end{align}\iff z-u\equiv x(x\!+\!v)+y(y\!+\!t)\pmod{xy} Mar 5, 2020 at 19:45