Euclidean domain

Let be an integral domain. A Euclidean function on is a function from {{math|R \ {0} }}to the non-negative integers satisfying the following fundamental division-with-remainder property: • (EF1) If and are in and is nonzero, then there exist and in such that and either or . A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. A particular Euclidean function is not part of the definition of a Euclidean domain, as, in general, a Euclidean domain may admit many different Euclidean functions. In this context, and are called respectively a quotient and a remainder of the division (or Euclidean division) of by . In contrast with the case of integers and polynomials, the quotient is generally not uniquely defined, but when a quotient has been chosen, the remainder is uniquely defined. Most algebra texts require a Euclidean function to have the following additional property: • (EF2) For all nonzero and in , . However, one can show that (EF1) alone suffices to define a Euclidean domain; if an integral domain is endowed with a function satisfying (EF1), then can also be endowed with a function satisfying both (EF1) and (EF2) simultaneously. Indeed, for in {{math|R \ {0} }}, one can define as follows: :f(a) = \min_{x \in R \setminus \{0\}} g(xa) In words, one may define to be the minimum value attained by on the set of all non-zero elements of the principal ideal generated by . A Euclidean function is multiplicative if and is never zero. It follows that . More generally, if and only if is a unit. Notes on the definition Many authors use other terms in place of "Euclidean function", such as "degree function", "valuation function", "gauge function" or "norm function". Some authors also require the domain of the Euclidean function to be the entire ring ; however, this does not essentially affect the definition, since (EF1) does not involve the value of . The definition is sometimes generalized by allowing the Euclidean function to take its values in any well-ordered set; this weakening does not affect the most important implications of the Euclidean property. The property (EF1) can be restated as follows: for any principal ideal of with nonzero generator , all nonzero classes of the quotient ring have a representative with . Since the possible values of are well-ordered, this property can be established by showing that for any with minimal value of in its class. Note that, for a Euclidean function that is so established, there need not exist an effective method to determine and in (EF1). ==Examples==

Examples of Euclidean domains include: • Any field. Define for all nonzero . • , the ring of integers. Define , the absolute value of . • , the ring of Gaussian integers. Define , the norm of the Gaussian integer . • (where {{tmath|1=\omega=\tfrac{-1\pm \sqrt{-3} }{2} }} is a primitive cube root of unity), the ring of Eisenstein integers. Define , the norm of the Eisenstein integer . • , the ring of golden integers, where {{tmath|1=\varphi=\tfrac{1+\sqrt 5}{2} }} is the golden ratio. Define , the absolute value of the field norm of . • , the ring of polynomials over a field . For each nonzero polynomial , define to be the degree of . • , the ring of formal power series over the field . For each nonzero power series , define as the order of , that is the degree of the smallest power of occurring in . In particular, for two nonzero power series and , if and only if divides . • Any discrete valuation ring. Define to be the highest power of the maximal ideal containing . Equivalently, let be a generator of , and be the unique integer such that is an associate of , then define . The previous example is a special case of this. • A Dedekind domain with finitely many nonzero prime ideals . Define f(x) = \sum_{i=1}^n v_i(x), where is the discrete valuation corresponding to the ideal . Examples of domains that are not Euclidean domains include: • Every domain that is not a principal ideal domain, such as the ring of polynomials in at least two indeterminates over a field, or the ring of univariate polynomials with integer coefficients, or the number ring . • The ring of integers of , consisting of the numbers where and are integers and both even or both odd. It is a principal ideal domain that is not Euclidean. This was proved by Theodore Motzkin and was the first case known. • The ring is also a principal ideal domain that is not Euclidean. To see that it is not a Euclidean domain, it suffices to show that for every non-zero prime p\in A, the map A^\times\to(A/p)^\times induced by the quotient map A\to A/p is not surjective. ==Properties==

Let R be a domain and f a Euclidean function on R. Then: • R is a principal ideal domain (PID). In fact, if I is a nonzero ideal of R then any element a of I \ {0} with minimal value (on that set) of f(a) is a generator of I. As a consequence R is also a unique factorization domain and a Noetherian ring. With respect to general principal ideal domains, the existence of factorizations (i.e., that R is an atomic domain) is particularly easy to prove in Euclidean domains: choosing a Euclidean function f satisfying (EF2), x cannot have any decomposition into more than f(x) nonunit factors, so starting with x and repeatedly decomposing reducible factors is bound to produce a factorization into irreducible elements. • Any element of R at which f takes its globally minimal value is invertible in R. If an f satisfying (EF2) is chosen, then the converse also holds, and f takes its minimal value exactly at the invertible elements of R. • If Euclidean division is algorithmic, that is, if there is an algorithm for computing the quotient and the remainder, then an extended Euclidean algorithm can be defined exactly as in the case of integers. • If a Euclidean domain is not a field then it has a non-unit element a called a universal side divisor{{Citation | last = Motzkin | first = Theodore | author-link = Theodore Motzkin | title = The Euclidean algorithm | journal = Bulletin of the American Mathematical Society | volume = 55 | issue = 12 | pages = 1142–6 | year = 1949 | url = http://projecteuclid.org/handle/euclid.bams/1183514381 | doi = 10.1090/S0002-9904-1949-09344-8 | zbl=0035.30302 However, in many finite extensions of Q with trivial class group, the ring of integers is Euclidean (not necessarily with respect to the absolute value of the field norm; see below). Assuming the extended Riemann hypothesis, if K is a finite extension of Q and the ring of integers of K is a PID with an infinite number of units, then the ring of integers is Euclidean.{{cite conference | last = Weinberger | first = Peter J. | author-link = Peter J. Weinberger | title = On Euclidean rings of algebraic integers | book-title=Analytic Number Theory | publisher = American Mathematical Society |location=Providence, Rhode Island In particular this applies to the case of totally real quadratic number fields with trivial class group. In addition (and without assuming ERH), if the field K is a Galois extension of Q, has trivial class group and unit rank strictly greater than three, then the ring of integers is Euclidean.{{Citation | last1 = Harper | first1 = Malcolm | last2 = Murty | first2 = M. Ram | author2-link = M. Ram Murty | title = Euclidean rings of algebraic integers | journal = Canadian Journal of Mathematics | volume = 56 | issue = 1 | pages = 71–76 | year = 2004 | url = http://www.mast.queensu.ca/~murty/harper-murty.pdf | doi = 10.4153/CJM-2004-004-5 An immediate corollary of this is that if the number field is Galois over Q, its class group is trivial and the extension has degree greater than 8 then the ring of integers is necessarily Euclidean. == Norm-Euclidean fields ==

Algebraic number fields K come with a canonical norm function on them: the absolute value of the field norm N that takes an algebraic element α to the product of all the conjugates of α. This norm maps the ring of integers of a number field K, say OK, to the nonnegative rational integers, so it is a candidate to be a Euclidean norm on this ring. If this norm satisfies the axioms of a Euclidean function then the number field K is called norm-Euclidean or simply Euclidean. Strictly speaking it is the ring of integers that is Euclidean since fields are trivially Euclidean domains, but the terminology is standard. If a field is not norm-Euclidean then that does not mean the ring of integers is not Euclidean, just that the field norm does not satisfy the axioms of a Euclidean function. In fact, the rings of integers of number fields may be divided in several classes: • Those that are not principal and therefore not Euclidean, such as the integers of \mathbf{Q}(\sqrt{-5}\,) • Those that are principal and not Euclidean, such as the integers of \mathbf{Q}(\sqrt{-19}\,) • Those that are Euclidean and not norm-Euclidean, such as the integers of \mathbf{Q}(\sqrt{69}\,) • Those that are norm-Euclidean, such as Gaussian integers (integers of \mathbf{Q}(\sqrt{-1}\,)) The norm-Euclidean quadratic fields have been fully classified; they are \mathbf{Q}(\sqrt{d}\,) where d takes the values :−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 . Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.