IRL ABooklet

Number theory Difficulty 5.2 AIME, harder Prove it Ireland

We say that a pair $(a, b)$ of positive integers is a link if no proper factor of $a + b$ exceeds $\min\{a, b\}$ .
Show that for any positive integers $u$ and $v$ there is a positive integer $n$ and a chain $c_0, c_1, \dots, c_n$ of positive integers such that
* $c_0 = u$
* $c_n = v$
* Each pair $(c_{k-1}, c_k)$ for $1 \le k \le n$ is a link.

Solution

For every positive integer $r$ , the pair $(r, r+1)$ is a link. This follows because the sum $2r + 1$ of the pair is an odd number, which implies that any proper factor is at least $3$ . Therefore, any proper factor of $2r+1$ is at most $(2r+1)/3$ . As $2r+1 \le 2r+1 + (r-1) = 3r$ we deduce that any proper factor of $2r+1$ is at most $r$ , which is the condition for $(r, r+1)$ to be a link.

Suppose without loss of generality that $u \le v$ , and let $n = v-u$ and $c_k = u+k$
for $0 \le k \le n$ . If $n = 0$ , $(u, u)$ is a link. If $n > 0$ each pair $(c_{k-1}, c_k)$ for
$k = 1, \dots, n$ is a link, as required.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.