2008 Putnam A3

Start with a finite sequence $a_1, a_2, \dots, a_n$ of positive integers.

If possible, choose two indices $j < k$ such that $a_j$ does not divide

$a_k$, and replace $a_j$ and $a_k$ by $\mathrm{gcd}(a_j, a_k)$

and $\mathrm{lcm}(a_j, a_k)$, respectively. Prove that if this process is

repeated, it must eventually stop and the final sequence does not depend

on the choices made. (Note: gcd means greatest common divisor and lcm

means least common multiple.)

从正整数的有限序列 $a_1, a_2, \dots, a_n$ 开始。

如果可能，选择两个索引 $j < k$ 使得 $a_j$ 不整除

$a_k$，并将$a_j$和$a_k$替换为$\mathrm{gcd}(a_j, a_k)$

和 $\mathrm{lcm}(a_j, a_k)$ 分别。证明如果这个过程是

重复，它最终必须停止并且最终的顺序不依赖于

关于所做的选择。 (注：gcd表示最大公约数，lcm表示

表示最小公倍数。)