1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Have you tried: $a^2\equiv 5\pmod{b}\;\&\;b^2\equiv 5\pmod{a}$ ? $\endgroup$
    – PinkyWay
    Mar 5, 2020 at 13:08
  • 2
    $\begingroup$ 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). $\endgroup$ Mar 5, 2020 at 16:08

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ How did you arrive at $ab | a^2+b^2-5 $ $\endgroup$
    – h-squared
    Mar 5, 2020 at 15:24
  • 2
    $\begingroup$ 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$. $\endgroup$ Mar 5, 2020 at 15:57
  • $\begingroup$ How did you deduce that, maybe I am not understanding a step $\endgroup$
    – h-squared
    Mar 5, 2020 at 15:57
  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 5, 2020 at 16:04
  • 1
    $\begingroup$ 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$. $\endgroup$ Mar 5, 2020 at 16:04
1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Note: Entering these numbers into OEIS also gave some hints as to how these numbers can come about. $\endgroup$
    – Arthur
    Mar 5, 2020 at 13:40
  • 1
    $\begingroup$ But you don't have OEIS on contest... :( $\endgroup$
    – nonuser
    Mar 5, 2020 at 13:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arthur
    Mar 5, 2020 at 13:57
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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}$$ $\endgroup$ Mar 5, 2020 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .