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)\qquad\text{and}\qquad\frac{\operatorname{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.

(Note that \(\gcd(x,y)\) denotes the greatest common divisor of positive integers \(x\) and \(y\), and \(\operatorname{lcm}(x,y)\) denotes the least common multiple of \(x\) and \(y\).)

Official text of the problem. Official problem paper (PDF)

Answer

If the initial integers are \(a_1,\ldots,a_{2026}\), then \[ M=\prod_{p\mid a_1a_2\cdots a_{2026}} p^{\gcd\bigl(v_p(a_1),\ldots,v_p(a_{2026})\bigr)}, \] where the product runs over primes and \(v_p(a)\) denotes the exponent of \(p\) in \(a\).

Solution

(a) Let \(P\) be the product of all numbers currently on the blackboard, and let \(k\) be the number of them greater than \(1\). We show that the positive integer \(P+k\) strictly decreases in every move.

Suppose the chosen numbers are \(m,n>1\), and put \(d=\gcd(m,n)\). The product of their replacements is \[ d\cdot\frac{\operatorname{lcm}(m,n)}d =\operatorname{lcm}(m,n)=\frac{mn}{d}. \] Thus the new product of all blackboard entries is \(P/d\). Also, \(k\) cannot increase, since two entries greater than \(1\) are replaced by two positive integers.

If \(d>1\), the product \(P\) strictly decreases. If \(d=1\), the replacements are \(1\) and \(mn>1\), so \(P\) stays unchanged and \(k\) decreases by one. Hence \(P+k\) strictly decreases in either case. Consequently, every sequence of moves is finite.

There is always at least one entry greater than \(1\): in any move the product of the two replacements is \(\operatorname{lcm}(m,n)>1\). When no further move is possible, there cannot be two entries greater than \(1\). Therefore exactly one such entry remains.

(b) Fix a prime \(p\). For the current blackboard entries \(b_1,\ldots,b_{2026}\), consider \[ G_p=\gcd\bigl(v_p(b_1),\ldots,v_p(b_{2026})\bigr), \] with the convention that the gcd of an all-zero list is \(0\).

If the selected numbers have \(p\)-adic exponents \(u=v_p(m)\) and \(v=v_p(n)\), their replacements have exponents \[ \min(u,v) \quad\text{and}\quad \max(u,v)-\min(u,v)=|u-v|. \] The common divisors of \(u,v\) are precisely the common divisors of \(\min(u,v),|u-v|\): one direction follows by subtraction, and the other by the identity \[ \max(u,v)=\min(u,v)+|u-v|. \] This also covers zero exponents. Since all other exponents remain unchanged, \(G_p\) is invariant under every move.

By part (a), the final entries are \(M\) and \(2025\) copies of \(1\). Thus the final value of this invariant is \[ G_p=\gcd\bigl(v_p(M),0,\ldots,0\bigr)=v_p(M). \] Comparing initial and final values gives, for every prime \(p\), \[ v_p(M)=\gcd\bigl(v_p(a_1),\ldots,v_p(a_{2026})\bigr). \] Unique prime factorization now yields the stated formula for \(M\), which depends only on the initial entries. This proves (b).

The solution was checked against Evan Chen's published IMO solution notes.