整数論パズル開発支援システム(2) - 非専門的シンギュラリティー研究所

「数学ゲーム(34) - 非専門的シンギュラリティー研究所」の残っていた問題について考えていきます。

$R$ を整域とします。以下の条件を満たす $f: R \setminus \{ 0 \} \to \mathbb{N}$ が存在するとき $R$ をユークリッド整域と呼びます。

任意の $a, b \in R$ に対して、 $b \ne 0$ ならば以下の条件を満たす $q, r \in R$ が存在する。

$a = bq + r$

$r = 0$ または $f(r) \lt f(b)$

整数全体からなる環 $\mathbb{Z}$ は、 $a$ の絶対値を $b$ の絶対値で割った商を $q$ 、余りを $r$ 、 $f(x)$ を $x$ の絶対値とすることによりユークリッド整域となります。

と定義しています( $\mathbb{N}$ は $0$ 以上の自然数の全体)。また、以下のことを説明しています。

整数全体からなる環 ℤ は、𝑎 の絶対値を 𝑏 の絶対値で割った商を 𝑞、余りを 𝑟、𝑓⁡(𝑥) を 𝑥 の絶対値とすることによりユークリッド整域となります。
ユークリッド整域は単項イデアル整域となります。
単項イデアル整域の 0 ではない素イデアルは極大イデアルとなります。
ℤ/𝑝⁢ℤ は体となります。
(整域の)素元は既約元となります。
一意分解整域の既約元は素元となります。
単項イデアル整域は一意分解整域となります。

目的の問題のためには、整数全体の環 $\mathbb{Z}$ が一意分解整域で、既約元が素元であることを言えば良いのでこの通りにやれば良いのですが、もうすこし簡単にできる方法を考えます。

(*) 整数全体の環 $\mathbb{Z}$ と絶対値をとる関数 $\mathrm{abs}: \mathbb{Z} \to \mathbb{N}$ に対して

任意のに対して、ならば以下の条件を満たすが存在する。
- $a = bq + r$
- $0 \le r \lt \mathrm{abs}(b)$

整数全体の集合 $\mathbb{Z}$ の部分集合 $X$ 、 $Y$ に対して
$XY = \{ xy \mid x \in X, \ y \in Y\}$
$X + Y = \{ x+y \mid x \in X, \ y \in Y\}$
と書きます。

$\mathbb{Z}$ の元 $a$ と部分集合 $X$ に対して
$aX = \{ ax \mid x \in X\}$
と書きます。

$\mathbb{Z}$ の元 $a$ 、 $b$ に対して
$(a) = a\mathbb{Z}$
$(a, b) = a\mathbb{Z} + b\mathbb{Z}$
と書きます。

$\mathbb{N}_k$ を $k$ 以上の整数全体の集合とします。

$\mathbf{P} = \mathbb{N}_2 \setminus \mathbb{N}_2 \mathbb{N}_2$ とおきます( $\mathbb{Z}$ の正の既約元全体)。「エラトステネスのふるいゲーム」のときと同様に、 $\mathbf{P}$ の元を素数と呼ぶことにします。

「数学ゲーム(34) - 非専門的シンギュラリティー研究所」の残っていた問題は以下のようになります。

$a_1 a_2 \cdots a_n$ が $p \in \mathbf{P}$ で割り切れるならば、 $a_1, a_2, \cdots, a_n$ のどれかは $p$ で割り切れる( $a_1, a_2, \cdots, a_n \in \mathbb{N}_0$ )

これを以下の手順で証明します。このとき集合の包含関係と自然数の順序を使います。 $a$ 、 $b$ などの文字で表されたものは整数とします。

(1) $a, b, q, r$ に対して、 $a = bq + r$ ならば $(a, b) = (r, b)$
(2) $a, b$ に対して $(a, b) = (g)$ を満たす $g$ が存在する
(3) $p \in \mathbf{P}$ 、 $ab \in (p)$ ならば $a \in (p)$ または $b \in (p)$
(4) $p \in \mathbf{P}$ 、 $a_1 a_2 \cdots a_n \in (p)$ ならば $a_k \in (p)$ を満たす $k$ が存在する

(1) $a, b, q, r$ に対して、 $a = bq + r$ ならば $(a, b) = (r, b)$

以下の包含関係から成り立ちます。
$(a, b) = (bq + r, b) \subseteq (bq) + (r) + (b) \subseteq (r, b)$
$(r, b) = (a - bq, b) \subseteq (a) + (bq) + (b) \subseteq (a, b)$

(2) $a, b$ に対して $(a, b) = (g)$ を満たす $g$ が存在する

$\mathbb{Z}$ が単項イデアル整域であることを言えば良いのですが、イデアルの定義を取り入れると複雑になるのでここではこのようにします。

$(a, b) = \{0\}$ のときは $(a, b) = (0)$ となります。

$(a, b) \ne \{0\}$ のとき $g = \min \{ \mathrm{abs}(x) \mid x \in (a, b) \setminus \{0\}\}$ とおきます。
$c \in (a, b)$ をとると(*)より $c = gq + r$ と書けます( $0 \le r < g$ )。
$r \in (a, b)$ なので $g$ の最小性から $r = 0$ となり $c = gq \in (g)$ となります。
よって $(a, b) = (g)$ となります。