Definition:Euclidean Domain

From ProofWiki
Jump to: navigation, search


Let $\struct {R, +, \circ}$ be an integral domain with zero $0_R$.

Let $\nu: R \setminus \set {0_R} \to \N$ be a mapping such that:

$(1): \quad$ For any $a, b \in R, b \ne 0_R$, there exist $q, r \in R$ with $\map \nu r < \map \nu b$, or $r = 0_R$ such that:
$a = q \circ b + r$
$(2): \quad$ For any $a, b \in R, b \ne 0_R$:
$\map \nu a \le \map \nu {a \circ b}$

Then $\nu$ is called a Euclidean valuation or Euclidean function and $R$ is called a Euclidean ring or Euclidean domain.


Integers are Euclidean Domain

The integers $\Z$ with the mapping $\nu: \Z \to \Z$ defined as:

$\forall x \in \Z: \map \nu x = \size x$

form a Euclidean domain.

Polynomial Forms over Field is Euclidean Domain

Let $\struct {F, +, \circ}$ be a field whose zero is $0_F$ and whose unity is $1_F$.

Let $X$ be transcendental in $F$.

Let $F \sqbrk X$ be the ring of polynomial forms in $X$ over $F$.

Then $F \sqbrk X$ is a Euclidean domain.

Gaussian Integers form Euclidean Domain

Let $\struct {\Z \sqbrk i, +, \times}$ be the integral domain of Gaussian Integers.

Let $\nu: \Z \sqbrk i \to \R$ be the real-valued function defined as:

$\forall a \in \Z \sqbrk i: \map \nu a = \cmod a^2$

where $\cmod a$ is the (complex) modulus of $a$.

Then $\nu$ is a Euclidean valuation on $\Z \sqbrk i$.

Hence $\struct {\Z \sqbrk i, +, \times}$ with $\nu: \Z \sqbrk i \to \Z$ forms a Euclidean domain.

Examples of Use of Euclidean Algorithm

GCD of $5 i$ and $3 + i$ in Ring of Gaussian Integers

The GCD of $5 i$ and $3 + 1$ in the ring of Gaussian integers is found to be:

$\gcd \set {5 i, 3 + 1} = 1 + 2 i$

and its associates $-1 - 2 i$, $-2 + i$ and $2 - i$.

Also see

  • Results about Euclidean domains can be found here.

Source of Name

This entry was named for Euclid.

Historical Note

A Euclidean domain is so named because, as an algebraic structure, it sustains the concept of the Euclidean Algorithm.

Euclid himself made no mention of the concept, which is an abstract algebraic concept defined in (mathematically speaking) modern times.

Linguistic Note

The term Euclidean domain is introduced with the indefinite article: a Euclidean domain.

This is because Euclid is pronounced Yoo-klid in English.