Problem 30: Germany 2003 (PEN A, Problem 112)

by henderson, Jun 30, 2016, 11:09 AM

$\bf\color{red}Problem \ 30$ Prove that there exist infinitely many pairs $(a, b)$ of relatively prime positive integers such that $\frac{a^{2}-5}{b}\;\; and\;\; \frac{b^{2}-5}{a}$ are both positive integers.
$\bf\color{green}Solution \$ If true, then $\tfrac{a^2-5}{b},\tfrac{b^2-5}{a}\in \mathbb{Z}$ , so their product $\tfrac{(a^2-5)(b^2-5)}{ab}=\tfrac{a^2b^2-5a^2-5b^2+25}{ab}=ab-5\left(\tfrac{a^2+b^2-5}{ab}\right)$ is also an integer. Hence, it suffices to show that there are infinitely many integers $a,b$ for which $ab\mid (a^2+b^2-5).$

Consider the infinite sequence $-1,1,4,11,29,76,199,...$ defined by $a_0=-1$ , $a_1=1$ , and $a_{n+2}=3a_{n+1}-a_n\ \forall{n\ge{0}}.$

Now, let's quickly prove that $\gcd(a_n,a_{n+1})=1$ before moving into the main proof. Note that we have $a_n \mid a_{n+1}^2 - 5$ and $a_{n+1} \mid a_{n}^2 - 5,$ so it is clear that $\gcd(a_n, a_{n+1}) \mid 5.$ But modulo $5$ the sequence $(a_n)_{n\geq 0}$ is periodic, with period $-1,1,$ and so no term is divisible by $5.$ Hence $\gcd(a_n, a_{n+1}) = 1,$ as desired.
Now, let us prove the following claim.

$\color{blue}\textbf{Claim.}$ $a_n^2+a_{n+1}^2=3a_na_{n+1}+5.$

$\color{blue}\textbf{Proof.}$ It is clearly true when $n=0,$ which we get $a_0^2+a_1^2=(-1)^2+1^2=2=3(-1)(1)+5=3a_0a_1+5.$
Suppose the proposition works for $n=k,$ where $k\ge{0},$ i.e. $a_k^2+a_{k+1}^2=3a_ka_{k+1}+5.$

By definition, $a_{k+2}=3a_{k+1}-a_k$ . Adding $2a_{k+2}$ to both sides yields $3a_{k+2}=3a_{k+1}+2a_{k+2}-a_k.$ Multiplying both sides by $a_{k+1}$ yields $3a_{k+1}a_{k+2}=3a_{k+1}^2+2a_{k+1}a_{k+2}-a_ka_{k+1}.$ Adding 5 to both sides yields
$\begin{align*} 3a_{k+1}a_{k+2}+5 & =3a_{k+1}^2+2a_{k+1}a_{k+2}-a_ka_{k+1}+5\\ &=3a_{k+1}^2+2a_{k+1}a_{k+2}+3a_ka_{k+1}-4a_ka_{k+1}+5. \end{align*}$ By the induction hypothesis, $3a_ka_{k+1}+5=a_k^2+a_{k+1}^2$ , thus
$\begin{align*} & 3a_{k+1}^2+2a_{k+1}a_{k+2}+3a_ka_{k+1}-4a_ka_{k+1}+5 \\ &=a_k^2+a_{k+1}^2+3a_{k+1}^2+2a_{k+1}a_{k+2}-4a_ka_{k+1}\\ &=a_k^2+a_{k+1}^2+3a_{k+1}^2+2a_{k+1}a_{k+2}-4a_ka_{k+1}\\ &=a_k^2+4a_{k+1}^2+2a_{k+1}a_{k+2}-4a_ka_{k+1}.\ (\clubsuit) \end{align*}$
But we can also get $(\clubsuit)$ as follows.

By definition, $a_{k+2}=3a_{k+1}-a_k$ . Subtracting $a_{k+1}$ from both sides, squaring, then adding $2a_ka_{k+1}$ to both sides yields $a_k^2+a_{k+1}^2=a_k^2+4a_{k+1}^2+2a_{k+1}a_{k+2}-4a_ka_{k+1}.$ But this is just $(\clubsuit)$ , hence $\boxed{a_k^2+a_{k+1}^2=3a_ka_{k+1}+5}$ $\bf Q.E.D.$

Well, then, let $(a,b)=(a_{n+1},a_{n+2})=(a_{n+1},3a_{n+1}-a_n).$ Then,
$\begin{eqnarray*}\frac{a^2+b^2-5}{ab}&=&\frac{a_{n+1}^2+(3a_{n+1}-a_n)^2-5}{a_{n+1}(3a_{n+1}-a_n)}\\ &=&\frac{a_{n+1}^2+9a_{n+1}^2-6a_na_{n+1}+a_n^2-5}{a_{n+1}(3a_{n+1}-a_n)}\\ &=&\frac{3a_{n+1}(3a_{n+1}-a_n)+a_n^2+a_{n+1}^2-(3a_na_{n+1}+5)}{a_{n+1}(3a_{n+1}-a_n)}. \end{eqnarray*}$ But by the lemma, $a_n^2+a_{n+1}^2=3a_na_{n+1}+5\iff a_n^2+a_{n+1}^2-(3a_na_{n+1}+5)=0.$ Therefore,
$\begin{align*} & \frac{3a_{n+1}(3a_{n+1}-a_n)+a_n^2+a_{n+1}^2-(3a_na_{n+1}+5)}{a_{n+1}(3a_{n+1}-a_n)} \\ &=\frac{3a_{n+1}(3a_{n+1}-a_n)}{a_{n+1}(3a_{n+1}-a_n)}\\ &=3. \end{align*}$ Or, in other words, $\boxed{(a,b)=(a_{n+1},a_{n+2})}$ generates infinitely many pairs $(a,b)\in \mathbb{Z}$ for which $b\mid{a^2-5}$ and $a\mid{b^2-5},$ so we're done. $\square$