IMO 2026 Problem 1

There are $2026$ integers greater than $1$ written on a blackboard, not necessarily different. In a move, Confucius chooses two integers $m>1$ and $n>1$ from different places on the blackboard and replaces these two integers with

\[\gcd(m,n) \quad \text{ and } \quad  \frac{\mathrm{lcm}(m,n)}{\gcd(m,n)}.\]

He continues to make moves while it is possible to do so.

(a) Prove that, regardless of the choices of Confucius, after finitely many moves, exactly one integer $M$ on the blackboard is greater than $1$.

(b) Prove that the value of $M$ does not depend on the choices of Confucius.

============================================

(a) After a move on $m$ and $n$, their product changes from $mn$ to $\mathrm{lcm}(m,n)\le mn$. The equality holds if and only if $m$ and $n$ are coprime, or equivalently, one of the new numbers is $1$. Hence, the sum of $\prod_{i=1}^{2026}x_i$ and the size of multiset $\{x_i:x_i>1\}$ decreases strictly after every move. Since this number does not decrease indefinitely, at some points the process halts, i.e., at most a number greater than $1$ remains. It is impossible that both new numbers are $1$, so exactly one number greater than $1$ remains at the end.

(b) For every prime $p$ that divides an initial number, let its initial exponents be $$q_1(p),q_2(p),\dots,q_{2026}(p).$$ After a move on numbers with exponents $q_i(p)\le q_j(p)$, they become $$(q_i(p),q_j(p)-q_i(p)).$$ With the argument identical to the correctness proof of Euclean algorithm for computing GCD, it could be seen that the GCD of all these exponents do not change after a move. It is also clear that at the end exactly one nonzero exponent remains, which is $$\gcd\left(q_1(p),q_2(p),\dots,q_{2026}(p)\right).$$ Hence the remaining number is $$M=\prod_pp^{\gcd\left(q_1(p),q_2(p),\dots,q_{2026}(p)\right)}.$$