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    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) = | a | 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₁ + r₁  =  b q₂ + r₂  with  deg(r₁) < deg(b)  and  deg(r₂) < deg(b) (2)

  
  
  implies

  r₁ - r₂  =  b (q₁ - q₂)  with  deg(r₁ - r₂) < deg(b) (3)

  
  
  Hence we must have q₁ - q₂ = 0 and thus r₁ - r₂ = 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

  $$\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 + iy) = x² + y² 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

  d ((x + iy)(z + it))	=	d (x z - t y + $$\left(\vphantom{ {y \ z}+{t \ x} }\right.$$y z + t x$$\left.\vphantom{ {y \ z}+{t \ x} }\right)$$ i)
  	=	(x z - t y)2 + (y z + t x)2
  	=	x2 z2 + t2 y2 - 2x z t y + y2 z2 + t2 x2 + 2x z t y
  	=	x2 (z2 + t2) + y2 (z2 + t2)
  	=	$$\left(\vphantom{{y \sp 2}+{x \sp 2}}\right.$$y$$\sp$$2 + x$$\sp$$2$$\left.\vphantom{{y \sp 2}+{x \sp 2}}\right)$$$$\left(\vphantom{{z \sp 2}+{t \sp 2}}\right.$$z$$\sp$$2 + t$$\sp$$2$$\left.\vphantom{{z \sp 2}+{t \sp 2}}\right)$$
  	=	d (x + iy) d (z + it)

  (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' + iy' with x', y' $\in$ $\mbox{${\mathbb Q}$}$. Let x, y $\in$ $\mbox{${\mathbb Z}$}$ be such that | x - x' | $\leq$ 1/2 and | y - y' | $\leq$ 1/2. Then

  d (a - b q)	=	d (a - b q + b q' - b q')
  	=	d (b(q - q'))
  	=	d (b)$$\left(\vphantom{ \mid x - x' \mid^2 + \mid y - y' \mid^2 }\right.$$ | x - x'$$\mid^{2}_{}$$ + | y - y'$$\mid^{2}_{}$$$$\left.\vphantom{ \mid x - x' \mid^2 + \mid y - y' \mid^2 }\right)$$
  	$$\leq$$	d (b)/2
  	<	d (b).

  (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.