Euclidean Domains

Definition 1   An integral domain $R$ endowed with a function $d: R \longmapsto {\mbox{${\mathbb{N}}$}} \ {\cup} \ \{-{\infty}\}$ is an Euclidean domain if the following two conditions hold

• for all $a,b \in R$ with $a \neq 0$ and $b \neq 0$ we have $d(a \, b) \geq d(a)$ ,
• for all $a,b \in R$ with $b \neq 0$ there exist $q,r \in R$ such that

  $$a \ = \ bq + r \ \ \ \ {\rm and} \ \ \ \ d(r) < d(b).$$ (1)

  
  

The elements $q$ and $r$ are called the quotient and the remainder of $a$ w.r.t. $b$ (although $q$ and $r$ may not be unique). The function $d$ is called the Euclidean size.

Example 1   Here are some classical examples.

• $R = {\mbox{${\mathbb{Z}}$}}$ with $d(a) = \mid a \mid$ for $a \in {\mbox{${\mathbb{Z}}$}}$ . Here the quotient $q$ and the remainder $r$ of $a$ w.r.t. $b$ (with $b \neq 0$ ) can be made unique by requiring $r \geq 0$ (hence we have $0 \leq r < b$ ).
• $R = {\bf k}[x]$ where ${\bf k}$ is a field with $d(a) = {\deg}(a)$ the degree of $a$ for $a \in R, a \neq 0$ and $d(0) = -{\infty}$ . Uniqueness of the quotient and the remainder is easy to show in that case. Indeed

  $$a \ = \ b \, q_1 + r_1 \ = \ b \, q_2 + r_2 \ \ {\rm with} \ \ {\deg}(r_1) < {\deg}(b) \ \ {\rm and} \ \ {\deg}(r_2) < {\deg}(b)$$ (2)

  
  
  implies

  $$r_1 - r_2 \ = \ b \, (q_1 - q_2) \ \ {\rm with} \ \ {\deg}(r_1 - r_2) < {\deg}(b)$$ (3)

  
  
  Hence we must have $q_1 - q_2 = 0$ and thus $r_1 - r_2 = 0$ .
• $R = {\bf k}$ is a field with $d(a) = 1$ for $a \in {\bf k}, a \neq 0$ and $d(0) = 0$ . In this case the quotient $q$ and the remainder $r$ of $a$ w.r.t. $b$ are $a/b$ and 0 respectively.
• Let $R$ be the ring of the complex numbers whose real and imaginary parts are integer numbers. Hence

  $$R \ = \ \{ x + {i}y \ \mid \ x, y \in {\mbox{${\mathbb{Z}}$}} \}$$ (4)

  
  
  Consider as a map $d$ from $R$ to ${\mbox{${\mathbb{N}}$}} \ {\cup} \ \{-{\infty}\}$ the norm of an element. Hence $d(x+{i}y) = x^2 + y^2$ with $x, y \in {\mbox{${\mathbb{Z}}$}}$ . It is easy to check that for every $a,b \in R$ with $a, b \neq 0$ we have $d(a \, b) \geq d(a)$ . Indeed for $x,y,z,t \in {\mbox{${\mathbb{Z}}$}}$ we have

  $$\begin{array}{rcl} d((x+{i}y) (z+{i}t)) & = & d({x \ z} -{t \... ...t({z^2}+{t^2}\right) \\ & = & d(x+iy) \, d(z+it) \\ \end{array}$$ (5)

  
  
  Moreover for every $a \neq 0$ we have $d(a) \geq 1$ . Therefore we have proved that $d(a \, b) \geq d(a)$ holds for every $a,b \in R$ with $a, b \neq 0$ . Now given $a,b \in R$ with $b \neq 0$ we are looking for a quotient and a remainder of $a$ w.r.t. $b$ . Hence we are looking for $q$ such that $d(a-b\,q) < d(b)$ . Such a $q$ can be constructed as follows. Let $q'$ be such that $a - q' \, b = 0$ that is $q' = -a/b = -a \overline{b} / d(b)$ where $\overline{b}$ is the conjugate of $b$ . Hence $q'$ writes $x' + {i}y'$ with $x' , y' \in {\mbox{${\mathbb{Q}}$}}$ . Let $x, y \in {\mbox{${\mathbb{Z}}$}}$ be such that $\mid x - x' \mid \leq 1/2$ and $\mid y - y' \mid \leq 1/2$ . Then

  $$\begin{array}{rcl} d(a-b\,q) & = & d(a-b\,q + b \, q' - b \, ... ...' \mid^2 \right) \\ & \leq & d(b) /2 \\ & < & d(b). \end{array}$$ (6)

  
  
  It turns out that several $q$ can be chosen. For instance with $a = 1 + {i}$ and $b = 2 - 2\, {i}$ we have $a - b \, q = -1 - {i}$ with $q = {i}$ and $a - b \, q = 1 + {i}$ with $q = 0$ . In both cases $d(a - b \, q) = 2 < 4 = d(b)$ . Finally this shows that a quotient and a remainder of $a$ w.r.t. $b$ may not be uniquely defined in $R$ .