08.01 Euclidean domains

Definition. norm

• $R$,
  • integral domain
• $N: R \rightarrow \mathbb{Z}_{\ge 0}$,

$N$ is said to be norm on the integral domain $R$ if $N(0) = 0$. If $N(a) > 0$ for $a \neq 0$, $N$ is called a positive norm

■

Definition. euclidian domain

• $R$,
  • integral domain

$R$ is said to be a Euclidean Domain (or possess a Division Algorithm) if there is a norm $N$ on $R$ such that

\[\begin{eqnarray} \forall a \in R, \ \forall b \neq 0 \n R, \ \exists q, r \in R, \ & & a = qb + r \nonumber \\ & & r = 0 \text{ or } N(r) < N(b) . \nonumber \end{eqnarray}\]

The $q$ is called the quotient. The $r$ is called the remainder of the division.

■

Remark

Euclidean Algorithm holds in any euclidian domain.

\[\begin{eqnarray} a & = & q_{0}b + r_{0} \nonumber \\ b & = & q_{1}r_{0} + r_{1} \nonumber \\ r_{0} & = & q_{2}r_{1} + r_{2} \nonumber \\ \vdots \nonumber \\ \nonumber \\ r_{n-2} & = & q_{n}r_{n-1} + r_{n} r_{n-1} & = & q_{n + 1}r_{n} \nonumber \end{eqnarray}\]

Such $r_{n}$ exists since $N(b) > N(r_{0}) > \cdots > N(r_{n}) = 0$.

■

Examples

■

Proposition 1.

• $R$,
  • euclidian domain
• $I \subseteq R$,
  • ideal

Then $I$ is principal. That is,

\[\exists d \in I, \text{ s.t. } I = (d) .\]

Moreover, for every non zero ideal $I$,

\[\begin{eqnarray} \exists d \neq \in I \text{ s.t. } I = (d), \ N(d) = \min \{ N(a) \mid a \in I \} . \end{eqnarray}\]

proof.

If $I$ is zero ideal, we have nothing to prove. Suppose that $I$ is not zero ideal. Let

\[d \in \arg\min_{a \in I} \{ N(a) \} .\]

Clearly, $(d) \subseteq I$, We show that $(d) \supseteq I$. Let $a \in I$. Using Division Algorithm we have

\[a = qd + r\]

where $N(r) = 0$ or $N(r) < N(d)$. Since $r = a - qd$. $r \in I$. $N(d)$ is the minimal norm in $I$ so that $N(r) = 0$. Hence $r = 0$ and $a = qd \in (d)$.

$\Box$

Remark

Applying Proposition1 to $\mathbb{Z}$, every ideal in $\mathbb{Z}$ is principal.

■

Definition. divisor

• $R$,
  • commutable ring
• $a, b \in R$,
  • $b \neq 0$,

(1) $a$ is said to be a multiple of $b$ if

\[\exists x \in R \text{ s.t. } a = bx .\]

In this case $b$ is said to divide $a$ or be a divisor of $a$, written $b \mid a$.

(2) $d \neq 0 \in R$ is said to be a greatest comon divisor of $a$ and $b$ if

• (i) $d \mid a$, $d \mid b$,
  • common divisor
• (ii) If $d^{\prime} \mid a$, $d^{\prime} \mid b$, $d^{\prime} \mid d$.
  • the greatest

■