---

（例題） ガウス整数環 Z[i] = { a+bi | a,b ∈ Z } において -1+12i と 4+7i の最大公約元を求めよ。

---

（考察） Z[i] はユークリッド整域なので、 互除法を用いて、最大公約元を求めることができます。

---

ガウス整数環での互除法
( a + bi ) を ( c + di ) で割るときは複素数体上で割って有理化し、 s + ti ( s,t は有理数 ）と表して、
s,t に最も近い整数を m,n とすれば、 ( m + ni ) が商、( a + bi ) - ( c + di )( m + ni ) が余りになります。

---

（解答例） 互除法を用いれば、
( -1 + 12i ) = ( 4 + 7i )( 1 + i ) + ( 2 + i )
( 4 + 7i ) = ( 2 + i )( 3 + 2i )
よって、( 2 + i ) が最大公約元です。

---

単項イデアル整域において、最大公約元は単元倍を除いて一意的でした。
また、Z[i] の単元は { ±1, ±i } なので 最大公約元は {±( 2 + i ), ±( 1 - 2i) } であることがわかります。

---

もともとの質問は 「ガウス整数環 Z[i] での最大公約元はどうやって求めるんですか？」

---

（命題） 　 ガウスの整数環 Z[i] はユークリッド整域である。

---

（確認） 複素数 a + bi に対して、a²+b² を 対応させる写像を f とします。 （絶対値の２乗）
このとき f(xy)= f(x)f(y) for ∀x,y ∈ C に注意しましょう。

---

f は Z[i] から整列集合 N ∪{0} への写像であり
(E1) f(0) = 0 < f(w)　for　0 ≠∀ w ∈ Z[i] を満たします。
A = a + bi, B = c + di ∈ Z[i] (0 ≠B) に対して、
複素数 A/B の分子分母に分母の共役複素数をかければ、 s + ti (s,t ∈ Q ) と表せます。
このとき、s,t に最も近い整数を m,n とすれば、 (s-m) ≦ 1/2 かつ (t-n) ≦ 1/2 が成り立ち、
f(A/B-q) < (s-m)²+(t-n)² ≦ 1/4 + 1/4 < 1 となります。
よって、q = ( m + n i ), r = (A - Bq) とおけば。
f(r) = f(A-Bq) =f(B(A/B-q))=f(B)f(A/B-q) < f(B) となります。
(E2) ∃ q.r ∈ Z[i] 　such that　 A = Bq+r 　and　 かつ f(r) < f(B).
したがって、Z[i] はユークリッド整域です。

---

ユークリッド整域 R においては 互除法によって最大公約元が求められます。

---

ユークリッド整域 R は単項イデアル整域なので、 任意の（０でない）２元 a と b に対して、
Ra + Rb = Rd となる元 d が存在します。 この d が最大公約元です。 （確認）

---

A₀=a,A₁=b,として互除法によって、
A₀ = A₁q₁+A₂
A₁ = A₂q₂+A₃

A_i-1 = A_iq_i+A_i+1

と求めれば、 f(A₁) > f(A₂) > ... > f(A_n) > f(A_n+1) = 0 となる n が存在します。
この時、A_n が a と b の最大公約元になります。

---

（確認） Ra+Rb を (a,b) と書くことにします。
任意の i (1 ≦ i ≦ n) に対して、
A_i-1 = A_iq_i+A_i+1 だから、 (A_i-1,A_i) = (A_i,A_i+1) となります。よって
(a,b)=(A₀,A₁) = (A₁,A₂) = ...= (A_n-1,A_n) = (A_n,A_n+1) = (A_n)
となります。 主張が得られます

---