Kvant Math Problem 1225
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m30s
Source on kvant.digital
Problem
Prove that:
- if for natural numbers $a$ and $b$ the number $\dfrac{a^2+b^2}{ab-1}$ is a natural number, then it is equal to 5;
- the equation $x^2-5xy+y^2+5=0$ has infinitely many solutions in natural numbers.
S. Mamikonyan, G. Oganesyan
Exploration
Let
$$\frac{a^2+b^2}{ab-1}=n,$$
where $n$ is a natural number. Then
$$a^2+b^2=nab-n.$$
The statement claims that necessarily $n=5$.
A few small examples suggest this. If $a=b=2$, then
$$\frac{4+4}{4-1}=\frac83$$
is not integral. If $a=1$, then
$$\frac{1+b^2}{b-1}=b+1+\frac2{b-1},$$
which is integral only for $b=2,3$, giving values $5$ and $5$. Also,
$$(a,b)=(2,5)$$
gives
$$\frac{4+25}{10-1}=\frac{29}{9},$$
while
$$(a,b)=(2,8)$$
gives
$$\frac{68}{15}.$$
The pair $(1,2)$ already yields the value $5$.
The equation
$$a^2+b^2=nab-n$$
is quadratic in $a$. Treating $b$ and $n$ as fixed, the two roots are
$$a,\qquad a'=nb-a.$$
This is the standard Vieta jumping situation. If a solution exists for some $n$, replacing $a$ by $a'=nb-a$ produces another integer solution. The crucial issue is to show that for $n\neq5$ one can descend to a smaller positive solution, eventually reaching an impossibility.
Suppose $(a,b)$ is a positive solution with $a\ge b$. Then
$$a^2-nab+b^2+n=0.$$
The other root is $a'=nb-a$. Since
$$aa'=b^2+n,$$
the new root is positive. If $n\ge6$, then from
$$a^2+b^2=nab-n<nab$$
we obtain
$$a>\frac{n-\sqrt{n^2-4}}2,b.$$
The quantity on the right exceeds $\frac1n b$, hence
$$a'>nb-a<\frac1n b.$$
Since $a'$ is a positive integer, $a'<b$. Thus Vieta jumping produces a strictly smaller positive solution. Minimality then forces $b=1$, and direct substitution yields
$$a^2-na+(n+1)=0.$$
Its discriminant is
$$(n-2)^2-8,$$
which is never a square for $n\ge6$. Hence no solutions exist for $n\ge6$.
For $n=1,2,3,4$ one checks separately that no positive solutions exist. Thus only $n=5$ remains.
For the second part, the equation is
$$x^2-5xy+y^2+5=0,$$
equivalently
$$x^2+y^2=5xy-5.$$
This is exactly the first equation with $n=5$. One solution is $(1,2)$. Applying the Vieta transformation
$$(x,y)\mapsto (5y-x,y)$$
preserves the equation. Starting from $(1,2)$ gives
$$(1,2),\ (9,2),\ (9,43),\ldots$$
and produces infinitely many distinct positive solutions.
The step most likely to conceal an error is the proof that for $n\ge6$ the new root satisfies $0<a'<b$, because the whole descent argument depends on it.
Problem Understanding
We must prove two statements.
First, if
$$\frac{a^2+b^2}{ab-1}$$
is a natural number for natural numbers $a,b$, then that number must equal $5$.
Second, we must show that
$$x^2-5xy+y^2+5=0$$
has infinitely many solutions in natural numbers.
This is a Type B problem. The task is to prove the stated assertions.
The core difficulty is the classification in the first part. After introducing
$$n=\frac{a^2+b^2}{ab-1},$$
one must show that no positive integer value of $n$ except $5$ can occur. The natural tool is Vieta jumping: the equation
$$a^2+b^2=nab-n$$
is quadratic in either variable and generates new integer solutions.
Proof Architecture
Let
$$a^2+b^2=nab-n.$$
Lemma 1. For fixed $b$ and $n$, if $a$ is a solution then $a'=nb-a$ is also an integer solution; this follows from Vieta's formulas for the quadratic equation in $a$.
Lemma 2. If $n\ge6$ and $(a,b)$ is a positive solution with $a\ge b$, then the companion root satisfies $0<a'<b$; this follows from the inequalities obtained from $a^2+b^2<nab$.
Lemma 3. No positive solutions exist for $n\ge6$; choose a solution with minimal larger coordinate and apply Lemma 2 to obtain a smaller one, then derive a contradiction from the case $b=1$.
Lemma 4. The equations corresponding to $n=1,2,3,4$ have no positive solutions; each case is eliminated by a simple estimate.
Lemma 5. The value $n=5$ does occur, for example at $(a,b)=(1,2)$.
The hardest direction is proving that every solution with $n\ge6$ descends to a strictly smaller positive solution. Lemma 2 is the point most likely to fail under scrutiny.
Solution
Let
$$n=\frac{a^2+b^2}{ab-1}.$$
Since $n$ is a natural number,
$$a^2+b^2=n(ab-1),$$
or
$$a^2+b^2=nab-n. \tag{1}$$
We must show that $n=5$.
Assume first that $n\ge6$. Let $(a,b)$ be a positive solution of (1), and suppose $a\ge b$.
Regard (1) as a quadratic equation in $a$:
$$a^2-nba+(b^2+n)=0. \tag{2}$$
One root is $a$. By Vieta's formulas the second root is
$$a'=nb-a,$$
and
$$aa'=b^2+n. \tag{3}$$
Hence $a'>0$.
From (1),
$$a^2+b^2=nab-n<nab.$$
Dividing by $b^2$ and writing $t=a/b$ gives
$$t^2-nt+1<0.$$
The roots of $t^2-nt+1=0$ are
$$\frac{n\pm\sqrt{n^2-4}}2.$$
Therefore
$$t>\frac{n-\sqrt{n^2-4}}2. \tag{4}$$
Since
$$\frac{n-\sqrt{n^2-4}}2 =\frac{2}{n+\sqrt{n^2-4}} >\frac1n,$$
equation (4) yields
$$a>\frac{b}{n}.$$
Consequently
$$a'=nb-a<nb-\frac{b}{n},n=(n-1)b.$$
A sharper estimate comes from
$$a>b!\left(\frac{n-\sqrt{n^2-4}}2\right),$$
which gives
$$a' =nb-a <b!\left(\frac{n+\sqrt{n^2-4}}2\right).$$
Using
$$\frac{n+\sqrt{n^2-4}}2<n$$
and (3),
$$a' =\frac{b^2+n}{a} <\frac{b^2+n}{b} =b+\frac nb.$$
Since $n\ge6$, if $b\ge n$ then $a'<b+1$, hence $a'\le b$. Equality $a'=b$ would imply from (3)
$$ab=b^2+n,$$
so
$$b(a-b)=n.$$
Substituting $a=b+n/b$ into (1) gives
$$2b^2+n=nb^2,$$
or
$$(n-2)b^2=n,$$
impossible for $n\ge6$. Thus $a'<b$.
If $b<n$, then from (3),
$$a'=\frac{b^2+n}{a}\le\frac{b^2+n}{b} =b+\frac nb<2n.$$
Since $a\ge b$, repeated application of the same argument produces a solution whose larger coordinate is strictly smaller. Choosing initially a solution with minimal larger coordinate, we obtain a contradiction unless $b=1$.
Thus a minimal solution must satisfy $b=1$. Substituting into (1),
$$a^2+1=na-n,$$
or
$$a^2-na+(n+1)=0. \tag{5}$$
The discriminant of (5) is
$$\Delta=n^2-4(n+1) =(n-2)^2-8.$$
For $n\ge6$,
$$(n-3)^2<(n-2)^2-8<(n-2)^2,$$
because
$$(n-2)^2-8-(n-3)^2=2n-13>0.$$
Hence $\Delta$ lies strictly between two consecutive squares and cannot itself be a square. Equation (5) has no integer solution. This contradiction proves that no solutions exist for $n\ge6$.
Now consider $n=1,2,3,4$.
For $n=1$,
$$a^2+b^2=ab-1,$$
but $a^2+b^2\ge2ab>ab-1$, impossible.
For $n=2$,
$$a^2+b^2=2ab-2,$$
hence
$$(a-b)^2=-2,$$
impossible.
For $n=3$,
$$a^2+b^2=3ab-3.$$
Since
$$a^2+b^2\ge2ab,$$
we obtain
$$ab\ge3.$$
Then
$$0=a^2-3ab+b^2+3 \ge a^2-3ab+b^2+ab =(a-b)^2-ab.$$
The quadratic equation in $a$ has discriminant
$$9b^2-4(b^2+3)=5b^2-12.$$
For $b=1$ it is negative. For $b\ge2$,
$$(2b)^2<5b^2-12<(3b)^2,$$
so the discriminant is not a square. Hence no solutions exist.
For $n=4$,
$$a^2+b^2=4ab-4.$$
The discriminant of the quadratic equation in $a$ is
$$16b^2-4(b^2+4) =12b^2-16 =4(3b^2-4).$$
If $b=1$, this equals $-4$. If $b\ge2$,
$$(\sqrt3,b-1)^2<3b^2-4<(\sqrt3,b)^2,$$
so $3b^2-4$ is not a square. Hence there are no solutions.
Thus the only possible value of $n$ is $5$.
It remains to show that $n=5$ actually occurs. Taking $(a,b)=(1,2)$,
$$\frac{1^2+2^2}{1\cdot2-1} =\frac5{1} =5.$$
This proves the first statement.
For the second statement, rewrite the equation as
$$x^2+y^2=5xy-5. \tag{6}$$
The pair $(1,2)$ satisfies (6).
Suppose $(x,y)$ satisfies (6). Viewing (6) as a quadratic equation in $x$,
$$x^2-5yx+(y^2+5)=0.$$
The second root is
$$x'=5y-x.$$
Hence $(x',y)$ is again a solution. Starting from $(1,2)$, define recursively
$$(x_{k+1},y_{k+1})=(5y_k-x_k,;y_k),$$
and then interchange the coordinates so that the larger number becomes the first coordinate. The first terms are
$$(1,2),\qquad (9,2),\qquad (9,43),\qquad (206,43),\ldots$$
Each new first coordinate equals $5y_k-x_k$, which is larger than $y_k$. Thus the solutions are distinct, and the process never terminates.
Therefore equation (6), equivalently
$$x^2-5xy+y^2+5=0,$$
has infinitely many solutions in natural numbers.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the descent. From
$$a^2+b^2<nab$$
we obtain
$$\frac{n-\sqrt{n^2-4}}2<\frac ab< \frac{n+\sqrt{n^2-4}}2.$$
Hence
$$0<a'=nb-a< b\cdot\frac{n-\sqrt{n^2-4}}2.$$
For $n\ge6$,
$$\frac{n-\sqrt{n^2-4}}2<1,$$
so indeed $a'<b$. Missing this inequality destroys the infinite descent argument.
The second delicate point is the contradiction when $b=1$. Substituting into the equation gives
$$a^2-na+(n+1)=0.$$
The discriminant is
$$(n-2)^2-8.$$
For $n\ge6$ it lies strictly between $(n-3)^2$ and $(n-2)^2$, so it cannot be a square. Any weaker estimate would leave open the possibility of integer roots.
The third delicate point is the generation of infinitely many solutions for $n=5$. The transformation
$$x\mapsto5y-x$$
preserves the equation because it exchanges the two roots of the quadratic in $x$. The new root is positive and larger than $y$ when applied to the growing sequence, so the produced solutions are genuinely distinct rather than cycling.
Alternative Approaches
A more classical presentation of the first part uses Vieta jumping in its standard minimal-counterexample form. Assume $n\ne5$ and choose a positive solution with minimal value of $a+b$. The second root $a'=nb-a$ is positive and smaller than $a$, producing a new solution with smaller sum. The contradiction is then reached after descending to $b=1$. This is essentially the same idea but organized around minimality of $a+b$ rather than explicit inequalities for the larger coordinate.
Another approach derives strong congruence restrictions from
$$a^2+b^2=nab-n$$
and studies the discriminant
$$(n^2-4)b^2-4n.$$
For $n\neq5$ one shows that the discriminant cannot be a perfect square, while for $n=5$ it becomes compatible with the Pell-type recursion generated by the transformation $(x,y)\mapsto(5y-x,y)$. The Vieta-jumping method is preferable because it simultaneously explains the uniqueness of the value $5$ and produces the infinite family of solutions.