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