nLab Euclidean domain

Contents

Context

Arithmetic

Algebra

Contents

Idea

A Euclidean domain is an integral domain which admits a form of the Euclidean quotient-and-remainder algorithm familiar from school mathematics, as well as a form of the extended Euclidean algorithm for calculating the greatest common divisor and Bézout coefficients in a Bézout domain.

Definition

A Euclidean domain is an integral domain AA for which there exists a function d:A{0}d: A \setminus \{0\} \to \mathbb{N} to the natural numbers, often called a degree function, such that given f,gAf, g \in A with g0g \neq 0, there exist q,rAq, r \in A such that f=qg+rf = q \cdot g + r and either r=0r = 0 or d(r)<d(g)d(r) \lt d(g). (One may harmlessly stipulate that d(0)=0d(0) = 0; what to do with the zero element varies from author to author.) There is no uniqueness requirement for q,rq, r.

One could posit, instead of the property that for all fAf \in A and gA{0}g \in A \setminus \{0\}, there exist q,rAq, r \in A such that f=qg+rf = q \cdot g + r and either r=0r = 0 or d(r)<d(g)d(r) \lt d(g); that the integral domain has the structure of a function ()÷():A×A{0}A(-)\div(-):A \times A \setminus \{0\} \to A called the division function, and a function ()%():A×A{0}A(-)\ \%\ (-):A \times A \setminus \{0\} \to A called the remainder function, such that for all fAf \in A and gA{0}g \in A \setminus \{0\}, f=(f÷g)g+(f%g)f = (f \div g) \cdot g + (f\ \%\ g) and either f%g=0f\ \%\ g = 0 or d(f%g)<d(g)d(f\ \%\ g) \lt d(g). There might be multiple such division and remainder functions for the integral domain AA.

Some authors also add the requirement that d(a)d(ab)d(a) \leq d(a b) for all nonzero a,ba, b. There is no loss of generality in assuming it; every Euclidean domain admits such a degree function dd', defining d(a)=min{d(ab):bA,b0}d'(a) = \min \{d(a b): b \in A, b \neq 0\}. We’ll use it freely below, if and when we need to.

In constructive mathematics

In constructive mathematics, there are different types of integral domains, yielding different types of Euclidean domains: the degree function, division, function, and remainder function are no longer valued in A{0}A \setminus \{0\} in one variable, but in {xA|x0}\{x \in A \vert x \neq 0\}, {xA|x#0}\{x \in A \vert x \# 0\}, or some other definition, depending on what the base integral domain ends up being (classical, Heyting, discrete, residue, et cetera).

The definition of the Euclidean domain further bifurcates in constructive mathematics due to the disjunctive condition above. These statements, which are equivalent in the presence of excluded middle, include:

  • (r=0)(d(r)<d(g))(r = 0) \vee (d(r) \lt d(g))
  • ¬((r0)(d(r)d(g)))\not((r \neq 0) \wedge (d(r) \geq d(g)))
  • (d(r)d(g))(r=0)(d(r) \geq d(g)) \to (r = 0)

or equivalently,

  • (f%g=0)(d(f%g)<d(g))(f\ \%\ g = 0) \vee (d(f\ \%\ g) \lt d(g))
  • ¬((f%g0)(d(f%g)d(g))\not((f\ \%\ g \neq 0) \wedge (d(f\ \%\ g) \geq d(g))
  • (d(f%g)d(g))(f%g=0)(d(f\ \%\ g) \geq d(g)) \to (f\ \%\ g = 0)

Examples

  • The (rational) integers \mathbb{Z}.

  • Any field (trivially).

  • The ring of polynomials k[x]k[x] over a discrete field kk, using the ordinary polynomial degree.

  • On the other hand, if kk is a Heyting field which is not a discrete field, not every polynomial in k[x]k[x] apart from zero can be proven to have a well-defined degree, and so is not an Euclidean domain.

  • The real polynomial ring [x]\mathbb{R}[x] is only an Euclidean domain in the presence of the analytic limited principle of omniscience, which states that it has decidable apartness.

  • Any discrete valuation ring: letting π\pi be a generator of the maximal ideal, put d(x)=nd(x) = n where x=uπ nx = u \pi^n, with uu a unit.

  • The Gaussian integers [i]\mathbb{Z}[i], with d(a+bi)=a 2+b 2d(a + b i) = a^2 + b^2 (the norm).

  • The Eisenstein integers? [ω]\mathbb{Z}[\omega], where ω\omega is a primitive cube root of unity, with d(a+bω)=a 2ab+b 2d(a + b \omega) = a^2 - a b + b^2 (the norm).

Properties

Proposition

A Euclidean domain is a Bézout domain.

Proof

Let IAI \subseteq A be a nonzero finitely generated ideal, and suppose d(g)d(g) is the minimum degree taken over all nonzero gIg \in I. For such a gg and any fIf \in I, we may write f=qg+rf = q g + r where either r=0r = 0 or d(r)<d(g)d(r) \lt d(g) (which is impossible since rIr \in I and d(g)d(g) is minimal). So r=0r = 0 it is, and thus I=(g)I = (g).

This proof uses the well-orderedness of \mathbb{N}. It also suggests the practical procedure known as the extended Euclidean algorithm: given two elements a,ba, b in a Euclidean domain AA, this algorithm provides a generator dd of the ideal I=(a)+(b)I = (a) + (b), called a greatest common divisor of a,ba, b, as follows. One constructs a sequence of pairs (a n,b n)(a_n, b_n) of elements of II, with (a 0,b 0)=(a,b)(a_0, b_0) = (a, b), and (a n+1,b n+1)=(b n,r n)(a_{n+1}, b_{n+1}) = (b_n, r_n) where a n=b nq n+r na_n = b_n q_n + r_n for some choice of q n,r nq_n, r_n such that d(r n)<d(b n)d(r_n) \lt d(b_n) and r n0r_n \neq 0. If no such choices for q n,r nq_n, r_n exist, then the sequence terminates at (a n,b n)(a_n, b_n), and b nb_n generates II, i.e, (b n)=I(b_n) = I. Notice that the sequence terminates after finitely many steps since we cannot have an infinite descent of natural numbers

d(r 0)>d(r 1)>,d(r_0) \gt d(r_1) \gt \ldots,

again by well-orderedness of \mathbb{N}.

The proof that this algorithm produces a gcd consists in the observation that at each step we have

(a n+1)+(b n+1)=(a n)+(b n),(a_{n+1}) + (b_{n+1}) = (a_n) + (b_n),

and that from the definition of Euclidean domain, the only reason why the sequence would terminate at (a n,b n)(a_n, b_n) is that a n=b nq n+0a_n = b_n q_n + 0 for some q nq_n, and in that case (a n)+(b n)=(b n)(a_n) + (b_n) = (b_n).

Generalisations

Euclidean domains could be generalised to the case where the structure is only a rig instead of a ring; these objects could be called Euclidean cancellative rigs.

See also

References

See also:

Last revised on December 10, 2022 at 15:38:39. See the history of this page for a list of all contributions to it.