Euclid整域
概要
Euclid整域（Euclidean domain）とは、元の大きさを測る写像 $\phi$（Euclid 写像）を備え、任意の $a$ と $b\neq0$ に対し $a=qb+r$、$\phi(r)<\phi(b)$ という除法の原理が成り立つ整域のことである。整数環 $\mathbb{Z}$（絶対値）、体上の多項式環 $K[X]$（次数）、Gauss 整数環 $\mathbb{Z}[i]$（ノルム）、離散付値環（付値）が代表例である。除法を繰り返す Euclid の互除法で最大公約元と Bezout の等式の係数が有限回で求まり、イデアルは大きさ最小の元で生成されるので、Euclid 整域は単項イデアル整域である。逆は成り立たず、$\mathbb{Z}[(1+\sqrt{-19})/2]$ は単項イデアル整域だがどの写像に関しても Euclid 整域でない。
定義
本記事で環とは 単位元 をもつ可換環を指す。$R$ を整域とする。
整域 $R$ が Euclid 整域（Euclidean domain）であるとは、写像 $\phi\colon R\to\mathbb{Z}$ で次の 3 条件を満たすものが存在することをいう。
- 任意の $x\in R$ について $\phi(x)\ge0$ であり、$\phi(x)=0$ となるのは $x=0$ のときに限る。
- 任意の $a,b\in R\setminus\{0\}$ について $\phi(ab)\ge\phi(a)$。
- （除法の原理）任意の $a,b\in R$、$b\neq0$ に対し、
$$a=qb+r,\qquad\phi(r)<\phi(b)$$
を満たす $q,r\in R$ が存在する。
このような $\phi$ を $R$ の Euclid 写像（Euclidean function）、条件 3 の $q$ を商、$r$ を剰余（余り）という。
条件 1 により $\phi(0)=0<\phi(b)$ なので、条件 3 は「$r=0$ であるか、または $r\neq0$ かつ $\phi(r)<\phi(b)$」と読める。文献によっては $\phi$ を $R\setminus\{0\}$ 上でだけ定義し、条件 3 をこの形で述べる。また条件 2 を課さない流儀もあるが、条件 2 は条件 1・3 から Euclid 写像を取り替えることで回復できるので（euclidean-domain-prop-redundancy）、どちらの流儀でも Euclid 整域のクラスは同じである。
Euclid 写像の呼称は文脈によって変わる。代数体の 整数環 では複素数の 絶対値 の 2 乗（ノルム）、多項式環 では次数、離散付値環 では付値が Euclid 写像の役割を果たし、それぞれ「Euclid ノルム」「次数」「付値」と呼ばれる。多項式の次数 $\deg$ は $\deg0$ が定義されない（あるいは $-\infty$）ので厳密には条件 1 を満たさないが、$\phi(f)=1+\deg f$（$f\neq0$）、$\phi(0)=0$ と $1$ を足せば条件 1 が満たされ、除法の原理の議論には影響しない。そのため「次数によって Euclid 整域になる」という言い方が広く用いられる。
直感
Euclid 整域とは、元の「大きさ」を測る関数 $\phi$ があって、どの元もそれより小さい大きさの余りを残して割り算できる整域である。$a$ を $b$ で割った余り $r$ は $b$ より真に小さいので、次に $b$ を $r$ で割り、さらにその余りで割り、と続けると大きさが真に減少する非負整数の列ができ、有限回で余りが $0$ になる。これが Euclid の互除法であり、最後に残った $0$ でない余りが $a$ と $b$ の 最大公約元 を与える（euclidean-domain-prop-algorithm）。同じ議論はイデアルにも適用でき、イデアルの $0$ でない元のうち大きさ最小のものがイデアル全体を生成する。したがって Euclid 整域は必ず 単項イデアル整域 である（euclidean-domain-prop-pid）。逆は成り立たず、どのような $\phi$ を取っても除法の原理が成り立たない単項イデアル整域がある（euclidean-domain-prop-not-euclidean）。Euclid 整域は「割り算の手続きが具体的に実行できる」という計算上の性質を公理にした概念であり、単項イデアル整域より真に強い。
例
整数環 $\mathbb{Z}$ は絶対値 $\phi(x)=|x|$ を Euclid 写像とする Euclid 整域である。条件 1・2 は $|ab|=|a|\,|b|\ge|a|$（$b\neq0$）から明らかである。条件 3 を示す。$a,b\in\mathbb{Z}$、$b\neq0$ とし、集合 $\{|a-qb|\mid q\in\mathbb{Z}\}$ の最小値を与える $q$ を取り、$r:=a-qb$ とおく。$|r|\ge|b|$ と仮定すると、$r$ と $b$ の符号が同じなら $|r-b|=|r|-|b|<|r|$、異なるなら $|r+b|=|r|-|b|<|r|$ となり、$q$ を $q+1$ または $q-1$ に取り替えると $|a-qb|$ が真に小さくなって最小性に反する。よって $|r|<|b|$ である。
剰余は一般に一意に定まらない。例えば
$$4=3\cdot1+1=3\cdot2+(-2)$$
において $\phi(1)=1$ と $\phi(-2)=2$ はともに $\phi(3)=3$ より小さいので、$1$ と $-2$ はどちらも $4$ を $3$ で割った剰余である。$\mathbb{Z}$ では剰余を $0\le r<|b|$ に限定して一意性を回復するのが普通であるが、これは $\mathbb{Z}$ に固有の約束である。
体 $K$ 上の 1 変数多項式環 $K[X]$ は
$$\phi(f):=\begin{cases}1+\deg f&(f\neq0)\\0&(f=0)\end{cases}$$
を Euclid 写像とする Euclid 整域である。条件 2 は $\deg(fg)=\deg f+\deg g$ から、条件 3 は多項式の除法の原理から従う（多項式環 の記事の定理「除法の原理」）。$\mathbb{Z}$ の場合と異なり、$K[X]$ では商と剰余が一意に定まる（同定理の一意性の部分）。これは $\deg r<\deg g$ という条件が $r$ を「次数が下がるまで引き続ける」操作の結果として一意に定めるためである。
Gauss整数環 $\mathbb{Z}[i]=\{a+bi\mid a,b\in\mathbb{Z}\}\subset\mathbb{C}$ は、ノルム $N(a+bi):=a^2+b^2=|a+bi|^2$ を Euclid 写像とする Euclid 整域である。$N$ は非負整数値で $N(\alpha)=0$ となるのは $\alpha=0$ のときに限り、$N(\alpha\beta)=|\alpha\beta|^2=N(\alpha)N(\beta)\ge N(\alpha)$（$\beta\neq0$）なので条件 1・2 が成り立つ。条件 3 を示す。$\alpha,\beta\in\mathbb{Z}[i]$、$\beta\neq0$ とし、複素数 $\alpha/\beta=u+vi$（$u,v\in\mathbb{Q}$）を考える。$u,v$ にもっとも近い整数 $m,n$ を取ると $|u-m|\le1/2$、$|v-n|\le1/2$ である。$q:=m+ni$、$r:=\alpha-q\beta$ とおくと $r\in\mathbb{Z}[i]$ であり、
$$N(r)=|\beta|^2\left|\frac{\alpha}{\beta}-q\right|^2=N(\beta)\bigl((u-m)^2+(v-n)^2\bigr)\le\frac{N(\beta)}{2}< N(\beta)$$
である。同じ議論は $\mathbb{Z}[\sqrt{-2}]$ や、$\omega=(-1+\sqrt{-3})/2$ に対する $\mathbb{Z}[\omega]$（Eisenstein 整数環）でも成り立つ（DF04 §8.1）。
$R$ を 離散付値環、$v\colon R\to\mathbb{Z}_{\ge0}\cup\{\infty\}$ をその付値とする（付値環）。$\phi(x):=1+v(x)$（$x\neq0$）、$\phi(0):=0$ とおくと $R$ は Euclid 整域である。条件 2 は $v(ab)=v(a)+v(b)\ge v(a)$ による。条件 3 について、$a,b\neq0$ とすると、$v(a)\ge v(b)$ なら $v(a/b)\ge0$ より $a/b\in R$ で $a=(a/b)\,b+0$、$v(a)< v(b)$ なら $a=0\cdot b+a$ で $\phi(a)<\phi(b)$ である。例えば $p$ 進付値環 $\mathbb{Z}_{(p)}$ と体 $k$ 上の 形式冪級数環 $k[\![t]\!]$ は Euclid 整域である。
- $\mathbb{Z}[X]$ と、体 $K$ 上の 2 変数多項式環 $K[X,Y]$ は整域である（満たす性質）が、単項イデアル整域でないので（多項式環 の記事の例「単項イデアル整域でない多項式環」）、euclidean-domain-prop-pid により Euclid 整域でない（満たさない性質）。すなわち「整域 $\Rightarrow$ Euclid 整域」は成り立たない。
- $\omega:=(1+\sqrt{-19})/2$ とする。$\omega^2=\omega-5$ なので $R:=\mathbb{Z}[\omega]=\{a+b\omega\mid a,b\in\mathbb{Z}\}$ は $\mathbb{C}$ の部分環であり、虚2次体 $\mathbb{Q}(\sqrt{-19})$ の整数環である。$R$ は単項イデアル整域である（満たす性質。証明は Dedekind–Hasse ノルム（単項イデアル整域 の記事の定義）を具体的に構成して行う。DF04 §8.2 に譲る）が、どのような写像 $\phi$ を取っても Euclid 整域でない（満たさない性質、euclidean-domain-prop-not-euclidean）。したがって「単項イデアル整域 $\Rightarrow$ Euclid 整域」は成り立たない。破れる原因は、$R$ の単元が $\pm1$ しかなく、剰余として取れる元が少なすぎることにある。
性質
Euclid 整域 $R$ の任意のイデアル $I$ は単項イデアルである。より詳しく、$I\neq0$ ならば $I$ の $0$ でない元のうち $\phi$ の値が最小のもの $b$ を取ると $I=(b)$ である。
$I=0$ なら $I=(0)$ である。$I\neq0$ とし、$\{\phi(x)\mid x\in I,\ x\neq0\}$ は正の整数の空でない集合なので最小値をもつ。それを与える $b\in I$、$b\neq0$ を取る。$(b)\subset I$ は明らかである。$a\in I$ を任意に取り、除法の原理により $a=qb+r$、$\phi(r)<\phi(b)$ と書く。$r=a-qb\in I$ であり、$r\neq0$ なら $\phi(b)$ の最小性に反するので $r=0$、すなわち $a=qb\in(b)$ である。よって $I=(b)$ である。$\square$
Euclid 整域は単項イデアル整域なので、単項イデアル整域 の記事で示される性質——Noether環 であること、$0$ でない 素イデアル が 極大イデアル であること、一意分解整域 であること——をすべてもつ。
$R$ を Euclid 整域、$\phi$ をその Euclid 写像とする。
- $\phi(1)=\min\{\phi(x)\mid x\in R,\ x\neq0\}$。
- $x\in R$ が 単元 であることと $\phi(x)=\phi(1)$ は同値である。
1。$x\neq0$ について条件 2 により $\phi(x)=\phi(1\cdot x)\ge\phi(1)$ である。
2。$x$ が単元なら $\phi(1)=\phi(xx^{-1})\ge\phi(x)\ge\phi(1)$ なので $\phi(x)=\phi(1)$ である。逆に $\phi(x)=\phi(1)$ とする。$x\neq0$ なので $1$ を $x$ で割って $1=qx+r$、$\phi(r)<\phi(x)=\phi(1)$ と書ける。1 により $\phi(r)<\phi(1)$ を満たす $r$ は $0$ に限るので $1=qx$、$x$ は単元である。$\square$
$R$ を Euclid 整域、$a,b\in R$、$b\neq0$ とする。$r_0:=a$、$r_1:=b$ とおき、$r_{t+1}\neq0$ である限り除法の原理により
$$r_{t}=q_{t}r_{t+1}+r_{t+2},\qquad\phi(r_{t+2})<\phi(r_{t+1})$$
を満たす $q_t,r_{t+2}$ を順に取る。このとき、ある $N\ge1$ で $r_{N+1}=0$ となって手続きが止まり、最後の $0$ でない剰余 $r_N$ について次が成り立つ。
- $(a,b)=(r_N)$。
- $r_N$ は $a$ と $b$ の最大公約元である。すなわち $r_N$ は $a,b$ をともに割り切り、$a,b$ をともに割り切る任意の $d\in R$ は $r_N$ を割り切る。
- $r_N=ax+by$ を満たす $x,y\in R$ が存在する（Bezout の等式）。しかも $x,y$ は手続きの各段の商 $q_t$ から具体的に計算できる。
$\phi(r_1)>\phi(r_2)>\phi(r_3)>\cdots$ は非負整数の真に減少する列なので有限で止まる。止まるのは $r_{N+1}=0$ となるときであり、そのとき $r_{N-1}=q_{N-1}r_N$ である。$b\neq0$ なので $N\ge1$ である。
1。各 $t$ について $(r_t,r_{t+1})=(r_{t+1},r_{t+2})$ である。実際 $r_t=q_tr_{t+1}+r_{t+2}$ より $r_t\in(r_{t+1},r_{t+2})$ かつ $r_{t+2}\in(r_t,r_{t+1})$ なので両辺は $(r_t,r_{t+1},r_{t+2})$ に等しい。よって $(a,b)=(r_0,r_1)=(r_{N-1},r_N)=(q_{N-1}r_N,r_N)=(r_N)$ である。
2。$a,b\in(r_N)$ なので $r_N$ は $a,b$ の公約元である。$d$ が $a,b$ をともに割り切れば $a,b\in(d)$ より $(r_N)=(a,b)\subset(d)$、すなわち $d$ は $r_N$ を割り切る。
3。$r_N\in(a,b)$ なので $r_N=ax+by$ となる $x,y$ が存在する。具体的には、$r_0=a$、$r_1=b$ から始めて $r_{t+2}=r_t-q_tr_{t+1}$ を用い、各 $r_t$ を $a,b$ の線形結合として順に書き直せばよい（拡張Euclid互除法）。$\square$
Bezout の等式は、Euclid 整域を含む Bezout環 で一般に成り立つ（Bezout環 の記事の命題「Bezout環はGCD整域である」）。Euclid 整域の特徴は、生成元 $r_N$ と係数 $x,y$ が有限回の割り算で構成できることにある。
整域 $R$ と写像 $\psi\colon R\to\mathbb{Z}$ が euclidean-domain-def の条件 1 と 3 を満たすとする。このとき
$$\phi(a):=\min\{\psi(ax)\mid x\in R,\ x\neq0\}\quad(a\neq0),\qquad\phi(0):=0$$
と定めると、$\phi$ は条件 1・2・3 をすべて満たす。したがって条件 2 を落として定義しても Euclid 整域のクラスは変わらない。
$a\neq0$ のとき、$R$ は整域なので $ax\neq0$ であり $\psi(ax)>0$、よって $\phi(a)$ は正の整数の集合の最小値として定まり $\phi(a)>0$ である。これで条件 1 が成り立つ。$a,b\neq0$ について、$\{abx\mid x\neq0\}\subset\{ay\mid y\neq0\}$（$y=bx$）なので $\phi(ab)=\min_{x\neq0}\psi(abx)\ge\min_{y\neq0}\psi(ay)=\phi(a)$ であり、条件 2 が成り立つ。
条件 3 を示す。$a,b\in R$、$b\neq0$ とする。$\phi(b)=\psi(bc)$ となる $c\neq0$ を取る。$\psi$ の除法の原理を $ac$ と $bc$ に適用して $ac=Q\,bc+r'$、$\psi(r')<\psi(bc)$ と書く。$q:=Q$、$r:=a-qb$ とおくと $rc=ac-Qbc=r'$ である。$r=0$ なら $\phi(r)=0<\phi(b)$ である。$r\neq0$ なら $\phi$ の定義から $\phi(r)\le\psi(rc)=\psi(r')<\psi(bc)=\phi(b)$ である。いずれの場合も $a=qb+r$、$\phi(r)<\phi(b)$ である。$\square$
$\omega=(1+\sqrt{-19})/2$、$R=\mathbb{Z}[\omega]$ とする。$R$ はどのような写像 $\phi\colon R\to\mathbb{Z}$ に関しても Euclid 整域でない。
$N(a+b\omega):=|a+b\omega|^2=a^2+ab+5b^2=(a+b/2)^2+\tfrac{19}{4}b^2$ とおく。$N$ は非負整数値で積を保ち（$|\alpha\beta|^2=|\alpha|^2|\beta|^2$）、$N(\alpha)=0$ となるのは $\alpha=0$ のときに限る。まず $R$ の単元は $\pm1$ に限る。$\alpha\beta=1$ なら $N(\alpha)N(\beta)=1$ より $N(\alpha)=1$ であり、$b\neq0$ なら $N(a+b\omega)\ge19/4>1$ なので $b=0$、$a^2=1$ である。逆に $N(\alpha)=1$ なら、$\alpha=a+b\omega$ の 複素共役 $\bar\alpha=a+b(1-\omega)$ は $R$ の元で $\alpha\bar\alpha=N(\alpha)=1$ なので $\alpha$ は単元である。次に $N(\alpha)=2$ または $3$ となる $\alpha\in R$ は存在しない。$b\neq0$ なら $N(\alpha)\ge19/4>3$ であり、$b=0$ なら $N(\alpha)=a^2$ は $2$ でも $3$ でもないからである。
$R$ が Euclid 写像 $\phi$ をもつと仮定する。$R$ の $0$ でも単元でもない元のうち $\phi$ の値が最小のもの $m$ を取る（$R$ は体でないのでそのような元は存在する）。任意の $x\in R$ を $m$ で割って $x=qm+r$、$\phi(r)<\phi(m)$ と書くと、$r\neq0$ なら $m$ の取り方から $r$ は単元、すなわち $r=\pm1$ である。よって $R$ のすべての元は $m$ を法として $0,1,-1$ のいずれかと合同であり、剰余環 $R/(m)$ の元の個数は $3$ 以下である。特に $R/(m)$ の 加法群 の 位数 は $2$ または $3$ なので、$2\cdot1=0$ または $3\cdot1=0$ が $R/(m)$ で成り立つ。すなわち $m$ は $2$ または $3$ を割り切る。
$m$ が $2$ を割り切るとする。$2=m\gamma$（$\gamma\in R$）と書くと $N(m)N(\gamma)=4$ で、$m$ は単元でないので $N(m)\in\{2,4\}$、$N(m)\neq2$ より $N(m)=4$、$N(\gamma)=1$ で $\gamma$ は単元、よって $(m)=(2)$ である。ところが $R$ は $1,\omega$ を基底とする 階数 $2$ の自由 $\mathbb{Z}$ 加群（自由加群）なので $R/(2)\cong(\mathbb{Z}/2\mathbb{Z})^2$ は $4$ 個の元をもち、$R/(m)$ の元の個数が $3$ 以下であることに反する。$m$ が $3$ を割り切る場合も同様に、$N(m)\in\{3,9\}$ と $N(m)\neq3$ から $(m)=(3)$ となり、$R/(3)\cong(\mathbb{Z}/3\mathbb{Z})^2$ が $9$ 個の元をもつことに反する。よって $R$ は Euclid 整域でない。$\square$
補足
除法の原理を用いた議論では、Euclid 写像の値が整数であることは本質的でなく、「値が真に減少する列は有限で止まる」こと、すなわち値域が整列集合（整列順序）であることだけが使われる。そのため Euclid 写像の値域を一般の整列集合（順序数）に取る流儀もある。
Euclid 整域の定義の条件 3 を「$a\notin(b)$ かつ $\phi(a)\ge\phi(b)$ ならば $0<\phi(pa-qb)<\phi(b)$ となる $p,q$ が存在する」と弱めたものが概 Euclid 整域であり、Euclid 整域は $p=1$ に取ることで概 Euclid 整域になる。整域が概 Euclid 整域であることと単項イデアル整域であることは同値である（単項イデアル整域 の記事の定理「概Euclid整域と単項イデアル整域の一致」）。Euclid 整域と単項イデアル整域の差を示す例の研究、および $\mathbb{Z}[\omega]$ 以外の例については PV08 を参照。虚 2 次体の整数環で Euclid 整域になるものは $d=-1,-2,-3,-7,-11$ の 5 個の $\mathbb{Q}(\sqrt{d})$ に限り、単項イデアル整域になるものはさらに $d=-19,-43,-67,-163$ を加えた 9 個に限ることが知られている（DF04 §8.1–8.2）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
