Problem 1909

*Proof.* Without loss of generality, assume that the greatest common divisor of $a_1, a_2, \dots, a_m$ is $1$, otherwise divide all $a_1, a_2, \dots, a_m$ by their greatest common divisor, which does not change the conclusion.
Let $p$ be a prime number in the interval $[2m - \sqrt{m} + 1, 2m]$. If $p$ divides any $a_i$, since the greatest common divisor of $a_1, \dots, a_m$ is $1$, there exists some $a_j$ not divisible by $p$, then
$$\frac{a_i}{(a_i, a_j)} \ge p > m.$$
So, we can assume that $a_1, a_2, \dots, a_m$ are not divisible by $p$.
If there exists $a_i \equiv a_j \pmod{p}$, assume $a_i > a_j$, then
$$\frac{a_i}{(a_i, a_j)} = \frac{a_i - a_j}{(a_i, a_j)} + \frac{a_j}{(a_i, a_j)} \ge p + 1 > m.$$
Therefore, we can assume that $a_1, a_2, \dots, a_m$ have pairwise distinct remainders modulo $p$.
Let $m = \frac{p-1}{2} + r$, then the condition $2m - \sqrt{m} + 1 \le p \le 2m$ is equivalent to $r \in [1, \frac{\sqrt{m}}{2}]$. Divide all non-zero residues modulo $p$ into $\frac{p-1}{2}$ groups, each group containing the residues $i$ and $p-i$. By the pigeonhole principle, there are $r$ groups, each containing two elements from $a_1, a_2, \dots, a_m$. Therefore, we can assume
$$a_{2i-1} \equiv -a_{2i} \pmod{p}, \quad a_{2i-1} < a_{2i}, \quad i = 1, 2, \dots, r.$$
Notice that for $i = 1, 2, \dots, r$, we have $p \mid \frac{a_{2i-1}+a_{2i}}{(a_{2i-1}, a_{2i})}$. If $\frac{a_{2i-1}+a_{2i}}{(a_{2i-1}, a_{2i})} \ge 2p$, then
$$\max \left( \frac{a_{2i-1}}{(a_{2i-1}, a_{2i})}, \frac{a_{2i}}{(a_{2i-1}, a_{2i})} \right) \ge p > m.$$
Therefore, we can assume that for $i = 1, 2, \dots, r$, we have $\frac{a_{2i-1}+a_{2i}}{(a_{2i-1}, a_{2i})} = p$. Let
$$d_i = (a_{2i-1}, a_{2i}), \quad a_{2i-1} = u_i d_i, \quad a_{2i} = v_i d_i.$$
Then $u_i < v_i$ and $u_i + v_i = p$. Notice that if any $v_i \ge m$, the conclusion is already satisfied. Therefore, we can assume
$$v_i \in \left\{ \frac{p-1}{2} + 1, \frac{p-1}{2} + 2, \dots, \frac{p-1}{2} + r - 1 = m - 1 \right\}.$$
By the pigeonhole principle, there are two equal numbers among $v_1, \dots, v_r$. Assume $v_1 = v_2 = v$, hence $u_1 = u_2 = p - v$, denoted as $u$. Clearly, $d_1 \ne d_2$ (since $a_1 \ne a_3$).
Now consider $a_1, a_2, a_3, \text{and } a_4$, assuming $d_1$ and $d_2$ are coprime (otherwise divide them by their greatest common divisor). We have
$$\frac{a_1}{(a_1, a_4)} = \frac{d_1 u}{(d_1, v) \cdot (d_2, u)} \ge \frac{(d_1, u)}{(d_2, u)} \cdot u; \quad \frac{a_3}{(a_2, a_3)} = \frac{d_2 u}{(d_1, u) \cdot (d_2, v)} \ge \frac{(d_2, u)}{(d_1, u)} \cdot u; \quad (6)$$
$$\frac{a_2}{(a_2, a_3)} = \frac{d_1 v}{(d_1, u) \cdot (d_2, v)} \ge \frac{(d_1, v)}{(d_2, v)} \cdot v; \quad \frac{a_4}{(a_1, a_4)} = \frac{d_2 v}{(d_1, v) \cdot (d_2, u)} \ge \frac{(d_2, v)}{(d_1, v)} \cdot v. \quad (7)$$
Notice that the conditions $r \in [1, \frac{\sqrt{m}}{2}]$ and $p - m + 1 \le u < v \le m - 1$ give the following inequality:
$$\frac{m-1}{v} < \frac{m-1}{u} \le \frac{m-1}{p-m+1} \le \frac{m-1}{m-\sqrt{m}+2} < \frac{m-1}{m-\sqrt{m}} = \frac{\sqrt{m}+1}{\sqrt{m}}.$$
If both $\frac{a_i}{(a_i, a_j)}$ in (6) are not greater than $m-1$, then
$$\frac{\sqrt{m}+1}{\sqrt{m}} \ge \frac{(d_1, u)}{(d_2, u)}, \quad \frac{\sqrt{m}+1}{\sqrt{m}} \ge \frac{(d_1, u)}{(d_2, u)}.$$
Thus, either $(d_1, u) = (d_2, u)$ or $(d_1, u) > \sqrt{m}$ and $(d_2, u) > \sqrt{m}$ both hold simultaneously. But note that $(d_1, u) \cdot (d_2, u) \le u < m$, so it must be that $(d_1, u) = (d_2, u)$, and since $d_1$ and $d_2$ are coprime, they must both be equal to $1$.
Similarly, if both $\frac{a_i}{(a_i, a_j)}$ in (7) are not greater than $m-1$, then $(d_1, v) = (d_2, v) = 1$, but then
$$\frac{a_4}{(a_1, a_4)} = \frac{d_2 v}{(d_2, u)(d_1, v)} = d_2 v \ge 2v > m,$$
which is a contradiction!
Therefore, there must exist $a_i$ and $a_j$ such that $\frac{a_i}{(a_i, a_j)} \ge m$. $\square$