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

\tfrac{\operatorname{lcm}(m,n)}{\gcd(m,n)}

and

\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.

Step 4 of 4: Part (b): the invariant fixes M uniquely

Previous step Next step

v_p(M)=\gcd(v_p(M),0,\ldots,0)=\gcd(v_p(a_1),\ldots,v_p(a_{2026}))\ \Longrightarrow\ M=\prod_p p^{\gcd(v_p(a_1),\ldots,v_p(a_{2026}))}

Detailed analysis

Let $a_1,\ldots,a_{2026}$ be the initial numbers on the blackboard. At the end of the game the board consists of $M$ and $2025$ ones, whose $p$ -adic valuations are $v_p(M)$ and $2025$ zeros; the greatest common divisor of these terminal valuations is $\gcd(v_p(M),0,\ldots,0)=v_p(M)$ . By the invariance of step 3, this must equal the initial greatest common divisor $\gcd(v_p(a_1),\ldots,v_p(a_{2026}))$ for every prime $p$ . Since a positive integer is uniquely determined by its $p$ -adic valuations across all primes $p$ , $M$ depends only on the initial numbers and not on Confucius's choices.