유클리드 정역

유클리드 정역

Definition 0.1. D는 정역이고 Z^≥0는 음이 아닌 정수들의 집합이라고 하자. 함수 ν : D → Z^≥0가 다음 조건을 만족하면 ν를 Euclidean valuation이라고 한다.

(1) 임의의 a, b ∈ D, b 6= 0_D에 대해 ∃ q, r ∈ D such that a = bq + r이고 r = 0_D 또는 ν(r) < ν(b)

(2) 임의의 a, b ∈ D, a 6= 0D, b 6= 0D에 대해 ν(a) ≤ ν(ab)

그리고 Euclidean valuation을 가지는 정역을 유클리드 정역(Euclidean domain) 이라고 한다.

Example 0.2. 함수 ν : Z → Z^≥0을 ν(n) := |n|으로 정의하면 ν는 Euclidean valu- ation이 된다. 따라서 Z는 유크리드 정역이 된다.

Example 0.3. F 가 체일 때 함수 ν : F [x] → Z^≥0을 ν(f (x)) := deg f (x)으로 정의 하면 ν는 Euclidean valuation이 된다. 따라서 F [x]는 유크리드 정역이 된다.

Theorem 0.4. 모든 유클리드 정역은 PID이다.

Proof. D는 Euclidean valuation ν를 가지는 유클리드 정역이라고 하자. 그리고 N 을 D의 아이디얼이라고 하자. 만일 N = {0_D}이면 N 은 주아이디얼이다. 이제 N 6= {0_D}이라고 하자. 그리고 b ∈ N 를

ν(b) = min{ν(x) | x ∈ N }

을 만족하는 N 의 0_D 아닌 원소라고 하자. 이제 a ∈ N 이라고 하자. 그러면 Eu- clidean valuation의 조건(1)에 의해

∃ q, r ∈ D such that a = bq + r이고 r = 0_D 또는 ν(r) < ν(b)

이다. 그러면 a, b ∈ N 이고 N 은 아이디얼이므로 r = a − bq ∈ N 이다. 따라서 r = 0_D이어야 한다. 그러므로 a = bq이고 결국 a ∈< b >이다. 즉, N =< b >이다.

Corollary 0.5. 모든 유클리드 정역은 UFD이다.

Theorem 0.6. D는 Euclidean valuation ν를 가지는 유클리드 정역이라고 하자.

그러면

ν(1_D) = min{ν(a) | a ∈ D, a 6= 0_D}

이다. 그리고 u ∈ D가 단원이 되는 필요충분조건은 ν(u) = ν(1_D)이 되는 것이다.

Proof. 임의의 a ∈ D, a 6= 0_D에 대해 Euclidean valuation의 조건(2)를 적용하면 ν(1_D) ≤ ν(1_Da) = ν(a)

이다.

이제 u ∈ D를 단원이라고 하자. 그러면 Euclidean valuation의 조건(2)에 의해 ν(u) = ν(uu⁻¹) = ν(1_D)

이다.

역으로 u ∈ D, u 6= 0_D에 대해 ν(u) = ν(1_D)이라고 하자. 1_D를 u로 나누면

∃ q, r ∈ D such that 1_D = uq + r, r = 0_D 또는 ν(r) < ν(u)

