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 1 of 4: Rewrite the replacement and track the product

Previous step Next step

\frac{\operatorname{lcm}(m,n)}{\gcd(m,n)}=\frac{mn}{\gcd(m,n)^2},\qquad \text{new pair product}=\frac{mn}{\gcd(m,n)}

Detailed analysis

Using $\operatorname{lcm}(m,n)\cdot\gcd(m,n)=mn$ , the two replacement numbers are $g:=\gcd(m,n)$ and $mn/g^2$ , whose product is $mn/g$ . Whenever $g>1$ , this new product $mn/g$ is strictly smaller than the old pair product $mn$ , so the product of all $2026$ numbers on the blackboard strictly decreases; whenever $g=1$ , the replacement is $(1,mn)$ , which leaves the total product unchanged but creates a new $1$ (since $m,n>1$ had neither equal to $1$ , while $mn>1$ ).