Euclidean Domain
2020-2학기, 대학에서 ‘현대대수1’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)
이번 파트에서는 Division Algorithm 에 대한 일반화를 다룬다.
Euclidean Norm & Euclidean Domain
Definition.
A Euclidean norm on an integral domain $D$
is a function $\nu$ mapping the non-zero elements of $D$ into the non-negative integers
such that the following conditions are satisfied:
-
For all $a, b \in D$ with $b \ne 0$, there exist $q$ and $r$ in $D$ s.t. $a = bq + r$, where either $r = 0$ or $\nu(r) = \nu(b)$.
-
For all non-zero $a, b \in D$, $\nu(a) \le \nu(ab)$.
“Euclidean norm”을 다른 말로 “Euclidean valuation”이라고도 한다.
Definition.
An integral domain $D$ is an “Euclidean Domain”
if $\exists$ a Euclidean norm on $D$.
Example.
Example.
Theorem 46.4
Every Euclidean Domain is a PID.
proof.
Let $D$ be a Euclidean Domain with a Euclidean norm $\nu$.
Let $N$ be an ideal in $D$.
If $N = \{ 0 \}$, then $N = \left< 0 \right>$ and $N$ is principal.
Supp. that $N \ne \{ 0 \}$.
Then there exist some $b \ne 0$ in $N$ s.t. $\nu (b) \le \nu (n)$ for all $n \in N$.
Claim: $N = \left< b \right>$.
Let $a \in N$, then by Condition 1 for E.D.,
there exist $q$ and $r$ in $D$ s.t.
\[a = bq + r\]where either $r = 0$ or $\nu (r) < \nu (b)$.
$r = a - bq$에 대해 $a, b \in N$이므로 $r \in N$이다.($\because$ $N$ is an ideal)
minimal $\nu(b)$로 $b$를 골랐으므로 $r$이 $\nu(r) < \nu(b)$인 경우는 불가능하다. 따라서 $r = 0$이다.
따라서 $a = bq$이다.
이것은 Ideal $N$이 principal ideal $\left< b \right>$임을 의미한다. $\blacksquare$
Corollary 46.5
Every Euclidean Domain is a UFD.
위의 정리를 통해 E.D.가 PID임을 보였다. 하지만, 일반적으로 반대 명제는 성립하지 않는다!!
PID가 E.D.가 되지 안는 경우를 찾는 것은 생각보다 쉽진 않다…
Arithmetic in Euclidean Domains
Theorem 46.5
For a E.D. with Euclidean norm $\nu$,
-
$\nu(1)$ is minimal among all $\nu(a)$ for non-zero $a \in D$.
-
$u \in D$ is a unit $\iff$ $\nu(u) = \nu (1)$.
proof.
(1번 명제에 대한 증명)
Euclidean norm $\nu$의 두번재 조건에 의하면 아래가 성립한다.
\[\nu(1) \le \nu(1a) = \nu(a)\]$\blacksquare$
(2번 명제에 대한 증명)
if $u$ is a unit in $D$, then
\[\nu (u) \le \nu (u u^{-1}) = \ne (1)\]반대로 $\nu (u) = \nu (1)$라면, division algorithm에 의해 아래의 식이 성립한다.
\[1 = uq + r\]where either $r=0$ or $\nu(r) < \nu(u)$
이때, $\nu(1)$은 E.D.의 모든 원소에 대해 minimal이고, $\nu(u) = \nu(1)$이므로 $\nu(r) < \nu(u)$인 경우는 불가능하다.
따라서 $r=0$이 되고, $1 = uq$이므로 $u$는 unit이다.
$\blacksquare$
Example.
For $\mathbb{Z}$, $\nu(n) = \left| n \right|$.
$\min \nu (n) = 1 = \nu (1)$.
when $\nu(n) = 1$, $n = 1, -1$.
그리고 $1, -1$은 $\mathbb{Z}$에서 unit이다.
Example.
$F[x]$, for non-zero $f(x)$, $\nu(f(x)) = \deg f(x)$.
$\min \ne(f(x)) = 0$.
$\nu(f(x)) = 0 = \nu (1)$ $\iff$ $f$: const
Therefore, $\mathcal{U}(F[x]) = F^{*}$.
Euclidean Algorithm
“유클리드 알고리즘”은 두 정수의 GCD를 찾는 알고리즘이다.
이 알고리즘을 정수 집합 $\mathbb{Z}$을 일반화한 Euclidean Domain에서 적용하여, “Euclidean Domain에서 GCD를 찾는 알고리즘”으로 일반화 할 수 있다!!
수업 때 다루지는 않았어서, 본 글에서는 짧게 언급하고 넘어가겠다.
$\mathbb{Z}$와 $F[x]$는 대표적인 Euclidean Domain이다.
다음 포스트에선 조금 특별하고 중요한 Euclidean Domain인 “Gaussian Integer”에 대해 다룬다. link