Euclidean Domains

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

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

  a  =  bq + r    and    d (r) < d (b). (1)

  
  

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

Example 1   Here are some classical examples.

• R = $\mbox{${\mathbb Z}$}$ mathend000# with d (a) = | a | mathend000# for a $\in$ $\mbox{${\mathbb Z}$}$ mathend000#. Here the quotient q mathend000# and the remainder r mathend000# of a mathend000# w.r.t. b mathend000# (with b $\neq$ 0 mathend000#) can be made unique by requiring r $\geq$ 0 mathend000# (hence we have 0 $\leq$ r < b mathend000#).
• R = $\bf k$[x] mathend000# where $\bf k$ mathend000# is a field with d (a) = deg(a) mathend000# the degree of a mathend000# for a $\in$ R, a $\neq$ 0 mathend000# and d (0) = - $\infty$ mathend000#. 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 mathend000# and thus r₁ - r₂ = 0 mathend000#.
• R = $\bf k$ mathend000# is a field with d (a) = 1 mathend000# for a $\in$ $\bf k$, a $\neq$ 0 mathend000# and d (0) = 0 mathend000#. In this case the quotient q mathend000# and the remainder r mathend000# of a mathend000# w.r.t. b mathend000# are a/b mathend000# and 0 mathend000# respectively.
• Let R mathend000# 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 mathend000# from R mathend000# to $\mbox{${\mathbb N}$}$  $\cup$  { - $\infty$} mathend000# the norm of an element. Hence d (x + iy) = x² + y² mathend000# with x, y $\in$ $\mbox{${\mathbb Z}$}$ mathend000#. It is easy to check that for every a, b $\in$ R mathend000# with a, b $\neq$ 0 mathend000# we have d (a b) $\geq$ d (a) mathend000#. Indeed for x, y, z, t $\in$ $\mbox{${\mathbb Z}$}$ mathend000# 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^2}+{x^2}}\right.$$y2 + x2$$\left.\vphantom{{y^2}+{x^2}}\right)$$$$\left(\vphantom{{z^2}+{t^2}}\right.$$z2 + t2$$\left.\vphantom{{z^2}+{t^2}}\right)$$
  	=	d (x + iy) d (z + it)

  (5)

  
  
  Moreover for every a $\neq$ 0 mathend000# we have d (a) $\geq$ 1 mathend000#. Therefore we have proved that d (a b) $\geq$ d (a) mathend000# holds for every a, b $\in$ R mathend000# with a, b $\neq$ 0 mathend000#. Now given a, b $\in$ R mathend000# with b $\neq$ 0 mathend000# we are looking for a quotient and a remainder of a mathend000# w.r.t. b mathend000#. Hence we are looking for q mathend000# such that d (a - b q) < d (b) mathend000#. Such a q mathend000# can be constructed as follows. Let q' mathend000# be such that a - q' b = 0 mathend000# that is q' = - a/b = - a$\overline{{b}}$/d (b) mathend000# where $\overline{{b}}$ mathend000# is the conjugate of b mathend000#. Hence q' mathend000# writes x' + iy' mathend000# with x', y' $\in$ $\mbox{${\mathbb Q}$}$ mathend000#. Let x, y $\in$ $\mbox{${\mathbb Z}$}$ mathend000# be such that | x - x' | $\leq$ 1/2 mathend000# and | y - y' | $\leq$ 1/2 mathend000#. 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 mathend000# can be chosen. For instance with a = 1 + i mathend000# and b = 2 - 2 i mathend000# we have a - b q = - 1 - i mathend000# with q = i mathend000# and a - b q = 1 + i mathend000# with q = 0 mathend000#. In both cases d (a - b q) = 2 < 4 = d (b) mathend000#. Finally this shows that a quotient and a remainder of a mathend000# w.r.t. b mathend000# may not be uniquely defined in R mathend000#.