The 65th IMO China National Team Selection Test

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(\mathrm{mod}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}(\mathrm{mod}p),a_{2i-1}<a_{2i},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}),a_{2i-1}=u_i{d}_i,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;\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;(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;\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.(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)},\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$