Number Theory Problem Germany 2003

contest-mathdivisibilityelementary-number-theoryproblem solvingvieta-jumping

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.

Best Answer

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.

Related Question