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

エラトステネスのふるい(2)

整数の場合

次に「エラトステネスのふるい」の整数の場合を考えます。

$\mathbb{Z}$ を整数全体の集合とし、以下 $R = \mathbb{Z}$ とします。 $\mathbb{N}$ を自然数全体の集合とし、 $f: \mathbb{Z} \to \mathbb{N}$ を $a \in \mathbb{Z}$ を $a$ の絶対値に写す写像とします。

$a \in R$ は $ab = 1$ となる $b \in R$ が存在するとき $R$ の単元と呼びます。 $R$ の単元全体の集合を $R^\times$ と書きます。 $\mathbb{Z}^\times = \{1, -1\}$ となります。

$S = R \setminus ( R^\times \cup \{0\} )$ とおきます。 $a \in R$ は以下の条件を満たすとき $R$ の既約元と呼びます。 $R = \mathbb{Z}$ のときは素数と呼びます。

(1) $a \in S$
(2) 任意の $b, c \in R$ に対して $a = bc$ ならば $b \in R^\times$ または $c \in R^\times$

$R$ の部分集合 $X$ 、 $Y$ に対して $\{ xy \mid x \in X, y \in Y \}$ を $XY$ と書くことにします。 $XX$ を $X^2$ と書くことにします。

$b \notin R^\times$ 、 $c \notin R^\times$ とすると $bc \in (S \cup \{0\})(S \cup \{0\}) = S^2 \cup \{0\}$ となります。よって条件(2)は $a \in R \setminus (S^2 \cup \{0\})$ と同値となります。よって $a$ が既約元(素数)であることは $a \in S \setminus S^2$ と同値となるので、 $R$ の既約元(素数)全体を $P$ とすると $P = S \setminus S^2$ となります。

(S1) $X$ を $S$ の有限部分集合とすると $S \setminus X R \ne \varnothing$ となります。

[証明] $X = \{a_1, a_2, \cdots, a_n\}$ とします。 $R = \mathbb{Z}$ なので $S \ne 0$ となります。 $n = 0$ のときは $S \ne 0$ なので成り立っています。以下 $n >0$ とします。

任意の $a_i$ に対して $a_1 a_2 \cdots a_n \in a_i R$ が成り立ちます。 $b = f(a_1 a_2 \cdots a_n) + 1$ とおきます( $f$ は絶対値)。 $b \in a_i R$ とすると $1 \in a_i R$ となって $a_i$ は単元ではないので矛盾となります。よって任意の $a_i$ に対して $b \notin a_i R$ となるので $b \notin X R$ となります。

$R = \mathbb{Z}$ なので $f(a_1 a_2 \cdots a_n) \ge 2$ となって $b \ge 3$ となるので $b$ は $0$ でも単元でもありません。

よって $b \in S \setminus X R$ となり、 $S \setminus X R \ne \varnothing$ が成り立ちます。[証明終わり]

(S1)より $S$ の部分集合の列 $P_0, P_1, P_2, \cdots$ を

$P_0 = \varnothing$
$P_{n+1} = P_n \cup f^{-1}(\min f(S \setminus P_n R))$

と帰納的に定義することができます。

$m_{n} = \min f(S \setminus P_n R)$ とおきます。

$P_n \subseteq P_{n+1}$ より $P_n R \subseteq P_{n+1} R$ 、 $S \setminus P_n R \supseteq S \setminus P_{n+1} R$ 、 $f(S \setminus P_n R) \supseteq f(S \setminus P_{n+1} R)$ 、 $\min f(S \setminus P_n R) \le \min f(S \setminus P_{n+1}) R$ 、 $m_{n+1} \le m_{n+2}$ となります。

$m_{n+1} = m_{n+2}$ とすると $m_{n+1} = m_{n+2} \in f(S \setminus P_{n+1} R)$ なので $m_{n+1} = f(a)$ 、 $a \in S \setminus P_{n+1} R$ となる $a$ が存在します。 $m_{n+1} = f(a)$ より $a \in f^{-1}(m_{n+1}) \subseteq P_{n+1}$ となりますが、 $a \in S \setminus P_{n+1} R$ より $a \notin P_{n+1} R \supseteq P_{n+1} \{1\} = P_{n+1}$ となるので、このようは $a$ は存在しません。

