You are here
HomeEuclidean valuation
Primary tabs
Euclidean valuation
Let $D$ be an integral domain. A Euclidean valuation is a function from the nonzero elements of $D$ to the nonnegative integers $\nu\colon D\setminus\{0_{D}\}\to\{x\in\mathbb{Z}:x\geq 0\}$ such that the following hold:

For any $a,b\in D$ with $b\neq 0_{D}$, there exist $q,r\in D$ such that $a=bq+r$ with $\nu(r)<\nu(b)$ or $r=0_{D}$.

For any $a,b\in D\setminus\{0_{D}\}$, we have $\nu(a)\leq\nu(ab)$.
Euclidean valuations are important because they let us define greatest common divisors and use Euclid’s algorithm. Some facts about Euclidean valuations include:
These facts can be proven as follows:

If $a\in D\setminus\{0_{D}\}$, then
$\nu(1_{D})\leq\nu(1_{D}\cdot a)=\nu(a).$ 
If $u\in D$ is a unit, then let $v\in D$ be its inverse. Thus,
$\nu(1_{D})\leq\nu(u)\leq\nu(uv)=\nu(1_{D}).$ Conversely, if $\nu(u)=\nu(1_{D})$, then there exist $q,r\in D$ with $\nu(r)<\nu(u)=\nu(1_{D})$ or $r=0_{D}$ such that
$1_{D}=qu+r.$ Since $\nu(r)<\nu(1_{D})$ is impossible, we must have $r=0_{D}$. Hence, $q$ is the inverse of $u$.

Let $v\in D$ be the inverse of $u$. Then
$\nu(a)\leq\nu(au)\leq\nu(auv)=\nu(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 $\nu(a)=0$ for all $a\in F\setminus\{0_{F}\}$.

$\mathbb{Z}$ is a Euclidean domain with absolute value 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 $a_{0},\dots,a_{n}\in F$ with $a_{n}\neq 0_{F}$, then
$\nu\left(\sum_{{j=0}}^{n}a_{j}x^{j}\right)=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 A First Course in Abstract Algebra.
Mathematics Subject Classification
13F07 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections