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 3 of 4: On each prime's exponents, a move is a Euclidean step

Previous step Next step

(v_p(m),v_p(n))=(x,y)\ \longmapsto\ (\min(x,y),\,|x-y|),\qquad \gcd(\min(x,y),|x-y|)=\gcd(x,y)

Detailed analysis

Fix a prime $p$ and write $x=v_p(m)$ , $y=v_p(n)$ for the $p$ -adic valuations of the two chosen numbers. Then $v_p(\gcd(m,n))=\min(x,y)$ and $v_p(\operatorname{lcm}(m,n)/\gcd(m,n))=\max(x,y)-\min(x,y)=|x-y|$ . Since $\gcd(\min(x,y),|x-y|)=\gcd(x,y)$ (the standard invariance of a subtraction step in the Euclidean algorithm), the greatest common divisor of all $2026$ valuations $v_p(t_1),\ldots,v_p(t_{2026})$ on the board is unchanged by every move.