(EF1) If a and b are in R and b is nonzero, then there exist q and r in R such that a = bq + r and either r = 0 or f (r) < f (b).

Any field. Define f (x) = 1 for all nonzero x.

Z, the ring of integers. Define f (n) = |n|, the of n.[3]

absolute value

Z[ i ], the ring of . Define f (a + bi) = a2 + b2, the norm of the Gaussian integer a + bi.

Gaussian integers

Z[ω] (where ω is a (non-real) cube root of unity), the ring of Eisenstein integers. Define f (a + bω) = a2 − ab + b2, the norm of the Eisenstein integer a + bω.

primitive

K[X], the over a field K. For each nonzero polynomial P, define f (P) to be the degree of P.[4]

ring of polynomials

K[[X]], the ring of over the field K. For each nonzero power series P, define f (P) as the order of P, that is the degree of the smallest power of X occurring in P. In particular, for two nonzero power series P and Q, f (P) ≤ f (Q) if and only if P divides Q.

formal power series

Any . Define f (x) to be the highest power of the maximal ideal M containing x. Equivalently, let g be a generator of M, and v be the unique integer such that g v is an associate of x, then define f (x) = v. The previous example K[[X]] is a special case of this.

discrete valuation ring

A with finitely many nonzero prime ideals P1, ..., Pn. Define , where vi is the discrete valuation corresponding to the ideal Pi.[5]

Dedekind domain

Examples of Euclidean domains include:


Examples of domains that are not Euclidean domains include:

R is a (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.[9] 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.

principal ideal domain

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 also holds, and f takes its minimal value exactly at the invertible elements of R.

converse

If Euclidean division is algorithmic, that is, if there is an for computing the quotient and the remainder, then an extended Euclidean algorithm can be defined exactly as in the case of integers.[10]

algorithm

If a Euclidean domain is not a field then it has an element a with the following property: any element x not divisible by a can be written as x = ay + u for some unit u and some element y. This follows by taking a to be a non-unit with f(a) as small as possible. This strange property can be used to show that some principal ideal domains are not Euclidean domains, as not all PIDs have this property. For example, for d = −19, −43, −67, −163, the of is a PID which is not Euclidean, but the cases d = −1, −2, −3, −7, −11 are Euclidean.[11]

ring of integers

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.

Those that are not and therefore not Euclidean, such as the integers of

principal

Those that are principal and not Euclidean, such as the integers of

Those that are Euclidean and not norm-Euclidean, such as the integers of

[16]

Those that are norm-Euclidean, such as (integers of )

Gaussian integers

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


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

Valuation (algebra)

Fraleigh, John B.; Katz, Victor J. (1967). A first course in abstract algebra (5th ed.). Addison-Wesley.  0-201-53467-3.

ISBN

Samuel, Pierre (1971). (PDF). Journal of Algebra. 19 (2): 282–301. doi:10.1016/0021-8693(71)90110-4. Archived from the original (PDF) on 2021-05-06. Retrieved 2021-04-24.

"About Euclidean rings"