Next: The Euclidean Algorithm Up: The Euclidean Algorithm Previous: The Euclidean Algorithm

## Euclidean Domains

Definition 1   An integral domain R endowed with a function d : R    { - } is an Euclidean domain if the following two conditions hold
• for all a, b R with a 0 and b 0 we have d (a b) d (a),
• for all a, b R with b 0 there exist q, r 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 = with d (a) = | a | for a . Here the quotient q and the remainder r of a w.r.t. b (with b 0) can be made unique by requiring r 0 (hence we have 0 r < b).
• R = [x] where is a field with d (a) = deg(a) the degree of a for a R, a 0 and d (0) = - . Uniqueness of the quotient and the remainder is easy to show in that case. Indeed

 a  =  b q1 + r1  =  b q2 + r2  with  deg(r1) < deg(b)  and  deg(r2) < deg(b) (2)

implies

 r1 - r2  =  b (q1 - q2)  with  deg(r1 - r2) < deg(b) (3)

Hence we must have q1 - q2 = 0 and thus r1 - r2 = 0.
• R = is a field with d (a) = 1 for a , a 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 + iy  |  x, y } (4)

Consider as a map d from R to    { - } the norm of an element. Hence d (x + iy) = x2 + y2 with x, y . It is easy to check that for every a, b R with a, b 0 we have d (a b) d (a). Indeed for x, y, z, t we have

 d ((x + iy)(z + it)) = d (x z - t y + y z + t x 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) = y2 + x2z2 + t2 = d (x + iy) d (z + it)
(5)

Moreover for every a 0 we have d (a) 1. Therefore we have proved that d (a b) d (a) holds for every a, b R with a, b 0. Now given a, b R with b 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/d (b) where is the conjugate of b. Hence q' writes x' + iy' with x', y' . Let x, y be such that | x - x' | 1/2 and | y - y' | 1/2. Then

 d (a - b q) = d (a - b q + b q' - b q') = d (b(q - q')) = d (b) | x - x' + | y - y' 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.

Next: The Euclidean Algorithm Up: The Euclidean Algorithm Previous: The Euclidean Algorithm
Marc Moreno Maza
2004-04-27