Kvant Math Problem 1135
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m16s
Source on kvant.digital
Problem
Let $a$ and $b$ be positive integers such that $a^2+b^2$ is divisible by $ab+1$. Prove that $\dfrac{a^2+b^2}{ab+1}$ is the square of an integer.
International Mathematical Olympiad for School Students (XXIX)
Exploration
Let
$$\frac{a^2+b^2}{ab+1}=k,$$
where $k$ is a positive integer. We must prove that $k$ is a perfect square.
Small examples suggest the claim.
If $a=b=1$, then $k=1$.
If $a=1$, then divisibility means $b^2+1$ is divisible by $b+1$. Since
$$b^2+1=(b+1)(b-1)+2,$$
we obtain $b+1\mid2$, hence $b=1$, again giving $k=1$.
If $(a,b)=(8,2)$, then
$$k=\frac{64+4}{16+1}=4.$$
If $(a,b)=(18,6)$, then
$$k=\frac{324+36}{108+1}=\frac{360}{109},$$
which is not integral.
The pair $(8,2)$ gives a nontrivial value $k=4=2^2$.
A standard idea for divisibility conditions of the form
$$a^2+b^2=k(ab+1)$$
is Vieta jumping. Assume a counterexample exists and choose one with minimal value of one variable. Writing the equation as a quadratic in $a$,
$$a^2-kba+(b^2-k)=0,$$
the second root is
$$a'=kb-a.$$
Since the product of the roots equals $b^2-k$, one expects $a'$ to be a smaller positive integer unless $k$ is already a square. The delicate point is proving positivity and strict decrease, and then extracting a contradiction from minimality.
The crucial step is to show that if $k$ is not a square, then the second root satisfies
$$0<a'<b,$$
which produces an infinite descent.
Problem Understanding
We are given positive integers $a$ and $b$ such that
$$ab+1\mid a^2+b^2.$$
Defining
$$k=\frac{a^2+b^2}{ab+1},$$
we must prove that $k$ is the square of an integer.
This is a Type B problem. The statement to prove is that every integer value arising from the divisibility condition is a perfect square.
The core difficulty is to rule out the possibility that a nonsquare integer $k$ satisfies
$$a^2+b^2=k(ab+1)$$
for some positive integers $a,b$. The natural tool is Vieta jumping together with a minimal-counterexample argument.
Proof Architecture
Assume that a nonsquare integer $k$ occurs and choose a solution $(a,b)$ with $a\ge b$ and with $b$ minimal among all such solutions.
The equation can be viewed as a quadratic in $a$,
$$a^2-kba+(b^2-k)=0,$$
whose other integer root is $a'=kb-a$.
If $k>b^2$, then the constant term $b^2-k$ is negative, forcing one root positive and one negative; since $a>0$, the other root is negative, which yields a contradiction unless $b=1$, and that case is impossible.
Hence $k<b^2$.
From Vieta's formulas,
$$aa'=b^2-k>0,$$
so $a'>0$.
Since $a\ge b$,
$$a'=\frac{b^2-k}{a}<\frac{b^2}{a}\le b.$$
Thus $0<a'<b$.
The pair $(a',b)$ satisfies the same equation, contradicting the minimal choice of $b$.
The hardest point is proving simultaneously that $a'$ is positive and strictly smaller than $b$.
Solution
Suppose, for contradiction, that there exists a solution for which
$$k=\frac{a^2+b^2}{ab+1}$$
is not a perfect square.
Then
$$a^2+b^2=k(ab+1). \tag{1}$$
Among all positive integer solutions of (1) with this fixed nonsquare integer $k$, choose one for which $\min(a,b)$ is as small as possible. Interchanging $a$ and $b$ if necessary, we may assume
$$a\ge b. \tag{2}$$
First consider the possibility $b=1$. Equation (1) becomes
$$a^2+1=k(a+1).$$
Reducing modulo $a+1$ gives
$$2\equiv0\pmod{a+1}.$$
Hence $a+1\le2$, so $a=1$. Then (1) yields $k=1$, which is a square, contrary to assumption. Therefore
$$b\ge2. \tag{3}$$
Regard (1) as a quadratic equation in $a$:
$$a^2-kba+(b^2-k)=0. \tag{4}$$
Since $a$ is one root, the other root
$$a'=kb-a$$
is also an integer by Vieta's formulas.
We claim that
$$k<b^2. \tag{5}$$
Indeed, if $k\ge b^2$, then from (4) the constant term satisfies
$$b^2-k\le0.$$
If $k>b^2$, then the product of the roots equals
$$aa'=b^2-k<0,$$
so the roots have opposite signs. Since $a>0$, this gives $a'<0$. Using
$$a+a'=kb,$$
we obtain
$$a>kb.$$
Substituting into (1),
$$k=\frac{a^2+b^2}{ab+1} >\frac{k^2b^2}{kb^2+1}.$$
Multiplying through,
$$k(kb^2+1)>k^2b^2,$$
hence
$$1>(k-1)b^2.$$
Because $b\ge2$ and $k\ge1$, this is impossible.
If $k=b^2$, then from (4)
$$aa'=0.$$
Since $a>0$, we get $a'=0$, whence
$$a=kb=b^3.$$
Substituting into (1),
$$b^6+b^2=b^2(b^4+1)=b^2(b^4+1),$$
while
$$k(ab+1)=b^2(b^4+1),$$
which implies
$$k=b^2,$$
a perfect square, contrary to the assumption that $k$ is nonsquare.
Thus (5) holds.
Now Vieta's formula gives
$$aa'=b^2-k.$$
By (5),
$$b^2-k>0,$$
so
$$a'>0. \tag{6}$$
Using (2),
$$a'=\frac{b^2-k}{a} <\frac{b^2}{a} \le b. \tag{7}$$
Hence
$$0<a'<b. \tag{8}$$
Since $a'$ is the second root of (4), it also satisfies (1):
$$(a')^2+b^2=k(a'b+1).$$
Thus $(a',b)$ is another positive integer solution of (1). By (8), its smaller coordinate is strictly less than $b$, contradicting the minimal choice of $b$.
The contradiction shows that no nonsquare value of $k$ can occur. Therefore every integer
$$k=\frac{a^2+b^2}{ab+1}$$
is a perfect square.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the deduction that the second Vieta root is positive. From
$$aa'=b^2-k,$$
positivity of $a'$ is equivalent to $b^2-k>0$. This is why establishing $k<b^2$ is essential. Without that inequality, the descent cannot begin.
The second delicate point is proving strict decrease. Using only
$$a'=\frac{b^2-k}{a},$$
one gets
$$a'<\frac{b^2}{a}.$$
The assumption $a\ge b$ then yields
$$a'\le \frac{b^2}{a}\le b.$$
Because $k>0$, the inequality is actually strict:
$$a'=\frac{b^2-k}{a}<\frac{b^2}{a}\le b.$$
This gives $a'<b$, which is exactly what minimality requires.
The third delicate point is the exclusion of $k\ge b^2$. If $k>b^2$, then $aa'<0$, so $a'<0$ and consequently $a>kb$. Substituting the stronger inequality $a>kb$ into
$$k=\frac{a^2+b^2}{ab+1}$$
produces
$$k>\frac{k^2b^2}{kb^2+1},$$
which simplifies to
$$1>(k-1)b^2.$$
Since $b\ge2$, this is impossible. A careless argument that merely states "the other root is negative, contradiction" would leave the crucial contradiction unjustified.
Alternative Approaches
A different proof uses the classical Vieta-jumping formulation more directly. Assume a nonsquare value $k$ occurs and choose a solution with minimal $a+b$. Writing the equation as
$$a^2-kba+b^2-k=0,$$
the second root $a'=kb-a$ is an integer. One proves that $0<a'<a$, so $(a',b)$ is another positive solution with a smaller sum, contradicting minimality. The verification again rests on showing $k<b^2$.
Another route interprets (1) through the theory of binary quadratic forms. The equation defines an indefinite quadratic form, and the existence of one positive solution generates others by Vieta transformations. If $k$ is not a square, repeated descent produces infinitely many smaller positive solutions, which is impossible. The elementary Vieta-jumping argument is preferable because it requires only integer arithmetic and a minimal-counterexample principle.