よって $m_0 < m_1 < m_2 < \cdots$ となります。

(S2) $f^{-1}( \min f(S \setminus P_n R) ) \subseteq P$

[証明] $a \in f^{-1}( \min f(S \setminus P_n R) )$ とすると $f(a) = \min f(S \setminus P_n R)$ となります。

もし $f(a) = bc$ 、 $b,c \in S$ 、 $b, c > 0$ とすると $R = \mathbb{Z}$ なので $b, c < f(a)$ となります。 $f(a)$ の最小性から $b \notin S \setminus P_n R$ 、 $b \in P_n R$ 、 $f(a) = bc \in P_n R$ となって矛盾となります。よって $f(a) \in P$ となります。

$f$ は絶対値をとる写像なので $f^{-1}( \min f(S \setminus P_n R) ) = \{ a , -a \} \subseteq P$ となります。[証明終わり]

(S2)より $P_{n+1} = f^{-1}(m_0) \cup f^{-1}(m_1) \cup \cdots \cup f^{-1}(m_n) \subseteq P$ となって $P^* = P_1 \cup P_2 \cup P_3 \cup \cdots$ とおくと $P^* \subseteq P$ が成り立ちます。

(S3) $a \in S, \ b \in R, \ f(a) \le f(b) \implies b \in S$

[証明] $R = \mathbb{Z}$ のときは $a \in S \iff f(a) \ge 2$ となるので成り立ちます。[証明終わり]

(S4) $a \in R, \ m_n < f(a) \implies a \notin P_{n+1}$

[証明] $R = \mathbb{Z}$ のときは $\max f(P_{n+1}) = m_n$ で $f$ は絶対値をとる写像なので成り立ちます。[証明終わり]

$a \in R$ 、 $m_n < f(a) < m_{n+1}$ とすると $f(a) \notin f(S \setminus P_{n+1} R)$ となります。 $a \notin S \setminus P_{n+1} R$ となり (S3)より $a \in S$ となるので $a \in P_{n+1} R \subseteq P_{n+1} \cup P_{n+1} S \subseteq P_{n+1} \cup S^2$ となります。(S4)より $a \notin P_{n+1}$ となるので $a \in S^2$ 、 $a \notin P$ となります。よって $f(P) \subseteq \{m_0, m_1, m_2, \cdots \}$ となって $P \subseteq f^{-1}(\{m_0, m_1, m_2, \cdots \}) =P^*$ となります。

よって $P = P^* = P_1 \cup P_2 \cup P_3 \cup \cdots$ となります。

自然数の有限集合の場合

$k \in \mathbb{N}$ に対して $S_k = S \cap \{ 2, 3, 4, \cdots, k \}$ とおきます。
$\begin{eqnarray*} P_1 \cap S_k & = & \{ 2 \}, \\ P_2 \cap S_k & = & \{ 2, 3 \}, \\ P_3 \cap S_k & = & \{ 2, 3, 5 \}, \\ & \vdots & \\ P_n \cap S_k & = & \{ 2, 3, 5, \cdots, m_{n-1} \} \\ \end{eqnarray*}$
となって、ある $n$ で $m_{n-1} \ge k$ となるので $P \cap S_k \subseteq P_n$ となって $S_k$ に含まれる素数をすべて見つけることができます。このように、有限個の自然数から最小値をとってその倍数をとることを繰り返す方法を「エラトステネスのふるい」と呼びます。

この方法は式で書きにくいので、最小値をとるかわりに自然数の小さいものから順に調べていく方法で書き直すと
$\begin{eqnarray*} P & = & P \cap \left( \bigcup_{k \in \mathbb{N}} \{k+1\} \right) \\ & = & \bigcup_{k \in \mathbb{N}} (P \cap \{k+1\}) \\ & = & \bigcup_{k \in \mathbb{N}} ( (S \setminus S^2) \cap \{k+1\}) \\ & = & \bigcup_{k \in \mathbb{N}} ( (S \setminus (P \cap S_{k})S ) \cap \{k+1\}) \\ \end{eqnarray*}$
のようになります。