第1問

黒板に

1

より大きい

2026

個の整数が書かれており、それらは異なるとは限らない。1回の操作で、孔子は黒板の異なる場所から2つの整数

m>1

と

n>1

を選び、これら2つの整数を

\tfrac{\operatorname{lcm}(m,n)}{\gcd(m,n)}

と

\gcd(m,n)

に置き換える。彼は可能な限り操作を続ける。(a) 孔子の選択にかかわらず、有限回の操作の後、黒板上で

1

より大きい整数

M

がちょうど1つだけになることを証明せよ。(b)

M

の値が孔子の選択によらないことを証明せよ。

ステップ 3/4: 各素数の指数において、操作はユークリッドの互除法の一歩である

前のステップ次のステップ

(v_p(m),v_p(n))=(x,y)\ \longmapsto\ (\min(x,y),\,|x-y|),\qquad \gcd(\min(x,y),|x-y|)=\gcd(x,y)

詳しい解説

素数 $p$ を固定し、選ばれた2数の $p$ 進付値を $x=v_p(m)$ 、 $y=v_p(n)$ と書く。すると $v_p(\gcd(m,n))=\min(x,y)$ 、 $v_p(\operatorname{lcm}(m,n)/\gcd(m,n))=\max(x,y)-\min(x,y)=|x-y|$ となる。 $\gcd(\min(x,y),|x-y|)=\gcd(x,y)$ (ユークリッドの互除法における引き算ステップの標準的な不変性)なので、黒板上の $2026$ 個すべての付値 $v_p(t_1),\ldots,v_p(t_{2026})$ の最大公約数はどの操作によっても変わらない。