Euclidean domain

related topics
{math, number, function}

In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain is a ring that can be endowed with a certain structure – namely a Euclidean function, to be described in detail below – which allows a suitable generalization of the Euclidean algorithm. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them (Bézout identity). Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the Fundamental Theorem of Arithmetic: every Euclidean domain is a unique factorization domain.

It is important to compare the class of Euclidean domains with the larger class of principal ideal domains (PIDs). An arbitrary PID has much the same "structural properties" of a Euclidean domain (or, indeed, even of the ring of integers), but knowing an explicit Euclidean function gives a concreteness which is useful for algorithmic applications. Especially, the fact that the integers and any polynomial ring in one variable over a field are Euclidean domains with respect to easily computable Euclidean functions is of basic importance in computational algebra.

So, given an integral domain R, it is often very useful to know that R has a Euclidean function: in particular, this implies that R is a PID. However, if there is no "obvious" Euclidean function, then determining whether R is a PID is generally a much easier problem than determining whether it is a Euclidean domain.

Euclidean domains appear in the following chain of class inclusions:

Contents

Motivation

Consider the set of integers with the natural operations of + and ⋅. The familiar concept of long division on the integers, relies heavily on the following fact: Given an integer a and a non-zero integer b, there exists integers q and r with a = qb + r, and furthermore, with r = 0 or |r| < |b|. If we only were to have considered positive a and b, this restriction on r and b may be expressed as r = 0, or r < b. Any ring has a notion of addition and multiplication so it is conceivable to think that this notion of long division may be generalized to any ring. However, the requirement on the remainder and the quotient (r = 0 or r < b) cannot be easily defined in the context of rings, unless of course there exists an "ordering" of some sort defined on the ring. This leads to the concept of a Euclidean domain, where, rather than an ordering (which would significantly restrict the rings possible – for example, the complex numbers), the ring is equipped with a "degree function". This degree function, in some sense, can be thought of as a distance from an element of the ring to the additive identity 0 (i.e. a norm). So rather than requiring r = 0 or r < b, we may lift this to r = 0 or d(r) < d(b). The essential idea behind a Euclidean domain is a ring, any element of which (a) and any non-zero element of which (b) have the property that there exists a multiple of b not too far away from a. Of course, if the ring happens to be a division ring (or a field), ab−1 yields a multiple of b (the pre-multiplication of this entity with b), which gives a. So for fields and division rings, there exists a multiple of b which exactly matches with a. Of course, this need not be true in general (this does not hold, even in the context of the integers) so the restriction is relaxed to just "a multiple of b sufficiently close to a". The natural question to ask is what the range of the degree function is defined to be. For many purposes, and in particular for the purpose that the Euclidean algorithm should hold, the range is defined to be the natural numbers. The crucial property of the natural numbers, here, is that they are well-ordered.

Full article ▸

related documents
Harmonic series (mathematics)
Triangle inequality
Monomorphism
Initial and terminal objects
Infinite product
Entailment
Discrete space
Combination
Coset
Torsion subgroup
Inverse element
Principal ideal
Sigma-algebra
Bézout's theorem
Fuzzy set
PSPACE
Homeomorphism
Interior (topology)
List of logarithmic identities
Connected space
Burali-Forti paradox
ElGamal encryption
Möbius inversion formula
Deque
Twin prime
Quaternion group
Congruence relation
Convex hull
Toeplitz matrix
Floor and ceiling functions