エレファントな整数論(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)$ と書くことができます。