Problem

Source: Indonesia National Math Olympiad 2021 Problem 6 (INAMO 2021/6)

Tags: number theory, algorithm



There are $n$ natural numbers written on the board. Every move, we could erase $a,b$ and change it to $\gcd(a,b)$ and $\text{lcm}(a,b) - \gcd(a,b)$. Prove that in finite number of moves, all numbers in the board could be made to be equal.