Euclidean valuation


Let D be an integral domain. A Euclidean valuation is a function from the nonzero elements of D to the nonnegative integers ν:D{0D}{x:x0} such that the following hold:

  • For any a,bD with b0D, there exist q,rD such that a=bq+r with ν(r)<ν(b) or r=0D.

  • For any a,bD{0D}, we have ν(a)ν(ab).

Euclidean valuations are important because they let us define greatest common divisorsMathworldPlanetmathPlanetmath and use Euclid’s algorithm. Some facts about Euclidean valuations include:

  • The minimal (http://planetmath.org/MinimalElement) value of ν is ν(1D). That is, ν(1D)ν(a) for any aD{0D}.

  • uD is a unit if and only if ν(u)=ν(1D).

  • For any aD{0D} and any unit u of D, we have ν(a)=ν(au).

These facts can be proven as follows:

  • If aD{0D}, then

    ν(1D)ν(1Da)=ν(a).
  • If uD is a unit, then let vD be its inversePlanetmathPlanetmath (http://planetmath.org/MultiplicativeInverse). Thus,

    ν(1D)ν(u)ν(uv)=ν(1D).

    Conversely, if ν(u)=ν(1D), then there exist q,rD with ν(r)<ν(u)=ν(1D) or r=0D such that

    1D=qu+r.

    Since ν(r)<ν(1D) is impossible, we must have r=0D. Hence, q is the inverse of u.

  • Let vD be the inverse of u. Then

    ν(a)ν(au)ν(auv)=ν(a).

Note that an integral domain is a Euclidean domain if and only if it has a Euclidean valuation.

Below are some examples of Euclidean domains and their Euclidean valuations:

  • Any field F is a Euclidean domain under the Euclidean valuation ν(a)=0 for all aF{0F}.

  • is a Euclidean domain with absolute valueMathworldPlanetmathPlanetmathPlanetmath acting as its Euclidean valuation.

  • If F is a field, then F[x], the ring of polynomials over F, is a Euclidean domain with degree acting as its Euclidean valuation: If n is a nonnegative integer and a0,,anF with an0F, then

    ν(j=0najxj)=n.

Due to the fact that the ring of polynomials over any field is always a Euclidean domain with degree acting as its Euclidean valuation, some refer to a Euclidean valuation as a degree function. This is done, for example, in Joseph J. Rotman’s .

Title Euclidean valuation
Canonical name EuclideanValuation
Date of creation 2013-03-22 12:40:45
Last modified on 2013-03-22 12:40:45
Owner Wkbj79 (1863)
Last modified by Wkbj79 (1863)
Numerical id 15
Author Wkbj79 (1863)
Entry type Definition
Classification msc 13F07
Synonym degree function
Related topic PID
Related topic UFD
Related topic Ring
Related topic IntegralDomain
Related topic EuclideanRing
Related topic ProofThatAnEuclideanDomainIsAPID
Related topic DedekindHasseValuation
Related topic EuclideanNumberField