第6問

素数 $p$ を $p>a_1^2$ のとき大きい素数、$p\le a_1^2$ のとき小さい素数と呼ぶ。$n\ge1$ に関する帰納法で、$a_n$ が大きい素数 $p$ で割り切れるならば $a_n$ は $\preceq$-極小でないことを示す。$a_n=pc$ と書き、任意の素因数 $q\mid\gcd(a_1,a_n)$ をとる;すると $q\le a_1<a_1^2<p$ なので $q\ne p$ であり、よって $q\mid c$ である。公比 $q\le a_1$ の等比数列 $c,qc,q^2c,\ldots$ において、$a_n/a_1\ge p/a_1>a_1\ge q$ なので、少なくとも1つの項 $x:=q^kc$ が区間 $[a_1,a_n)$ に属する。すべての $\preceq$-極小な項 $a_i<a_n$ に対し、帰納法の仮定より大きい素数 $p$ は $a_i$ を割り切らないので、$\gcd(q^kc,a_i)\ge\gcd(c,a_i)=\gcd(pc,a_i)=\gcd(a_n,a_i)>1$ となる。ステップ1より、$x=q^kc$ は数列の中に $m<n$ なるある $a_m$ として現れなければならない($x<a_n$ のため)。$q\mid c$ だから $\operatorname{rad}(q^kc)=\operatorname{rad}(c)\mid\operatorname{rad}(pc)=\operatorname{rad}(a_n)$ であり、よって $a_m\prec a_n$ となって $a_n$ は $\preceq$-極小ではない。