이다. ν(r) = ν(1_D의 최솟값 성질에 의해 r = 0_D일 수 밖에 없다. 결국 1_D = uq 에서 u는 단원이 된다.

우리는 자연수에서 정의된 최대공약수의 개념을 ±1의 곱을 무시하면 정수로 확 장할 수 있다. 여기서는 일반적인 PID에서 이런 최대공약수의 개념을 공부해 본다.

Definition 0.7. D는 UFD라고 하자. a, b ∈ D에 대해 다음을 만족하는 d ∈ D를 a, b의 최대공약수(greatest commom divisor) 라고 하고 gcd(a, b)로 표기한다.

(1) d|a 이고 d|b

(2) c|a 이고 c|b 이면 c|d 이다.

* 단원들을 곱하는 개념을 제외하면 최대공약수는 유일하게 결정된다.

Example 0.8. (1) Z에서 gcd(18, 48) = ±6이다.

(2) Z[x]에서 gcd(x²− 2x + 1, x²+ x − 2) = ±(x − 1)이다.

(3) Q[x]에서 gcd(x²− 2x + 1, x²+ x − 2) = a(x − 1), a ∈ (Q − {0})이다.

Theorem 0.9. D는 PID이고 a, b ∈ D는 0_D가 아니라고 하자. 그러면 gcd(a, b)가 존재한다. 그리고 gcd(a, b) = λa + µb을 만족하는 λ, µ ∈ D가 존재한다.

Proof. N := {ra + sb | r, s ∈ D}이라고 하자. 그러면 N 은 D의 아이디얼이 됨을 쉽게 확인할 수 있다. 따라서 N =< d >이 되는 d ∈ D가 존재한다. s = 0_D, r = 1_D 이면 d|a이고 s = 1_D, r = 0_D이면 d|b이다. 그리고 d는 N 의 원소이므로 N = λa+µb 을 만족하는 λ, µ ∈ D가 존재한다. 만일 c|a 이고 c|b이면 c|(λa+µb)이므로 c|d이다.

따라서 d = gcd(a, b)이다.

위의 정리에서 증명은 gcd(a, b)를 구하는 것은 제공하지 못한다. 그런 측면에서 다음 정리는 훨씬 좋은 정보를 가지고 있다고 볼 수 있다. 우리는 증명 없이 다음 정리를 사용한다.

Theorem 0.10. (Euclidean Algorithm) D는 Euclidean valuation ν를 가지는 유클리드 정역이라고 하자. 그리고 a, b ∈ D는 0_D가 아니라고 하자. Euclidean valuation 조건(1)에서

a = bq₁+ r₁, r₁ = 0_D 또는 ν(r₁) < ν(b) 이다. 만일 r₁ 6= 0_D이면

b = r₁q₂+ r₂, r₂ = 0_D 또는 ν(r₂) < ν(r₁) 이다. 이런 과정을 계속하면

r_i−1= r_iq_i+1+ r_i+1, r_i+1= 0_D 또는 ν(r_i+1) < ν(r_i)

을 얻는다. 만일 r₁ = 0_D이면 b = gcd(a, b)이다. 만일 r₁ 6= 0_D이면 최초로 0_D이 되는 r_s가 존재한다. 이 때 gcd(a, b) = r_s−1이다.

Example 0.11. gcd(22471, 3266) 구하기;

22471 = 3266 · 6 + 2875 3266 = 2875 · 1 + 391

2875 = 391 · 7 + 138 391 = 138 · 2 + 115

138 = 115 · 1 + 23 115 = 23 · 5 + 0 따라서 gcd(22471, 3266) = 23이다.

<조별 도전 문제>

1. N = {a + xf (x) | a ∈ 2Z, f (x) ∈ Z[x]}는 Z[x]의 아이디얼이 됨을 보여라.

2. Z[x]는 PID가 되는가?

3. Z[x]는 유클리드 정역이 되는가?

Definition 0.12. (가우스 정수(Gaussian Integer)) 복소수 i에 대해 a+bi, a, b ∈ Z을 가우스 정수(Gaussian integer)라고 한다. 그리고 가우스 정수 α = a + bi에 대해 N (α) := a²+ b²을 α의 norm이라고 한다. 모든 가우스 정수들의 집합을 Z[i]

으로 표기한다.

Lemma 0.13. Z[i]에서 norm N 에 대해 다음이 성립한다.

(1) N (α) ≥ 0, ^∀α ∈ Z[i].

(2) N (α) = 0 ⇔ α = 0.

(3) N (αβ) = N (α)N (β), ^∀α, β ∈ Z[i].

Lemma 0.14. Z[i]는 정역이다.

Proof. α, β ∈ Z[i]에 대해 αβ = 0이라고 하자. 그러면 N (αβ) = N (α)N (β) = N (0) =)0

이다. 따라서 N (α) = 0 또는 N (β) = 0이다. 그러므로 α = 0 또는 β = 0이다.

Theorem 0.15. 함수 ν : Z[i] → Z^≥0을 ν(α) = N (α)으로 정의하면 ν는 Euclidean valuation이 된다. 따라서 Z[i]는 유클리드 정역이 된다.

Proof. ν가 Euclidean valuation임을 보이기 위해 조건(1)의 나눗셈 알고리듬 부분 만 보이면 나머지 부분은 쉽게 증명된다. 이제 α = a₁+ a₂i, β = b₁ + b₂i이라고 하자. 그러면

∃ q, r ∈ Z[i] such that α = βq + r, r = 0 또는 N(r) < N(β) 이 됨을 보이면 된다. q = q₁+ q₂i이라고 두자. 그러면

r = (a1+ a2i) − (b1+ b2i)(q1+ q2i)

= (a₁ − b₁q₁+ b₁q₂) + (a₂− b₁q₂− b₂q₁)i

이 된다. 이제

N (r) = (a₁− b₁q₁ + b₁q₂)² + (a₂− b₁q₂− b₂q₁)² < b²₁+ b²₂ 이 되기 위해서는

(a₁− b₁q₁+ b₁q₂)²

b²₁+ b²₂ +(a₂− b₁q₂− b₂q₁)² b²₁+ b²₂ < 1 이어야 한다. 그런데

(a₁− b₁q₁+ b₁q₂)² b²₁+ b²₂

은 좌표평면에서 점 (q₁, q₂)와 직선 a₁− b₁X + b₂Y = 0 사이의 거리의 제곱이고 (a₂− b₁q₂− b₂q₁)²

b²₁+ b²₂ < 1

은 점 (q₁, q₂)와 직선 a₂− b₂X − b₁Y 사이의 거리의 제곱이므로 결국 q를 구한다는 것은 위의 두 직선의 교점과 거리가 1 보다 작고 정수 좌표를 가지는 점 q를 구하 는 것과 같은 것이 된다. 그런데 이런 점은 항상 찾을 수 있으므로 q가 존재하고 따라서 조건을 만족하는 r도 존재한다.

Example 0.16. Z[i]에서 단위원은 1이다. 따라서 N (1) = 1 = N(α) 이 되는 α는 단원이다. α = a₁ + a₂i 이라고 두면 a²₁ + a²₂ = 1 일 때 a₁ = ±1, a₂ = 0 이거나 a₁ = 0, a₂ = ±1 이다. 따라서 Z[i]의 단원들은 ±1, ± i 들이다.

5는 Z 상에서 기약임을 알고 있다. 그러면 5가 Z[i] 상에서도 기약이 되는지 알아 보자. Z[i]에서

5 = (1 + 2i)(1 − 2i) = (2 + i)(2 − i)

이고 1 + 2i, 1 − 2i들은 단원이 아니므로 5는 Z[i]에서 기약이 아님을 알 수 있다.