エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

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

ユークリッド整域

 R を整域とします。

  • (1) (除法の原理)  a, b \in R b \ne 0 とすると以下のような  q, r \in R が存在する。
    •  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) と書くことができます。

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