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, bR with a 0 and b 0 we have
d (ab) d (a),
for all a, bR with b 0
there exist q, rR such that
a = bq + randd (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 1Here 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
aR, a 0
and
d (0) = - .
Uniqueness of the quotient and the remainder is easy to show
in that case. Indeed
a = bq_{1} + r_{1} = bq_{2} + r_{2}with deg(r_{1}) < deg(b) and deg(r_{2}) < deg(b)
(2)
implies
r_{1} - r_{2} = b (q_{1} - q_{2}) 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 = 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) = x^{2} + y^{2} with
x, y .
It is easy to check that for every a, bR with
a, b 0
we have
d (ab) d (a).
Indeed for
x, y, z, t we have
Moreover for every a 0 we have
d (a) 1.
Therefore we have proved that
d (ab) d (a) holds
for every a, bR with
a, b 0.
Now given a, bR 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 - bq) < 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 - bq)
=
d (a - bq + bq' - bq')
=
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 - bq = - 1 - i with q = i
and
a - bq = 1 + i with q = 0.
In both cases
d (a - bq) = 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.