エレファントな整数論(18) - エレファント・コンピューティング調査報告

整数の素因数分解

整数 $a \notin I = \{0, 1, -1\}$ が素数であることは

(1) $a = bc$ ならば $b = \pm 1$ または $c = \pm 1$

であることと同値となります。

素数全体の集合を $P$ とし、 $f(a)$ を $a$ の絶対値とします。

$X_n = \{ a \in \mathbb{Z} \setminus I \mid f(a) \le n \}$ とおくと $\displaystyle \mathbb{Z} = I \cup \bigcup_{n \in \mathbb{N}} X_n$ となります。

$X, Y \subseteq \mathbb{Z}$ に対して $XY = \{ xy \mid x \in X, y \in Y \}$ 、 $X^* = X \cup XX \cup XXX \cup \cdots$ と書くことにします。

(2) $a \notin I$ ならば $a$ は素数の積で表すことができます。

[証明] (1)より $X_n \subseteq P \cup X_{n-1}^*$ となります。よって
$\begin{eqnarray*} X_n & \subseteq & P^* \cup P^* X_{n-1}^* \cup X_{n-1}^* \\ & \subseteq & P^* \cup P^*(P^* \cup X_{n-2}^* )^* \cup (P^* \cup X_{n-2}^* )^* \\ & \subseteq & P^* \cup P^* X_{n-2}^* \cup X_{n-2}^* \\ \end{eqnarray*}$
となって、これを繰り返して $X_n \subseteq P^* \cup P^* X_{1}^* \cup X_{1}^* \subseteq P^*$ となります。

よって $\displaystyle \mathbb{Z} = I \cup \bigcup_{n \in \mathbb{N}} X_n = I \cup P^*$ となります。よって $a \notin I$ ならば $a$ は素数の積で表すことができます。[証明終わり]

整数の素因数分解の多重集合としての一意性

重複度を含めた集合を多重集合*1と呼びます。多重集合 $\{| x_1, x_2, \cdots , x_m |\}$ とは、通常の集合とは異なり、 $x_1, x_2, \cdots , x_m$ の中に重複するものがあったとき、その出現する回数が異なれば多重集合としては異なるものとするものです。

多重集合 $\{| x_1, x_2, \cdots , x_m |\}$ と $\{| y_1, y_2, \cdots , y_n |\}$ は全単射 $g: \{1, 2, \cdots, m\} \to \{1, 2, \cdots, n\}$ が存在して任意の $i \in \{1, 2, \cdots, m\}$ に対して $x_i = y_{g(i)}$ であるとき $\{| x_1, x_2, \cdots , x_m |\} = \{| y_1, y_2, \cdots , y_n |\}$ とします。

整数 $a$ の倍数全体の集合を $(a)$ とします。

(3) $(a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p)$

を満たす整数 $p$ で $p \notin \{0, 1, -1\}$ であるもの全体の集合を $Q$ とします。

(4) $Q \subseteq P$

[証明]
$\begin{eqnarray*} p \in Q & \iff & \bigl[ \ (a)(b) \subseteq (p) \implies (a) \subseteq (p) \lor (b) \subseteq (p) \ \bigr] \\ & \implies & \bigl[ \ ab = p \implies a \in (ab) \lor b \in (ab) \ \bigr] \\ & \iff & \bigl[ \ ab = p \implies (b) = (1) \lor (a) = (1) \ \bigr] \\ & \iff & p \in P \end{eqnarray*}$
[証明終わり]

(5) $\mathbb{Z} = I \cup Q^*$

[証明] (4) より $Q$ に対しても (2) が成り立ちます。[証明終わり]

(6) $P = Q$

[証明] (5) より $P = P \cap Q^* \subseteq Q$ となります。 [証明終わり]

(7) $m, n \ge 1$ とし、 $p_1, p_2, \cdots , p_m, q_1, q_2, \cdots , q_n$ を正の素数とします。 $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$ ならば任意の $i$ に対して $j$ が存在して $p_i = q_j$ となります。

[証明] $(q_1 q_2 \cdots q_n) \subseteq (p_i)$ であり (6) より $p_i \in Q$ なので $(q_j) \subseteq (p_i)$ となる $j$ が存在します。(1)より $p_i = \pm q_j$ となります。[証明終わり]

