【２】ユークリッドの互除法

ユークリッド整域とは，ある数体系内で，除法

　　α＝β・γ＋δ，｜δ｜＜｜β｜

は可能かという問題です．複素数版のユークリッドの互除法でも割り算の余りδが｜δ｜＜｜β｜として表現されれば，アルゴリズムが定義できます．ここでは，Ｚ（√−ｄ）整数の体系内で，除法

　　α＝β・γ＋δ，｜δ｜＜｜β｜

は可能かというユークリッド整域の問題を考えてみます．

Ｑ（√−ｄ）の部分集合Ｚ（√−ｄ）は

　　Ｚ（√−ｄ）＝｛ａ＋ｂ√−ｄ｜ａ，ｂは整数｝

で定義されます．Ｚ（√−ｄ）は複素平面内で幅１×高さ√ｄの直交格子を形成しますから，β^-1αに最も近いＺ（√−ｄ）の整数γが１未満にあるためには，

ｌ^2＝（√ｄ／２）^2＋（１／２）^2

　　ｄ＝１のとき，√２／２＜１（ユークリッド整域）ガウス整数環

　　ｄ＝２のとき，√３／２＜１（ユークリッド整域）

ｄ≧３のときユークリッド整域でないことが幾何学的に証明されます．

Ｚ（√−３）はユークリッド整域ではありませんが，それではＺ（（−１＋√−ｄ）／２）はどうでしょうか？　　これは複素平面内で斜交格子を形成し，その菱形の４頂点は

（０，√−ｄ，（１＋√−ｄ）／２，（−１＋√−ｄ）／２）

β^-1αに最も近いＺ（√−ｄ）の整数γが１未満にあるためには，　

ｌ^2＝（√ｄ／２−ｌ）^2＋（１／２）^2

　　−ｌ√ｄ＋（ｄ＋１）／４＝０

　　ｌ＝（ｄ＋１）／４√ｄ

　　ｄ＝３のとき，１／√３＜１（ユークリッド整域）アイゼンシュタイン整数環

　　ｄ＝７のとき，２／√７＜１（ユークリッド整域）

　　ｄ＝１１のとき，３／√１１＜１（ユークリッド整域）

以上より，Ｚ（√−ｄ）の整数環がユークリッド整域となるのは，

　　ｄ＝１，２，３，７，１１

の５つの場合に限ります．ユークリッド整域→一意性整域が成り立つは真ですが，逆は成り立ちません．一意分解性をもつが，ユークリッド整域ではないもの（単項イデアル整域）は，

　　ｄ＝１９，４３，６７，１６３

に対応するものです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

斜交格子の４頂点は

（０，√−ｄ，（１＋√−ｄ）／２，（−１＋√−ｄ）／２）

ｄ＞1であるから縦長菱形

この菱形の内部の点で、格子点から最も離れた点を求めることになる

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