エレファントな整数論(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$ となります。