In mathematics, more specifically in ring theory, a Euclidean domain (also called a Euclidean ring) is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. 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's 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 when an explicit algorithm for Euclidean division is known, one may use the Euclidean algorithm and extended Euclidean algorithm to compute greatest common divisors and Bézout's identity. In particular, the existence of efficient algorithms for Euclidean division of integers and of polynomials in one variable over a field is of basic importance in computer 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:

rngsringscommutative ringsintegral domainsintegrally closed domainsGCD domainsunique factorization domainsprincipal ideal domainsEuclidean domainsfieldsalgebraically closed fields


Let R be an integral domain. A Euclidean function on R is a function f from R \ {0} to the non-negative integers satisfying the following fundamental division-with-remainder property:

A Euclidean domain is an integral domain which can be endowed with at least one Euclidean function. A particular Euclidean function f 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, q and r are called respectively a quotient and a remainder of the division (or Euclidean division) of a by b. 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:

However, one can show that (EF1) alone suffices to define a Euclidean domain; if an integral domain R is endowed with a function g satisfying (EF1), then R can also be endowed with a function satisfying both (EF1) and (EF2) simultaneously. Indeed, for a in R \ {0} , one can define f (a) as follows:[1]

In words, one may define f (a) to be the minimum value attained by g on the set of all non-zero elements of the principal ideal generated by a.

A Euclidean function f is multiplicative if f (ab) = f (a) f (b) and f (a) is never zero. It follows that f (1) = 1. More generally, f (a) = 1 if and only if a 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".[2] Some authors also require the domain of the Euclidean function to be the entire ring R;[2] however, this does not essentially affect the definition, since (EF1) does not involve the value of f (0). 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 I of R with nonzero generator b, all nonzero classes of the quotient ring R/I have a representative r with f (r) < f (b). Since the possible values of f are well-ordered, this property can be established by showing that f (r) < f (b) for any rI with minimal value of f (r) in its class. Note that, for a Euclidean function that is so established, there need not exist an effective method to determine q and r in (EF1).


Examples of Euclidean domains include:

Examples of domains that are not Euclidean domains include:


Let R be a domain and f a Euclidean function on R. Then:

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.[12] 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.[13] 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.[14][15] 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:

The norm-Euclidean quadratic fields have been fully classified; they are where takes the values

−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73 (sequence A048981 in the OEIS).[17]

Every Euclidean imaginary quadratic field is norm-Euclidean and is one of the five first fields in the preceding list.

See also


  1. ^ Rogers, Kenneth (1971), "The Axioms for Euclidean Domains", American Mathematical Monthly, 78 (10): 1127–8, doi:10.2307/2316324, JSTOR 2316324, Zbl 0227.13007
  2. ^ a b Dummit, David S.; Foote, Richard M. (2004). Abstract Algebra. Wiley. p. 270. ISBN 9780471433347.
  3. ^ Fraleigh & Katz 1967, p. 377, Example 1
  4. ^ Fraleigh & Katz 1967, p. 377, Example 2
  5. ^ Samuel, Pierre (1 October 1971). "About Euclidean rings". Journal of Algebra. 19 (2): 282–301 (p. 285). doi:10.1016/0021-8693(71)90110-4. ISSN 0021-8693.
  6. ^ Motzkin, Th (December 1949). "The Euclidean algorithm". Bulletin of the American Mathematical Society. 55 (12): 1142–1146. ISSN 0002-9904.
  7. ^ Pierre, Samuel (1964). Lectures on Unique Factorization Domains (PDF). Tata Institute of Fundamental Research. pp. 27–28.
  8. ^ "Quotient of polynomials, PID but not Euclidean domain?".
  9. ^ Fraleigh & Katz 1967, p. 377, Theorem 7.4
  10. ^ Fraleigh & Katz 1967, p. 380, Theorem 7.7
  11. ^ Motzkin, Theodore (1949), "The Euclidean algorithm", Bulletin of the American Mathematical Society, 55 (12): 1142–6, doi:10.1090/S0002-9904-1949-09344-8, Zbl 0035.30302
  12. ^ Weinberger, Peter J. (1973), "On Euclidean rings of algebraic integers", Proceedings of Symposia in Pure Mathematics, 24, AMS: 321–332, doi:10.1090/pspum/024/0337902, ISBN 9780821814246
  13. ^ Harper, Malcolm; Murty, M. Ram (2004), "Euclidean rings of algebraic integers" (PDF), Canadian Journal of Mathematics, 56 (1): 71–76, CiteSeerX, doi:10.4153/CJM-2004-004-5
  14. ^ Ribenboim, Paulo (1972). Algebraic Numbers. Wiley-Interscience. ISBN 978-0-471-71804-8.
  15. ^ Hardy, G.H.; Wright, E.M.; Silverman, Joseph; Wiles, Andrew (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 978-0-19-921986-5.
  16. ^ Clark, David A. (1994). "A quadratic field which is Euclidean but not norm-Euclidean". Manuscripta Mathematica. 83 (3–4): 327–330. CiteSeerX doi:10.1007/BF02567617. Zbl 0817.11047.
  17. ^ LeVeque, William J. (2002) [1956]. Topics in Number Theory. Vol. I and II. Dover. pp. II:57, 81. ISBN 978-0-486-42539-9. Zbl 1009.11001.