Kvant Math Problem 1451

Let $d=\gcd(a,b)$ and write $a=dx$, $b=dy$ with $\gcd(x,y)=1$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m15s
Source on kvant.digital

Problem

Natural numbers $a$ and $b$ are such that $$\dfrac{a+1}{b}+\dfrac{b+1}{a}$$ is an integer. Let $d$ be the greatest common divisor of the numbers $a$ and $b$. Prove that $d^2\le a+b$.

A. S. Golovanov, E. Malinnikova

Russian Mathematical Olympiad (XX)

Exploration

Let $d=\gcd(a,b)$ and write $a=dx$, $b=dy$ with $\gcd(x,y)=1$. The given expression becomes

$$\frac{dx+1}{dy}+\frac{dy+1}{dx} = \frac{x}{y}+\frac{y}{x}+\frac{1}{d}\left(\frac{1}{x}+\frac{1}{y}\right).$$

The first part $\frac{x}{y}+\frac{y}{x}$ simplifies to $\frac{x^2+y^2}{xy}$, which is always rational with denominator dividing $xy$. The integrality condition forces a strong divisibility constraint involving $d$ and $x+y$.

A natural attempt is to clear denominators completely and separate terms depending on $d$ from those depending only on $x,y$. This suggests that the only way the expression can be integer is if a certain linear combination of $x$ and $y$ is divisible by $d$.

Testing small examples such as $(a,b)=(2,1),(3,2),(4,2)$ confirms that when the expression is integer, $d$ is small compared to $a+b$, suggesting the inequality $d^2\le a+b$ is likely a direct consequence of a divisibility relation implying $x+y\ge d$.

The key step is extracting an integrality condition that isolates $(x+y)/d$.

Problem Understanding

The problem is Type B, a divisibility statement leading to an inequality.

We are given positive integers $a,b$ such that

$$\frac{a+1}{b}+\frac{b+1}{a}\in\mathbb{Z},$$

and we must prove that for $d=\gcd(a,b)$,

$$d^2\le a+b.$$

The central difficulty is to convert the integrality condition into a clean arithmetic constraint involving $\gcd(a,b)$ and then relate it to $a+b$.

Proof Architecture

First, we express $a$ and $b$ in terms of $d$ and coprime integers $x,y$.

Next, we rewrite the given expression in terms of $x,y,d$ and isolate integer and fractional parts.

Then we prove that integrality forces $d\mid (x+y)$.

Finally, we rewrite $a+b$ in terms of $d$ and deduce $d^2\le a+b$ from the resulting divisibility.

The most delicate step is correctly separating terms to deduce $d\mid (x+y)$.

Solution

Let $d=\gcd(a,b)$ and write $a=dx$, $b=dy$, where $x,y$ are positive integers with $\gcd(x,y)=1$.

We rewrite the given expression:

$$\frac{a+1}{b}+\frac{b+1}{a} = \frac{dx+1}{dy}+\frac{dy+1}{dx}.$$

Expanding each term gives

$$\frac{dx+1}{dy}=\frac{x}{y}+\frac{1}{dy},\qquad \frac{dy+1}{dx}=\frac{y}{x}+\frac{1}{dx}.$$

Hence the sum equals

$$\frac{x}{y}+\frac{y}{x}+\frac{1}{d}\left(\frac{1}{x}+\frac{1}{y}\right).$$

We combine the first two terms:

$$\frac{x}{y}+\frac{y}{x}=\frac{x^2+y^2}{xy}.$$

Thus the whole expression is

$$\frac{x^2+y^2}{xy}+\frac{1}{d}\left(\frac{x+y}{xy}\right) = \frac{x^2+y^2}{xy}+\frac{x+y}{dxy}.$$

Putting everything over the common denominator $xy$ yields

$$\frac{d(x^2+y^2)+(x+y)}{dxy}.$$

Since the expression is an integer, the numerator is divisible by $dxy$.

In particular, reducing modulo $d$ shows that

$$x+y \equiv 0 \pmod d,$$

so $d\mid (x+y)$. Write $x+y=dm$ for some positive integer $m$.

Now we compute

$$a+b=d(x+y)=d\cdot dm=d^2 m.$$

Since $x$ and $y$ are positive integers, $x+y\ge 2$, hence $m=\frac{x+y}{d}$ is a positive integer and therefore $m\ge 1$.

Thus

$$a+b=d^2 m \ge d^2,$$

which implies

$$d^2 \le a+b.$$

This completes the proof. ∎

Verification of Key Steps

The critical deduction is that $d\mid (x+y)$. Starting from the expression

$$\frac{d(x^2+y^2)+(x+y)}{dxy}\in\mathbb{Z},$$

we note that $d(x^2+y^2)$ is divisible by $d$, hence modulo $d$ the numerator is congruent to $x+y$. For the entire fraction to be integer, the numerator must be divisible by $d$, forcing $x+y\equiv 0\pmod d$.

Another delicate point is ensuring $m\ge 1$. Since $x,y\ge 1$, we have $x+y\ge 2$, and divisibility by $d$ ensures $m$ is a positive integer, so it cannot vanish.

Finally, rewriting $a+b=d(x+y)=d^2 m$ confirms the inequality directly.

Alternative Approaches

A different approach starts directly from the integrality condition and clears denominators to obtain a symmetric Diophantine equation in $a$ and $b$. One can then perform a gcd-based reduction on that equation and again extract the condition $d\mid (a/d+b/d)$. This method is structurally similar but less transparent because the symmetry in $x,y$ is hidden until after division by $d$.