, 2022

Equivalently, we have a graph on 100 vertices and a positive integer written on each vertex. At each step we pick a perfect matching (i.e. a set of disjoint edges covering all vertices) and for each edge of the matching we divide the numbers in its endpoints with their highest common divisor.

If initially the numbers on the vertices are $p_1, p_2, \dots, p_{99}$ and $p_1 p_2 \cdots p_{99}$, where $p_1, \dots, p_{99}$ are distinct prime numbers, then we need at least 99 steps. This is because the vertex having the number $p_1 p_2 \cdots p_{99}$ needs to be matched with every other vertex and we need 99 steps for this.

We show that 99 steps are enough. For this it is enough to show that $K_{100}$ has a 1-factorisation. I.e. we can decompose the edges of the complete graph on 100 vertices into 99 perfect matchings. In general it is a known fact that $K_{2n}$ has a 1-factorisation. For one way to achieve this, write $x, x_1, \dots, x_{2n-1}$ for the vertices, and for the $i$-th matching ($1 \le i \le 2n-1$) consider all edges of the form $x_i x_s$ with $1 \le r < s \le 2n-1$ and $r+s \equiv i \mod{2n-1}$ together with the edge $x x_t$ where $2t \equiv i \mod{2n-1}$.