Problem 447

Solution:

First of all, since
$$a \cdot b = \operatorname{gcd}(a, b) \cdot \operatorname{lcm}(a, b)$$
for all positive integers $a$ and $b$, the product of the numbers on the board does not change.

Second, we claim that at each step in which the numbers change, their sum increases. Suppose we pick two numbers $a$ and $b$ ($a \leq b$) and replace them with $g = \operatorname{gcd}(a, b)$ and $\ell = \operatorname{lcm}(a, b)$. If $g = a$, then $\ell = b$ and the numbers do not change, so $g < a$ and therefore $g < b$. The change in the sum of the numbers is
$$(g + \ell) - (a + b) = \frac{g^2 + g \ell - g a - g b}{g} = \frac{g^2 + a b - g a - g b}{g} = \frac{(a - g)(b - g)}{g} > 0.$$
Since each number on the blackboard cannot exceed the product of the numbers that were originally there, the sum cannot increase unboundedly, and thus the numbers must stop changing.