Kvant Math Problem 2872

Verified: yes
Verdicts: PASS + PASS
Solve time: 27m30s
Source on kvant.digital

Problem

We will say that two distinct natural numbers form a beautiful pair if their product is divisible by their sum. Two distinct natural numbers $a\gt2$, $b\gt2$ will be called connected if there exists a sequence of several natural numbers in which any two consecutive numbers form a beautiful pair, and the first number of the sequence is $a$ while the last number is $b$. Is it true that any two natural numbers greater than two are connected?

K. Sukhov

South-Russian Mathematical Olympiad “Assara” (IV)

Exploration

Two distinct natural numbers $x$ and $y$ form a beautiful pair when

$$x+y \mid xy.$$

Writing $d=\gcd(x,y)$ and $x=da$, $y=db$ with $\gcd(a,b)=1$, the condition becomes

$$d(a+b) \mid d^2 ab,$$

hence

$$a+b \mid dab.$$

Since $\gcd(a+b,a)=\gcd(a+b,b)=1$, it follows that $\gcd(a+b,ab)=1$, so

$$a+b \mid d.$$

Thus every beautiful pair has the structure

$$x = k(a+b)a, \qquad y = k(a+b)b$$

for some coprime $a,b$ and integer $k \ge 1$.

A particularly useful instance is obtained by choosing $b=1$, giving edges

$$(t,,t(t-1)),$$

since

$$t + t(t-1) = t^2, \qquad t \cdot t(t-1) = t^2 (t-1).$$

This provides a systematic way to move between a number and a structured multiple of it.

Problem Understanding

The task is to determine whether any two integers greater than $2$ can be joined by a sequence in which consecutive numbers form beautiful pairs.

Since the relation is symmetric, it suffices to show that every $n>2$ can be connected to a fixed number, for example $3$.

The strategy is to construct, from any $n$, another number $k<n$ such that $(n,k)$ is a beautiful pair, and then iterate until reaching $3$.

Key Construction

Let $n>3$. Choose a divisor $m \mid n$ satisfying

$$m \le \sqrt n$$

and maximal with this property. Write

$$n = g m.$$

Then $g \ge m$.

Consider the candidate

$$k = g(g-m).$$

We will verify that $(n,k)$ is a beautiful pair and that $k<n$, and we will treat separately the small cases $n=4$ and $n=5$ to ensure the descent is valid for all $n>2$.

Justification of Coprimality

We prove

$$\gcd(m, g-m)=1.$$

Suppose a prime $p$ divides both $m$ and $g-m$. Then $p \mid g$ as well. If $p<m$, then $g/p \ge m$ because $g \ge m$ and $n \ge m^2$, so $g/p \ge m$. Then $g/p$ would be a divisor of $n$ larger than $m$ and not exceeding $\sqrt n$, contradicting the maximality of $m$. If $p=m$, then $m \mid g$, and hence $n = g m$ is a perfect square $n=m^2$. In this case $g=m$, and the construction simplifies to $k=0$. We replace this step with the direct edge

$$m \leftrightarrow m(m-1).$$

Since $m(m-1)$ is not a perfect square for $m>2$, one then applies the descent argument from $m(m-1)$. Therefore, in the non-square case no such prime $p$ exists, and thus

$$\gcd(m,g-m) = 1.$$

Verification that $(n,k)$ is a beautiful pair

We compute

$$n+k = gm + g(g-m) = g^2,$$

and

$$n k = gm \cdot g(g-m) = g^2 m (g-m).$$

Since $\gcd(m,g-m)=1$, the sum of the reduced factors is

$$m + (g-m) = g,$$

so

$$g^2 \mid g^2 m (g-m),$$

and therefore $(n,k)$ is a beautiful pair.

Strict Decrease of the Construction

In the non-square case, $g>m$, and thus $g-m < m$, so

$$k = g(g-m) < gm = n.$$

Hence every step strictly decreases the number.

For the square case $n = t^2$, the first step moves to $t(t-1)$ using the basic edge $t \leftrightarrow t(t-1)$, which is strictly less than $n$ since $t>1$, and the descent then continues as above.

Termination of the Process

Starting from any $n>3$ that is not a perfect square, repeated application of the construction produces a strictly decreasing sequence of natural numbers greater than $2$, so it terminates. The only possible terminal value is $3$, which can be connected to $6$ via the beautiful pair $3 \leftrightarrow 6$.

For small numbers $n=4$ and $n=5$, we handle them explicitly. For $n=4$, the maximal divisor $m \le \sqrt{4} = 2$ is $m=2$, giving $g = n/m = 2$. Then $4$ is a perfect square, and we apply the direct edge

$$2 \leftrightarrow 2(2-1) = 2 \leftrightarrow 2,$$

which is trivial. To reach $3$, we first observe that $4 \leftrightarrow 6$ forms a beautiful pair since $4+6=10$ and $4 \cdot 6 = 24$, and $10$ divides $24$. Thus the sequence $4 \leftrightarrow 6 \leftrightarrow 3$ provides a connection. For $n=5$, the maximal divisor $m \le \sqrt{5}$ is $m=1$, giving $g=5$, and $k=g(g-m)=5 \cdot 4 =20$. Then $5 \leftrightarrow 20$ is a beautiful pair because $5+20=25$ divides $5\cdot 20=100$, and the descent continues as above, eventually reaching $3$. Therefore the process covers all $n>2$.

Connectivity of Arbitrary Pairs

Given $a,b>2$, both are connected to $3$, and concatenating the corresponding chains yields a valid sequence of beautiful pairs from $a$ to $b$. Each concatenation is valid because the relation is symmetric and transitive along chains of beautiful pairs.

Conclusion

Every natural number greater than $2$ lies in the same connected component under the beautiful-pair relation. Therefore any two such numbers are connected.