2021-01-11

エレファントな整数論(11)

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

一般の整域の場合

ここでは既約元の定義から「エラトステネスのふるい」を一般化したものを導くことを考えます。

$R$ を整域とします。

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

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

(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$ となります。

$f: S \to \mathbb{N}$ を以下で述べるような条件(S2)、(S3)、(S4)を満たす写像とします。 $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))$

と帰納的に定義します。このとき

(S1) $S \setminus P_n R \ne \varnothing$

が成り立つとします( $R = \mathbb{Z}$ のときは成り立ちます)。この条件(S1)により $P_0, P_1, P_2, \cdots$ を定義することができます。 $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$ となります。

$f$ は

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

を満たすとします( $R = \mathbb{Z}$ のときは $f$ を絶対値をとる写像とすると成り立ちます)。この条件(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$ が成り立ちます。

$f$ は

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

を満たすとします( $R = \mathbb{Z}$ 、 $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$ となります。

2021-01-07

エレファントな整数論(10)

「群論の計算(20) - エレファント・コンピューティング調査報告」でも書いているのですが、整数の素数の説明を書くために、素イデアル、素元、既約元などの説明をまた書いておきます。

整域

$R$ を単位元を持つ自明ではない可換環とします。任意の $x, y \in R$ に対して $xy = 0$ ならば $x = 0$ または $y = 0$ であるとき、 $R$ を整域と呼びます。体は整域となります。整数全体からなる環 $\mathbb{Z}$ は整域となります。 $R$ が整域であるとき、 $R$ 上の多項式環 $R[X_1, X_2, \cdots , X_n]$ は整域となります。

ユークリッド整域

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

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

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

単項イデアル整域

$R$ を整域とします。 $R$ の任意のイデアルが単項イデアル( $I = Ra$ となる $a \in R$ が存在するようなイデアル $I$ )であるとき、 $R$ を単項イデアル整域と呼びます。

ユークリッド整域は単項イデアル整域となります。

素イデアル

単位元を持つ自明ではない可換環 $R$ の元 $a \in R$ で生成されるイデアル $Ra$ を $(a)$ と書きます。また、元 $a, b \in R$ で生成されるイデアル $Ra+Rb$ を $(a,b)$ と書きます。

単位元を持つ自明ではない可換環 $R$ のイデアル $P$ は(条件1)

$P \ne R$
任意のイデアル $A, B \subseteq R$ に対して、 $AB \subseteq P$ ならば $A \subseteq P$ または $B \subseteq P$

を満たすとき素イデアルと呼びます。

単位元を持つ自明ではない可換環 $R$ のイデアル $P$ が素イデアルであることは、以下の条件(条件2)と同値となります。

$P \ne R$
任意の $a, b \in R$ に対して、 $ab \in P$ ならば $a \in P$ または $b \in P$

[証明] (条件1 $\implies$ 条件2) $a, b \in R$ 、 $ab \in P$ とすると、 $R$ は可換環であることから $(a)(b) = (ab)$ となります。 $(a)(b) = (ab) \subseteq P$ となり (条件1) より $(a) \subseteq P$ または $(b) \subseteq P$ となります。よって $a \in P$ または $b \in P$ となって (条件2) が成り立ちます。

(条件2 $\implies$ 条件1) $A, B \subseteq R$ 、 $AB \subseteq P$ 、 $a \in A$ 、 $b \in B$ とすると、 $ab \in AB \subseteq P$ となって (条件2) より $a \in P$ または $b \in P$ となります。 $A \not \subseteq P$ とすると $a \in A \setminus P$ が存在します。任意の $b \in P$ に対して $a \in P$ または $b \in P$ となるのですが $a \not \in P$ であるので $b \in P$ となります。よって $B \subseteq P$ となって (条件1) が成り立ちます。[証明終わり]

$P$ を単位元を持つ自明ではない可換環 $R$ の素イデアルとすると、 $R/P$ は整域となります。

素元

単位元を持つ自明ではない可換環 $R$ の元 $a$ は $a \ne 0$ であって $(a)$ が $R$ の素イデアルであるとき $R$ の素元と呼びます。

素数 $p$ は整数環 $\mathbb{Z}$ の素元となります。 $(p) = p \mathbb{Z} = \{ p a \ | \ a \in \mathbb{Z} \}$ は $\mathbb{Z}$ の素イデアルとなります。

既約元

$R$ を整域とします。

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

$a \in R$ は $a \ne 0$ であって以下の条件を満たすとき $R$ の既約元と呼びます。

$a$ は $R$ の単元ではない
任意の $b, c \in R$ に対して $a = bc$ ならば $b$ が $R$ の単元であるかまたは $c$ が $R$ の単元である

素数 $p$ は整数環 $\mathbb{Z}$ の既約元となります。

単位元を持つ自明ではない可換環上の多項式環の既約多項式は既約元となります。

素元は既約元となります。

[証明] $a \in R$ を $R$ の素元とします。 $(a)$ は $R$ の素イデアルとなります。素イデアルの定義より $a$ は $R$ の単元ではありません。 $a = bc$ 、 $b, c \in R$ とします。 $(a)$ は $R$ の素イデアルであるから $b \in (a)$ または $c \in (a)$ となります。 $b \in (a) = (bc)$ ならば $b = bcx$ となる $x \in R$ が存在するので $1 = cx$ となって $c$ は $R$ の単元となります。同様に $c \in (a)$ ならば $b$ は $R$ の単元となります。[証明終わり]

$n, m \ge 1$ とし、 $p_1, p_2, \cdots , p_n$ 、 $q_1, q_2, \cdots , q_m$ を $R$ の素元とします。 $p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_m$ ならば $n = m$ であり、適当に並べ替えると任意の $1 \le i \le n$ に対して $(p_i) = (q_i)$ となります。

[証明] $p_1, p_2, \cdots , p_n$ 、 $q_1, q_2, \cdots , q_m$ は $R$ の既約元となります。

$n = 1$ のときは $p_1 = q_1 q_2 \cdots q_m$ となります。 $p_1$ は $R$ の既約元なので $(p_1) = (q_i)$ となる $i$ が存在して、その他の $q_j$ はすべて単元となりますが、 $q_j$ は既約元なので単元となることはありません。よって $m = 1$ であり $(p_1) = (q_1)$ となります。

$n \gt 1$ として、 $n$ より小さい場合は主張が成り立っているとします。 $(p_1) \supseteq (p_1 p_2 \cdots p_n) \ni q_1 q_2 \cdots q_m$ であり $(p_1)$ は素イデアルであるから $(p_1) \ni q_i$ となる $i$ が存在します。番号を付け替えてこの $q_i$ を $q_1$ とします。

$a p_1 = q_1$ となる $a \in R$ が存在します。 $q_1$ は既約元なので $a$ は単元となります。 $a p_1 p_2 \cdots p_n = a q_1 q_2 \cdots q_m$ となるので $q_1 p_2 \cdots p_n = a q_1 q_2 \cdots q_m$ となります。 $R$ は整域なので $p_2 \cdots p_n = a q_2 \cdots q_m$ となります。 $a$ は単元なので帰納法の仮定より $n = m$ であり、適当に並べ替えると任意の $2 \le i \le n$ に対して $(p_i) = (q_i)$ となります。したがって主張が成り立ちます。[証明終わり]

一意分解整域

整域 $R$ の $0$ でも単元でもない任意の元 $a$ に対して素元 $p_1, p_2, \cdots , p_n \in R \ (n \ge 1)$ が存在して

$a = p_1 p_2 \cdots p_n$

と表すことができる(これを素元分解と呼びます)とき $R$ を一意分解整域と呼びます。

一意分解整域の既約元は素元となります。

[証明] $R$ を一意分解整域、 $a \in R$ を既約元とします。素元 $p_1, p_2, \cdots , p_n \in R \ (n \ge 1)$ が存在して $a = p_1 p_2 \cdots p_n$ と表すことができます。 $a$ は既約元なのである1つの $p_i$ 以外の $p_j$ は単元となります。よってある単元 $b$ が存在して $a = b p_i$ となり、 $(a) = (p_i)$ となるので $a$ は素元となります。[証明終わり]

上に示した命題により整域 $R$ が一意分解整域であることは以下の条件と同値となります。

整域 $R$ の $0$ でも単元でもない任意の元 $a$ に対して既約元 $p_1, p_2, \cdots , p_n \in R \ (n \ge 1)$ が存在して

$a = p_1 p_2 \cdots p_n$

と表すことができ、その表示が一意的となる。表示が一意的であるとは既約元 $q_1, q_2, \cdots , q_m \in R \ (m \ge 1)$ が存在して

$a = q_1 q_2 \cdots q_m$

と表されるならば、 $n = m$ であり、適当に並べ替えると任意の $1 \le i \le n$ に対して $(p_i) = (q_i)$ となることを言う。

単項イデアル整域は一意分解整域となります。

[証明] $R$ を単項イデアル整域とします。

$u, v \in R^\times$ ならば $uv \in R^\times$ となります。 $u \in R^\times$ 、 $p$ が既約元ならば $up$ は既約元となります。 $(a) = (b)$ ならば $a = ub$ となる $u \in R^\times$ が存在します。

$R$ の既約元の1個以上の有限個の積全体の集合を $P$ とおきます。すなわち $P = \{ p_1 p_2 \cdots p_n \ | \ p_1, p_2, \cdots , p_n \in R, p_1, p_2, \cdots , p_n は既約元 , n \ge 1 \}$ とおきます。 $\displaystyle I = \bigcup_{x \in R \setminus (P \cup R^\times) } (x)$ とおくと $I$ は $R$ のイデアルとなります。 $R$ は単項イデアル整域なので $I = (a)$ となる $a \in R$ が存在します。 $a \in (x)$ となる $x \in R \setminus (P \cup R^\times)$ が存在します。 $(a) = (x)$ となります。

$a \in R^\times$ とすると、 $x \in R^\times$ となります。 $a \in P$ とすると、 $x \in P$ となります。どちらも $x \notin P \cup R^\times$ に反します。

よって $a \notin P \cup R^\times$ となります。 $a \ne 0$ とすると $a$ は既約元ではないので、 $a = bc$ であって、 $b \notin R^\times$ 、 $c \notin R^\times$ となる $b, c \in R$ が存在します。 $(a) = (b)$ とすると、 $a = ub$ となる $u \in R^\times$ が存在します。 $ub = bc$ 、 $c = u \in R^\times$ となって $c \notin R^\times$ に反するので $(a) \ne (b)$ となります。よって $b \notin P$ とすると、 $b \in (a)$ となって $(a) = (bc) \subseteq (b)$ に反するので $b \in P$ となります。同様に $c \in P$ となります。よって $a = bc \in P$ となって $a \notin P$ であることに矛盾します。

よって $a = 0$ となって $R = P \cup R^\times \cup 0$ となり主張が成り立ちます。[証明終わり]

可換環論の勘どころ (数学のかんどころ)

作者:四郎, 後藤
発売日: 2017/08/10
メディア: 単行本

2021-01-06

エレファントな整数論(9)

ユークリッド整域

$R$ を整域とします。

(1) (除法の原理) 、とすると以下のようなが存在する。
- $a = qb + r$ かつ
- $r = 0$ または $\varphi(r) < \varphi(b)$
(2) $a, b \in R$ 、 $a \ne 0$ 、 $b \ne 0$ ならば $f(a) < f(ab)$

という2つの条件を満たす $\varphi: R \setminus \{0\} \to \mathbb{N}$ (ユークリッド関数)が存在するとき、 $R$ をユークリッド整域と呼びます(この定義はWikipediaによります*1 )。

$R$ を整域、 $a \in R$ のとき $aR$ は $R$ のイデアルとなります。このような一つの元で生成されたイデアルを単項イデアルと呼びます。 $R$ の任意のイデアルが単項イデアルであるとき単項イデアル整域と呼びます。

ユークリッド整域は単項イデアル整域となります。

[証明] $R$ をユークリッド整域、 $\varphi: R \setminus \{0\} \to \mathbb{N}$ をユークリッド関数、 $I$ を $R$ のイデアルとします。

$I \ne 0$ とすると $n = \min \{ \varphi(a) \mid a \in I \setminus \{0\} \}$ が存在します。 $n = \varphi(a)$ 、 $a \in I \setminus \{0\}$ とします。 $b \in I$ をとると

$b = qa + r$ 、
$r = 0$ または $\varphi(r) < \varphi(a)$

であるような $q, r \in R$ が存在します。 $r = b - qa \in I$ で $\varphi(a)$ は最小のものなので $r \ne 0$ ならば $\varphi(r) < \varphi(a)$ となることはありません。よって $r = 0$ となって $b = qa \in aR$ となります。

よって $I \ne 0$ のとき $I = aR$ となる $a \in R$ が存在します。 $I = 0$ のときは $I = 0R$ となるので $R$ は単項イデアル整域となります。[証明終わり]

ユークリッドの互除法

$R$ をユークリッド整域、 $\varphi: R \setminus \{0\} \to \mathbb{N}$ をユークリッド関数、 $a, b \in R$ 、 $a \ne 0$ 、 $b \ne 0$ とします。

$a = qb + r$ かつ
$r = 0$ または $\varphi(r) < \varphi(b)$

となる $q, r \in R$ が存在します。 $r \ne 0$ のとき $a_1 = b$ 、 $b_1 = r$ とおくと $aR + bR = a_1 R + b_1 R$ 、 $\varphi(a_1) > \varphi(b_1)$ となります。

$a_n, b_n$ に対して

$a_n = q_n b_n + r_n$ かつ
$r_n= 0$ または $\varphi(r_n) < \varphi(b_n)$

となる $q_n, r_n \in R$ が存在します。 $r_n \ne 0$ のとき $a_{n+1} = b_{n}$ 、 $b_{n+1} = r_n$ とおくと $aR + bR = a_{n+1} R + b_{n+1} R$ 、 $\varphi(a_{n+1}) > \varphi(b_{n+1})$ となります。

任意の $n \in \mathbb{N}$ に対して $r_n \ne 0$ とすると、 $a_1 > a_2 > \cdots$ という無限の列が存在することになりますが、そのようなことはないので $r_n = 0$ となる $n \in \mathbb{N}$ が存在します。このとき $a_n = q_n b_n + r_n = q_n b_n$ より $aR + bR = a_{n} R + b_{n} R = b_{n} R$ となります。

このように $a, b \in R$ から $r$ (余り)をとることを繰り返すことによって $r_1, r_2, \cdots$ を作り $aR + bR = cR$ となる $c \in R$ 得る方法をユークリッドの互除法と呼びます。
$\begin{eqnarray*} b_{1} & = & a - q b \\ b_{2} & = & a_{1} - q_{1} b_{1} \\ & \vdots & \\ b_{n-1} & = & a_{n-2} - q_{n-2} b_{n-2} \\ c = b_n & = & a_{n-1} - q_{n-1} b_{n-1} \end{eqnarray*}$
を順に代入していくことによってこの $c$ を $a$ と $b$ で表すことができます。

$a \in \mathbb{Z}$ の絶対値 $|a|$ を $a > 0$ のとき $|a| = a$ 、 $a < 0$ のとき $|a| = -a$ とし、 $\varphi: \mathbb{Z} \setminus \{0\} \to \mathbb{N}$ を $\varphi(a) = |a|$ とします。

$r: \mathbb{Z} \times (\mathbb{Z} \setminus \{0\}) \to \mathbb{N}$ を $r(a, b) = \min (\mathbb{N} \cap (a + b \mathbb{Z}))$ とすると $a - r(a, b) \in b \mathbb{Z}$ となって $a = qb + r(a, b)$ となる $q \in \mathbb{Z}$ が存在します。また $r(a, b) < |b|$ となるので $\varphi$ はユークリッド関数の条件(1)を満たします。 $a, b \in \mathbb{Z}$ 、 $a \ne 0$ 、 $b \ne 0$ のとき $\varphi(a) = |a| < |a| |b| = \varphi(ab)$ となって $\varphi$ はユークリッド関数の条件(2)も満たすので $\varphi$ はユークリッド関数となります。

よって $\mathbb{Z}$ はユークリッド整域となり、ユークリッドの互除法により $a, b \in \mathbb{Z}$ に対して $a \mathbb{Z} + b \mathbb{Z} = c \mathbb{Z}$ となる $c \in \mathbb{Z}$ を求めることができます。

ユークリッドの互除法を式で書く方法を考えます。 $\mathbb{N}^+ = \mathbb{N} \setminus \{0\}$ とおきます。上記の $(a_n, b_n)$ を $(a_{n+1}, b_{n+1})$ に写す写像を $f: \mathbb{N}^+ \times \mathbb{N} \to \mathbb{N}^+ \times \mathbb{N}$ とします。ただし $b_n = 0$ のときは $f$ は恒等写像とします。 $a, b \in \mathbb{N}$ に対して
$f(a, b), f(f(a, b)), f(f(f(a, b))), \cdots$
という列を $b_n = 0$ になるまで繰り返したものを $f^*(a, b)$ と書くことにすると $f^*(a, b) = (c, 0)$ と書くことができます。

初等整数論入門 Math＆Science (ちくま学芸文庫)

作者:銀林浩
発売日: 2019/08/09
メディア: Kindle版

*1:「群論の計算(20)」でユークリッド整域について少し書いていました。この定義もWikipediaに従ったと思うのですが、条件(2)については書いていません。条件(2)はなくてもユークリッドの互除法はできるようです。

2021-01-02

エレファントな整数論(8)

剰余類

$a, b \in \mathbb{Z}$ に対して

$a \mathbb{Z} = \{ an \mid n \in \mathbb{Z} \}$
$b + a \mathbb{Z} = \{ b + an \mid n \in \mathbb{Z} \}$

と定義します。

$a \in \mathbb{Z}$ に対して

$\mathbb{Z} / a \mathbb{Z} = \{ b + a \mathbb{Z} \mid b \in \mathbb{Z} \}$

と定義します。 $\mathbb{Z} / a \mathbb{Z}$ に演算 $+$ を $b, c \in \mathbb{Z}$ に対して

$(b + a \mathbb{Z}) + (c + a \mathbb{Z}) = (b + c) + a \mathbb{Z}$

と定義すると、 $\mathbb{Z} / a \mathbb{Z}$ はアーベル群になります。この元を剰余類と呼びます。

$a \ne 0$ とし $f : \mathbb{Z} \to \mathbb{Z} / a \mathbb{Z}$ を $n \mapsto n + a \mathbb{Z}$ とします。 $f$ は群の準同型となります。 $b \in \mathbb{Z}$ に対して $r = \min (\mathbb{N} \cap f^{-1}(f(b)))$ とおきます。

$a > 0$ のとき $r \ge a$ とすると $r = a + c$ となる $c \in \mathbb{N}$ が存在します。 $f(c) = f(r) = f(b)$ となり、 $r$ の最小性から $r \le c$ となります。 $r = a + c$ から $a + c \le c$ となり $a \le 0$ となって $a > 0$ に矛盾します。

$a < 0$ のとき $r \ge -a$ とすると $r = -a + c$ となる $c \in \mathbb{N}$ が存在します。 $f(c) = f(r) = f(b)$ となり、 $r$ の最小性から $r \le c$ となります。 $r = -a + c$ から $-a + c \le c$ となり $-a \le 0$ となって $a < 0$ に矛盾します。

よって

$a > 0$ のとき $0 \le r < a$
$a < 0$ のとき $0 \le r < -a$

となります。 $r$ を $b$ を $a$ で割った余りと呼びます。

環と半環

集合 $R$ に加法と乗法という2つの二項演算が存在して

加法に関して可換なモノイド
乗法に関して半群(結合法則を満たす)
乗法の加法に対する分配法則を満たす

ならば $R$ は半環であるといいます。

$R = \{0\}$ のとき自明であるといいます。
乗法の単位元が存在するとき単位元( $1$ と書きます)をもつ
乗法が可換であるとき可換
加法に関してアーベル群であるとき環

といいます。

$\mathbb{N}$ は単位元をもつ自明ではない可換半環、 $\mathbb{Z}$ は単位元をもつ自明ではない可換環となります。

単位元をもつ自明ではない可換半環 $R$ の部分集合全体の集合を $P$ とします。 $X, Y \in P$ に対して

$X+Y = \{x+y \mid x \in X, y \in Y\}$
$XY = \{xy \mid x \in X, y \in Y\}$

と定義します。これらの演算によって $P$ は単位元をもつ自明ではない可換半環となります。

$X=\{x\}$ のとき $X+Y$ を $x+Y$
$X=\{x\}$ のとき $XY$ を $xY$

と書きます。

$I \in P$ が

$I+I \subseteq I$
$IR \subseteq I$

であるとき $R$ のイデアルと呼びます。

$I$ が $R$ のイデアルのとき $f: R \to P$ を $f(x) = x + I$ とすると

$f(x+y) = (x + y) + I = (x + I) + (y + I) = f(x) + f(y)$
$f(xy) = (xy) + I = (x + I)(y + I) = f(x)f(y)$

となるので、 $f(R)$ は単位元をもつ可換半環、 $f$ は半環の準同型となります。
$f(R)$ が環のとき $f(R)$ は単位元をもつ可換環、 $f$ は環の準同型となります。

$X \in P$ のとき $X^* = X \cup (X+X) \cup (X+X+X) \cup \cdots$ とします。 $I, J$ が $R$ のイデアルのとき $I * J = (IJ)^*$ とすると、 $R$ のイデアル全体の集合 $S$ は加法 $+$ と乗法 $*$ に関して単位元をもつ自明ではない可換半環となります。

最大公約数

$a \in \mathbb{Z}$ に対して $a \mathbb{Z} = \{ an \mid n \in \mathbb{Z} \}$ の元を $a$ の倍数と呼びます。 $b \in a \mathbb{Z}$ に対して $a$ を $b$ の約数と呼びます。

$b \mathbb{Z} \subseteq a \mathbb{Z}$ $\iff$ $b$ は $a$ の倍数 $\iff$ $a$ は $b$ の約数

$a, b, c \in \mathbb{Z}$ に対して

$c$ が $b$ の約数かつ $c$ が $b$ の約数

であるとき $c$ を $a$ と $b$ の公約数と呼びます。

$a \mathbb{Z} + b \mathbb{Z} \subseteq c \mathbb{Z}$ $\iff$ $c$ は $a$ と $b$ の公約数

となります。

$a \mathbb{Z} + b \mathbb{Z} \subseteq \mathbb{Z} = 1 \mathbb{Z}$ なので $1$ は $a$ と $b$ の公約数となります。

$\max \{ c \in \mathbb{Z} \mid a \mathbb{Z} + b \mathbb{Z} \subseteq c \mathbb{Z} \}$ を $a$ と $b$ の最大公約数と呼びます。

$e = \min \{ c, d \in \mathbb{N} \mid a \mathbb{Z} + b \mathbb{Z} = c \mathbb{Z} + d \mathbb{Z} \}$ とおきます。 $e > 0$ とすると $a \mathbb{Z} + b \mathbb{Z} = e \mathbb{Z} + c \mathbb{Z}$ 、 $c \ge e$ となる $c \in \mathbb{Z}$ が存在します。 $f: \mathbb{Z} \to \mathbb{Z} / e \mathbb{Z}$ を $x \mapsto x + e \mathbb{Z}$ という写像とし、 $r = \min (\mathbb{N} \cap f^{-1}(f(c)))$ とすると、上の議論より $a \mathbb{Z} + b \mathbb{Z} = e \mathbb{Z} + c \mathbb{Z} = r \mathbb{Z} + c \mathbb{Z}$ 、 $r < e$ となって $e$ の最小性に矛盾となります。よって $e = 0$ となります。

$a \mathbb{Z} + b \mathbb{Z} = c \mathbb{Z}$ となって $c$ は $a$ と $b$ の最大公約数となります。

初等整数論入門 Math＆Science (ちくま学芸文庫)

作者:銀林浩
発売日: 2019/08/09
メディア: Kindle版

2021-01-01

今後の課題

数学的帰納法の記法

数学的帰納法に関する計算を「 $\cdots$ 」という書き方でやっています。「素因数分解の一意性」の証明をこの記法で行うことが目標となっています。このままの記法でできると思うのですが、できない場合は新しい記法を考えていきます。

可換な和、行または列が可換な行列

$+$ が可換であるとき、 $x+y$ と $y+x$ が同じものに見えないという問題です。これを進めていって、ポアンカレ予想の説明をすることが目標です。

圏論、直積、極限

直積を使って極限を表すという問題です。自然数の定義と同様の方法でできると思われますが、まだよくわかっていません。

複素数の極限

複素数の極限について、普通の極限の記法だとうまく証明できないものがあるので、何か工夫の余地があると思われますが、できるのかどうかわかりません。これを進めていって、リーマン予想の説明をすることが目標です。

体上の代数

体上の代数の計算方法を考えて、それによって体の拡大を表すことができるかという問題です。半環と体の対応も考えていきます。

群の計算

群の計算で数学的帰納法を使うものを考えていきます。

今後の予定

式の変形の記法をいろいろ考えます。
式の変形の動画によって入力を行う方法を考えます。
その入力によって順序を指定する方法を考えます。
ブラウザからの入力によって順序を指定することによりプログラムを更新できるようにしていきます。
ゲームのような形式でプログラムを更新して得点を得ることができるシステムを考えます。
これを進めていってリモートワークができるようにします。

2020-12-31

エレファントな整数論(7)

$\mathbb{N}$ を使って良いことにしたので、前回の議論は群を使って考えることができます。

群による整数の加法

集合 $G$ と $G$ の二項演算 $+$ が

$+$ は結合法則を満たす。すなわち
任意の $x, y, z \in G$ に対して $(x + y) + z = x + (y + z)$
$0 \in G$ が存在して、任意の $x \in G$ に対して $0 + x = x + 0 = 0$
任意の $x \in G$ に対して $-x \in G$ が存在して、 $(-x) + x = x + (-x) = 0$

が成り立つとき $G$ と $+$ の組を群と呼びます。

$x \in G$ 、 $n \in \mathbb{N}$ に対して $n \cdot x$ を

$0 \cdot x = 0$
$(n + 1) \cdot x = n \cdot x + x$

と定義します。

$\begin{eqnarray*} & & (n+1) \cdot x = x + n \cdot x \\ & \Leftarrow & n \cdot x + x = x + (n-1) \cdot x + x \\ & \Leftarrow & n \cdot x = x + (n-1) \cdot x \\ & \Leftarrow & (n-1) \cdot x = x + (n-2) \cdot x \\ & \Leftarrow & \cdots \Leftarrow (n-n+1) \cdot x = x + (n-n) \cdot x \Leftarrow x = x \end{eqnarray*}$

任意の $x \in G$ 、 $n \in \mathbb{N}$ に対して $(n+1) \cdot x = n \cdot x + x = x + n \cdot x$

$n \cdot x + (-x) = (-x) + x + n \cdot x + (-x) = (-x) + n \cdot x + x + (-x) = (-x) + n \cdot x$

任意の $x \in G$ 、 $n \in \mathbb{N}$ に対して $n \cdot x + (-x) = (-x) + n \cdot x$

$x \in G$ 、 $n \in \mathbb{N}$ に対して $(-n) \cdot x$ を

$0 \cdot x = 0$
$(-(n + 1)) \cdot x = (-n) \cdot x + (-x)$

と定義します。

$\begin{eqnarray*} & & (-(n+1)) \cdot x = (-x) + (-n) \cdot x \\ & \Leftarrow & ( (-n) \cdot x) + (-x) = (-x) + ( (-(n-1) ) \cdot x) + (-x) \\ & \Leftarrow & ( (-n) \cdot x) = (-x) + ( (-(n-1) ) \cdot x) \\ & \Leftarrow & ( (-(n-1) ) \cdot x) + (-x) = (-x) + ( (-(n-2) ) \cdot x) \\ & \Leftarrow & \cdots \Leftarrow ( (-(n-n+1) ) \cdot x) = (-x) + ( (-(n-n) ) \cdot x) \Leftarrow -x = -x \end{eqnarray*}$

任意の $x \in G$ 、 $n \in \mathbb{N}$ に対して $(-(n+1)) \cdot x = (-n) \cdot x + (-x) = (-x) + (-n) \cdot x$

$(-n) \cdot x + x = x + (-x) + (-n) \cdot x + x = x + (-n) \cdot x + (-x) + x = x + (-n) \cdot x$

任意の $x \in G$ 、 $n \in \mathbb{N}$ に対して $(-n) \cdot x + x = x + (-n) \cdot x$

$y = n \cdot x$ または $y = (-n) \cdot x$ のとき
$m \cdot x + y = (m - 1) \cdot x + x + y \\ = (m - 1) \cdot x + y + x = (m - 2) \cdot x + y + 2 \cdot x \\ = \cdots = (m - m) \cdot x + y + m \cdot x = y + m \cdot x$
$(-m) \cdot x + y = (-(m - 1)) \cdot x + (-x) + y \\ = (-(m - 1)) \cdot x + y + (-x) = (-(m - 2)) \cdot x + y + (-2) \cdot x \\ = \cdots = (-(m - m)) \cdot x + y + (-m) \cdot x = y + (-m) \cdot x$

(G5) 任意の、に対して
- $m \cdot x + n \cdot x = n \cdot x + m \cdot x$
- $m \cdot x + (-n) \cdot x = (-n) \cdot x + m \cdot x$
- $(-m) \cdot x + n \cdot x = n \cdot x + (-m) \cdot x$
- $(-m) \cdot x + (-n) \cdot x = (-n) \cdot x + (-m) \cdot x$

$n \cdot x + (-n) \cdot x = (n - 1) \cdot x + x + (-(n - 1)) \cdot x + (-x) \\ = (n - 1) \cdot x + (-(n - 1)) \cdot x = (n - 2) \cdot x + (-(n - 2)) \cdot x \\ = \cdots = (n - n) \cdot x + (-(n - n)) \cdot x = 0$

(G4) 任意の $x \in G$ 、 $n \in \mathbb{N}$ に対して
$n \cdot x + (-n) \cdot x = (-n) \cdot x + n \cdot x = 0$

$(m + n) \cdot x = (m + n - 1) \cdot x + x = (m + n - 2) \cdot x + 2 \cdot x \\ = \cdots = = (m + n - n) \cdot x + n \cdot x = m \cdot x + n \cdot x$
$(-(m + n)) \cdot x = (-(m + n - 1)) \cdot x + (-x) = (-(m + n - 2)) \cdot x + (-2) \cdot x \\ = \cdots = = (-(m + n - n)) \cdot x + (-n) \cdot x = (-m) \cdot x + (-n) \cdot x$

(G1) 任意の、に対して
- $(m + n) \cdot x = m \cdot x + n \cdot x$
- $-(m + n) \cdot x = (-m) \cdot x + (-n) \cdot x$

$m \ge n$ のとき $m = n + d$ となる $d \in \mathbb{N}$ が存在します。 $d = m \setminus n$ と書くと

(G2) 任意の、に対して
- $m \cdot x + (-n) \cdot x = n \cdot x + (m \setminus n) \cdot x + (-n) \cdot x = (m \setminus n) \cdot x$
(G3) 任意の、に対して
- $(-m) \cdot x + n \cdot x = (-n) \cdot x + (-(m \setminus n)) \cdot x + n \cdot x = (-(m \setminus n)) \cdot x$

となります。

$H = \{ n \cdot x \mid n \in \mathbb{N} \} \cup \{ (-n) \cdot x \mid n \in \mathbb{N} \}$ とおくと(G1)、(G2)、(G3)より $H$ は $+$ に関して閉じています。(G4)より $H$ は逆元をとることに関して閉じているので、 $H$ は $G$ の部分群となります。(G5)より $H$ はアーベル群となります。 $H$ が無限集合のとき $H$ は整数全体の集合 $\mathbb{Z}$ と考えることができます。

群による整数の乗法

$G$ をアーベル群とします。 $E = \mathrm{End}(G)$ を $f: G \to G$ で任意の $x, y \in G$ に対して $f(x+y) = f(x)+f(y)$ を満たす写像(自己準同型)全体の集合とします。

$f, g \in E$ に対して $f+g$ を $(f+g)(x) = f(x) + g(x)$ と定義すると、 $G$ の演算が可換であることから
$(f+g)(x+y) = f(x+y) + g(x+y) = (f(x)+f(y)) + (g(x)+g(y)) \\ = (f(x)+g(x)) + (f(y)+g(y)) = (f+g)(x) + (f+g)(y)$
となって $f+g \in E$ となります。よって $E$ は $+$ に関してアーベル群となります。 $fg \in E$ を $(fg)(x) = f(g(x))$ (写像の合成)と定義すると、 $E$ は写像の合成に関してモノイドとなります。 $f, g, h \in E$ に対して $f$ は自己準同型であるから $f(g+h) = fg + fh$ が成り立ちます。 $+$ の定義から $(f+g)h = fh + gh$ が成り立ちます。 $+$ を加法、写像の合成を乗法とすると乗法の加法に対する分配法則が成り立ちます。 $E$ はこの加法と乗法に関して環となります。

$x \in G$ 、 $n \in \mathbb{Z}$ 、 $n \ge 0$ に対して $n \cdot x$ を

$0 \cdot x = 0$
$(n + 1) \cdot x = n \cdot x + x$

と定義します。

$n \cdot (x+y) \\ = (n-1) \cdot (x+y) + (x+y) = (n-2) \cdot (x+y) + (x+y) + (x+y) \\ = (n-2) \cdot (x+y) + (2 \cdot x + 2 \cdot y) = \cdots = (n-n) \cdot (x+y) + (n \cdot x + n \cdot y) \\ = n \cdot x + n \cdot y$
となります。

$x \in G$ 、 $n \in \mathbb{Z}$ 、 $n \le 0$ に対して $n \cdot x$ を

$0 \cdot x = 0$
$(n - 1) \cdot x = n \cdot x - x$

と定義します。

$n \cdot (x+y) = (n+1) \cdot (x+y) + (-(x+y)) \\ = (n+1) \cdot (x+y) + ( (-x)+(-y) ) = (n+2) \cdot (x+y) + ( (-x)+(-y) ) + ( (-x)+(-y) ) \\ = (n+2) \cdot (x+y) + ( (-2) \cdot x + (-2) \cdot y) = \cdots = (n+(-n)) \cdot (x+y) + (n \cdot x + n \cdot y) \\ = n \cdot x + n \cdot y$
となります。

よって

任意の $x, y \in G$ 、 $n \in \mathbb{Z}$ に対して $n \cdot (x+y) = n \cdot x + n \cdot y$

となります。

よって $\varphi: \mathbb{Z} \to E$ を $\varphi(n) \in E$ が $x \mapsto n \cdot x$ となる写像として定義することができます。

任意の $m, n \in \mathbb{Z}$ に対して $\varphi(m+n) = \varphi(m) + \varphi(n)$
$\varphi(0) = 0$ ( $0$ は $x \mapsto 0$ という写像)

となるので $\varphi$ は群の準同型となります。

任意の $m, n \in \mathbb{Z}$ 、 $m \ge 0$ に対して

$\varphi(0) \varphi(n) = 0$
$\varphi(m + 1) \varphi(n) = \varphi(m)\varphi(n) + \varphi(n)$

任意の $m, n \in \mathbb{Z}$ 、 $m \le 0$ に対して

$\varphi(0) \varphi(n) = 0$
$\varphi(m - 1) \varphi(n) = \varphi(m)\varphi(n) - \varphi(n)$

となります。よって

任意の $m, n \in \mathbb{Z}$ に対して $p \in \mathbb{Z}$ が存在して $\varphi(m) \varphi(n) = \varphi(p)$

となって $\varphi(\mathbb{Z})$ は乗法に関して閉じているので $\varphi(\mathbb{Z})$ は $E$ の部分環となります。

任意の $m, n \in \mathbb{Z}$ 、 $m \ge 0$ に対して
$\varphi(m) \varphi(n) - \varphi(n)\varphi(m) = (\varphi(m) - \varphi(1)) \varphi(n) + \varphi(n) - \varphi(n)\varphi(m) \\ = (\varphi(m) - \varphi(1)) \varphi(n) - \varphi(n) (\varphi(1) - \varphi(m)) \\ = \cdots = (\varphi(m) - \varphi(m)) \varphi(n) - \varphi(n) (\varphi(m) - \varphi(m)) = 0$
任意の $m, n \in \mathbb{Z}$ 、 $m \le 0$ に対して
$\varphi(m) \varphi(n) - \varphi(n)\varphi(m) = (\varphi(m) + \varphi(1)) \varphi(n) - \varphi(n) - \varphi(n)\varphi(m) \\ = (\varphi(m) + \varphi(1)) \varphi(n) - \varphi(n) (\varphi(1) + \varphi(m)) \\ = \cdots = (\varphi(m) + \varphi(-m)) \varphi(n) - \varphi(n) (\varphi(-m) + \varphi(m)) = 0$
となるので

任意の $m, n \in \mathbb{Z}$ に対して $\varphi(m) \varphi(n) = \varphi(n) \varphi(m)$

となって $\varphi(\mathbb{Z})$ は乗法に関する交換法則を満たします。 $\varphi(\mathbb{Z})$ が無限集合のとき $\varphi(\mathbb{Z})$ は整数全体の環と考えることができます。

初等整数論入門 Math＆Science (ちくま学芸文庫)

作者:銀林浩
発売日: 2019/08/09
メディア: Kindle版

2020-12-30

エレファントな整数論(6)

$\mathbb{N}$ (自然数全体の集合)と数学的帰納法の関係を考察したので、ここからは数学的帰納法の原理が成り立つ $\mathbb{N}$ が存在するとして進めます。

整数の加法

$a \in \mathbb{N}$ に対して $-a$ を

$-0 = 0$
$-(a + 1) = (-a) + s^{-1}$

と定義します。 $s^{-1} = -1$ となります。

$\begin{eqnarray*} & & (-a) + (-1) = (-1) + (-a) \\ & \Leftarrow & (-(a-1)) + (-1) + (-1) = (-1) + (-(a-1)) + (-1) \\ & \Leftarrow & (-(a-1)) + (-1) = (-1) + (-(a-1)) \\ & \Leftarrow & (-(a-2)) + (-1) = (-1) + (-(a-2)) \\ & \Leftarrow & \cdots \Leftarrow (-(a-a)) + (-1) = (-1) + (-(a-a)) \Leftarrow -1 = -1 \end{eqnarray*}$

任意の $a \in \mathbb{N}$ に対して $(-a) + (-1) = (-1) + (-a)$

$(-a) + 1 = 1 + (-1) + (-a) + 1 = 1 + (-a) + (-1) + 1 = 1 + (-a)$

任意の $a \in \mathbb{N}$ に対して $(-a) + 1 = 1 + (-a)$

$a + (-b) = (a - 1) + 1 + (-b) = (a - 1) + (-b) + 1 = (a - 2) + (-b) + 2 \\ = \cdots = (a - a) + (-b) + a = (-b) + a$

(Z5) 任意の $a, b \in \mathbb{N}$ に対して $a + (-b) = (-b) + a$

$a + (-a) = (a - 1) + 1 + (-(a - 1)) + (-1) = (a - 1) + (-(a - 1)) \\ = (a - 2) + (-(a - 2)) = \cdots = (a - a) + (-(a - a)) = 0$

(Z4) 任意の $a \in \mathbb{N}$ に対して $a + (-a) = (-a) + a = 0$

$-(a + b) = (-(a + b - 1)) + (-1) = (-(a + b - 2)) + (-2) \\ = \cdots = = (-(a + b - b)) + (-b) = (-a) + (-b)$

(Z1) 任意の $a, b \in \mathbb{N}$ に対して $-(a + b) = (-a) + (-b)$
(Z6) 任意の $a, b \in \mathbb{N}$ に対して $(-a) + (-b) = (-b) + (-a)$

$a \ge b$ のとき $a = b + c$ となる $c \in \mathbb{N}$ が存在します。 $c = a \setminus b$ と書くと

(Z2) 任意の $a, b \in \mathbb{N}$ に対して $a + (-b) = b + c + (-b) = c = a \setminus b$
(Z3) 任意の $a, b \in \mathbb{N}$ に対して $(-a) + b = (-(b + c)) + b = (-c) + (-b) + b = -c = -(a \setminus b)$

となります。

$\mathbb{N}$ は可換なモノイドなので、 $\mathbb{N}^- = \{ -a \mid a \in \mathbb{N} \}$ 、 $\mathbb{Z} = \mathbb{N} \cup \mathbb{N}^-$ とおくと(Z1)、(Z2)、(Z3)より $\mathbb{Z}$ は $+$ (写像の合成)に関して閉じています。(Z4)より逆元が存在するので $\mathbb{Z}$ は群となります。 $\mathbb{Z}$ は $1$ を含む最小の(全単射全体の群の)部分群となります。(Z5)、(Z6)より $\mathbb{Z}$ はアーベル群となります。

$a, b \in \mathbb{Z}$ に対して $a - b = a + (-b)$ と定義します。(Z2)より $a, b \in \mathbb{N}$ 、 $a \ge b$ のとき $a - b = a \setminus b$ となります。

初等整数論入門 Math＆Science (ちくま学芸文庫)

作者:銀林浩
発売日: 2019/08/09
メディア: Kindle版

エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

エレファントな整数論(11)

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

一般の整域の場合

エレファントな整数論(10)

整域

ユークリッド整域

単項イデアル整域

素イデアル

単位元を持つ自明ではない可換環 $R$ のイデアル $P$ が素イデアルであることは、以下の条件(条件2)と同値となります。

素元

既約元

素元は既約元となります。

$n, m \ge 1$ とし、 $p_1, p_2, \cdots , p_n$ 、 $q_1, q_2, \cdots , q_m$ を $R$ の素元とします。 $p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_m$ ならば $n = m$ であり、適当に並べ替えると任意の $1 \le i \le n$ に対して $(p_i) = (q_i)$ となります。

一意分解整域

一意分解整域の既約元は素元となります。

単項イデアル整域は一意分解整域となります。

エレファントな整数論(9)

ユークリッド整域

ユークリッドの互除法

エレファントな整数論(8)

剰余類

環と半環

最大公約数

今後の課題

数学的帰納法の記法

可換な和、行または列が可換な行列

圏論、直積、極限

複素数の極限

体上の代数

群の計算

今後の予定

エレファントな整数論(7)

群による整数の加法

群による整数の乗法

エレファントな整数論(6)

整数の加法

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

一般の整域の場合

整域

ユークリッド整域

単項イデアル整域

素イデアル

単位元を持つ自明ではない可換環 のイデアル が素イデアルであることは、以下の条件(条件2)と同値となります。

素元

既約元

素元は既約元となります。

とし、、 を の素元とします。 ならば であり、適当に並べ替えると任意の に対して となります。

一意分解整域

一意分解整域の既約元は素元となります。

単項イデアル整域は一意分解整域となります。

ユークリッド整域

剰余類

環と半環

最大公約数

数学的帰納法の記法

可換な和、行または列が可換な行列

圏論、直積、極限

複素数の極限

体上の代数

群の計算

今後の予定

群による整数の加法

群による整数の乗法

整数の加法

単位元を持つ自明ではない可換環 $R$ のイデアル $P$ が素イデアルであることは、以下の条件(条件2)と同値となります。

$n, m \ge 1$ とし、 $p_1, p_2, \cdots , p_n$ 、 $q_1, q_2, \cdots , q_m$ を $R$ の素元とします。 $p_1 p_2 \cdots p_n = q_1 q_2 \cdots q_m$ ならば $n = m$ であり、適当に並べ替えると任意の $1 \le i \le n$ に対して $(p_i) = (q_i)$ となります。