多重集合 $\mathcal{X} = \{| x_1, x_2, \cdots , x_m |\}$ と $\mathcal{Y} = \{| y_1, y_2, \cdots , y_n |\}$ に対して

$\{| x_1, x_2, \cdots , x_m, y_1, y_2, \cdots , y_n |\}$ を $\mathcal{X} + \mathcal{Y}$ と書くことにします。
$\mathcal{X} + \mathcal{Z} = \mathcal{Y}$ となる多重集合 $\mathcal{Z}$ が存在するとき $\mathcal{X} \le \mathcal{Y}$ 、 $\mathcal{Z} = \mathcal{Y} - \mathcal{X}$ と書くことにします。
$m$ を $\# \mathcal{X}$ と書くことにします。
$\displaystyle \prod_{i=1}^m x_i$ を $\displaystyle \prod \mathcal{X}$ と書くことにします。 $\# \mathcal{X} = 0$ のときは $\displaystyle \prod \mathcal{X} = 1$ とします。

$\mathcal{Y} \le \mathcal{X}$ のとき $(\mathcal{X} - \mathcal{Y}) + \mathcal{Y} = \mathcal{X}$ となります。

(8) $\mathcal{P}, \mathcal{Q}$ を0個以上の有限個の正の素数からなる多重集合とするとき、 $\prod \mathcal{P} = \prod \mathcal{Q}$ ならば $\mathcal{P} = \mathcal{Q}$ となります。

[証明] $\# \mathcal{P} = 0$ とすると $\prod \mathcal{P} = 1$ となります。 $\prod \mathcal{P} = \prod \mathcal{Q}$ ならば $\prod \mathcal{Q} = 1$ となって $\# \mathcal{Q} = 0$ となるので $\mathcal{P} = \mathcal{Q}$ となります。

$\# \mathcal{P} \ne 0$ とすると $\{| p |\} \le \mathcal{P}$ となる $p$ が存在します。(7) より $\{| p |\} \le \mathcal{Q}$ となります。 $\mathcal{P}' = \mathcal{P} - \{| p |\}$ 、 $\mathcal{Q}' = \mathcal{Q} - \{| p |\}$ とおくと $\prod \mathcal{P} = \prod \mathcal{Q}$ より $\prod \mathcal{P}' = \prod \mathcal{Q}'$ となります。このとき $\mathcal{P}' = \mathcal{Q}'$ と仮定すると、 $\mathcal{P} = \mathcal{P}' + \{| p |\} = \mathcal{Q}' + \{| p |\} = \mathcal{Q}$ となります。

よって $\mathcal{P} = \{| p_1, p_2, \cdots , p_m |\}$ とすると
$\begin{eqnarray*} & & \left[ \ \prod \mathcal{P} = \prod \mathcal{Q} \implies \mathcal{P} = \mathcal{Q} \ \right] \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \{| p_1 |\}) = \prod (\mathcal{Q} - \{| p_1 |\}) \implies \mathcal{P} - \{| p_1 |\} = \mathcal{Q} - \{| p_1 |\} \ \right] \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \{| p_1, p_2 |\}) = \prod (\mathcal{Q} - \{| p_1, p_2 |\}) \implies \mathcal{P} - \{| p_1, p_2 |\} = \mathcal{Q} - \{| p_1, p_2 |\} \ \right] \\ & \Longleftarrow & \\ & \vdots & \\ & \Longleftarrow & \left[ \ \prod (\mathcal{P} - \mathcal{P}) = \prod (\mathcal{Q} - \mathcal{P}) \implies \mathcal{P} - \mathcal{P} = \mathcal{Q} - \mathcal{P} \ \right] \\ \end{eqnarray*}$
となって、最後の項は $\# \mathcal{P} = 0$ の場合なので成り立ちます。よって $\prod \mathcal{P} = \prod \mathcal{Q}$ ならば $\mathcal{P} = \mathcal{Q}$ となります。[証明終わり]

*1:Wikipediaの多重集合の項を参考にします。多重集合の書き方はいろいろあるようですがここでは $\{| \cdots |\}$ を採用します。 $X$ の生成する自由可換モノイドとの関連についてリンクがありますが、リンク先は自由加群となっていてモノイドの場合については書かれていないようです。アーベル群の場合と同様の議論ができると考えられます。