Discover

In abstract algebra, a 'Euclidean domain' (also called a 'Euclidean ring') is a type of ring in which the Euclidean algorithm can be used.

Contents

Definition

Examples

Properties

See also

Further reading

Definition

Formally, a Euclidean domain is an integral domain ''D'' on which one can define a function ''v'' mapping nonzero elements of ''D'' to non-negative integers that satisfies the following division-with-remainder property:

★ If ''a'' and ''b'' are in ''D'' and ''b'' is nonzero, then there are ''q'' and ''r'' in ''D'' such that ''a'' = ''bq'' + ''r'' and either ''r'' = 0 or ''v''(''r'') < ''v''(''b'').
The function ''v'' is called a ''valuation'' or ''norm'' or ''gauge'' and the key point here is that the remainder ''r'' has ''v''-size smaller than the ''v''-size of the divisor ''b''. The operation mapping (''a'', ''b'') to (''q'', ''r'') is called the 'Euclidean division', whereas q is called the 'Euclidean quotient'.
Nearly all algebra textbooks which discuss Euclidean domains include the following extra property in the definition: for all nonzero ''a'' and ''b'' in ''D'', ''v''(''ab'') ≥ ''v''(''a''). This property does not have to be assumed since it is not needed to prove the most basic facts about Euclidean domains (see below). However, this inequality can always be arranged to occur by changing the choice of ''v'', as follows: if (''D'',''v'') is a Euclidean domain as given above then the function ''w'' defined on nonzero elements of ''D'' by ''w''(''a'') = least value of ''v''(''ax'') as ''x'' runs over nonzero elements of ''D'' also makes ''D'' a Euclidean domain according to the above definition and it satisfies ''w''(''ab'') ≥ ''w''(''a'') for all nonzero ''a'' and ''b'' in ''D''.

Examples

Examples of Euclidean domains include:

★ 'Z', the ring of integers. Define ''v''(''n'') = |''n''|, the absolute value of ''n''.

★ 'Z'[''i''], the ring of Gaussian integers. Define ''v''(''a''+''bi'') = ''a''²+''b''², the norm of the Gaussian integer ''a''+''bi''.

★ 'Z'[ω] (where ω is a cube root of 1), the ring of Eisenstein integers. Define ''v''(''a''+''b''ω) = ''a''²+''ab''+''b''², the norm of the Eisenstein integer ''a''+''b''ω.

★ ''K''[''X''], the ring of polynomials over a field ''K''. For each nonzero polynomial ''f'', define ''v''(''f'') to be the degree of ''f''.

★ ''K''''X'', the ring of formal power series over the field ''K''. For each nonzero power series ''f'', define ''v''(''f'') as the degree of the smallest power of ''X'' occurring in ''f''.

★ Any discrete valuation ring. Define ''v''(''x'') to be the highest power of the maximal ideal ''M'' containing ''x'' (equivalently, to the power of the generator of the maximal ideal that ''x'' is associated to). The case ''K''''X'' is a special case of the above.

★ Any field. Define ''v''(''x'') = 1 for all nonzero ''x''.
The examples of polynomial and power series rings in one variable are the reason that the function ''v'' in the definition of a Euclidean domain
is not assumed to be defined at 0.

Properties

Every Euclidean domain is a principal ideal domain.
In fact, if ''I'' is a nonzero ideal of a Euclidean domain ''D'' and a nonzero ''a'' in ''I'' is chosen to minimize ''v''(''a'') over all elements of ''I'', then ''I'' = ''aD''. The proof of this does not use the inequality ''v''(''ab'') ≥ ''v''(''a'').
The name Euclidean domain comes from the fact that the extended Euclidean algorithm can be carried out in any Euclidean domain. The proof that this algorithm terminates does not use the inequality ''v''(''ab'') ≥ ''v''(''a'').
In order to prove every nonzero nonunit in a Euclidean domain is a product of irreducibles, the inequality ''v''(''ab'') ≥ ''v''(''a'') is useful for an inductive argument. Or one could instead appeal to the proof of this same result for any principal ideal domain (or Noetherian domain) and once again avoid having to use the inequality ''v''(''ab'') ≥ ''v''(''a'').
Every Euclidean domain is a principal ideal domain and the principal ideals of elements with minimal Euclidean valuation are the entire ring (ie they are the units). Conversely not every PID is Euclidean; for example for ''d'' = -19, -43, -67, -163, the ring of integers of 'Q'($sqrt\{d\}$) is a PID which is 'not' Euclidean, but the cases ''d'' = -1, -2, -3, -7, -11 'are' Euclidean, this was proved by Motzkin. However, in the case of finite extensions of 'Q' with trivial class group, very many have Euclidean integral rings. Under a certain GRE it has been shown by Weinberger that if ''K'' is a finite extension of 'Q' and the ring of integers of ''K'' is a PID with an inifinte number of units, then the ring of integers is Euclidean. In particular this applies to the case of totally real quadratic numberfields with trivial class group. In addition to this it has been proved unconditionally by Harper and Murty that if the field ''K'' has trivial class group and unit rank strictly greater than three, then the ring of integers is Euclidean, an immediate corollary of this is that if the class group is trivial and the extension has degree greater than 8 then the ring of integers is necessarily Euclidean.

See also

★ Ordinal number - these allow a kind of Euclidean division: for all ''α'' and ''β'', if ''β'' > 0, then there are unique ''γ'' and ''δ'' such that ''α'' = ''β'' · ''γ'' + ''δ'' and ''δ'' < ''β''; however, the ordinals are not a Euclidean domain, since they are not even a ring.

Further reading

★ Motzkin "The Euclidean algorithm" Bull. Amer. Math. Soc. 55, (1949) pp. 1142--1146

★ Weinberger "On Euclidean rings of algebraic integers" in "Analytic number theory", Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, MO (1972) published by Amer. Math. Soc. (1973) pp. 321--332

★ Harper and Murty, Canad. J. Math. Vol. 56 (1) (2004) pp. 71--76