Euclidean domains

This article is under construction.

Please do not rely on any information it contains.

This article page is a stub, please help by expanding it.

A given ring $R$ is a Euclidean domain with respect to some function $f:R\to \mathbb {Z} ^{+}\cup \{0\}$ if for any numbers $x,y\in R$, if $x|y$ then $f(x)<f(y)$, and there are always numbers $q,r\in R$ such that $y=qx+r$ with $f(r)<f(x)$. The norm function is often used, so then if $R$ is Euclidean in regards to norm, it is called a norm-Euclidean domain. For example, $\mathbb {Z} [{\sqrt {-2}}]$ is a norm-Euclidean domain, as it is Euclidean with respect to the norm function $N(a+b{\sqrt {-2}})=a^{2}+2b^{2}$. (See A003174 and A048981).

All Euclidean domains are principal ideal domains, but not all principal ideal domains are Euclidean. For example, of the nine imaginary quadratic integer rings that are principal ideal domains, only five are Euclidean: $\mathbb {Z} [i]$, $\mathbb {Z} [{\sqrt {-2}}]$, $\mathbb {Z} [\omega ]$, ${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-7}})}$ and ${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-11}})}$.

The Euclidean algorithm to calculate the GCD of two integers in $\mathbb {Z}$ can be adapted and implemented in any Euclidean domain, and it will always execute correctly. In non-Euclidean domains, there may be cases in which the Euclidean algorithm seems to work but there will also be cases in which it doesn't.

Theorem. $\mathbb {Z}$ is a Euclidean domain in regards to the absolute value function. Given any two integers $m,n\in \mathbb {Z}$, there are always integers $q,r$ such that $n=qm+r$ and $|r|<|m|$.

Proof. (Euclid) [THIS IS JUST A MATTER OF COPYING EUCLID'S PROOF FROM A MODERN TRANSLATION OF THE ELEMENTS]

For quadratic integer rings that are Euclidean, the Euclidean function is often either the norm (in the case of imaginary rings) or the absolute value of the norm (in the case of real rings).

Domain	Euclidean function	Domain	Euclidean function
$\mathbb {Z} [i]$	Norm
$\mathbb {Z} [{\sqrt {-2}}]$		$\mathbb {Z} [{\sqrt {2}}]$	Absolute value of the norm
$\mathbb {Z} [\omega ]$		$\mathbb {Z} [{\sqrt {3}}]$
$\mathbb {Z} [{\sqrt {-5}}]$	N/A, not PID nor UFD	$\mathbb {Z} [\phi ]$
$\mathbb {Z} [{\sqrt {-6}}]$		$\mathbb {Z} [{\sqrt {6}}]$
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-7}})}$	Norm	$\mathbb {Z} [{\sqrt {7}}]$
$\mathbb {Z} [{\sqrt {-10}}]$	N/A, not PID nor UFD	$\mathbb {Z} [{\sqrt {10}}]$	N/A, not PID nor UFD
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-11}})}$	Norm	$\mathbb {Z} [{\sqrt {11}}]$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-13}}]$	N/A, not PID nor UFD	${\mathcal {O}}_{\mathbb {Q} ({\sqrt {13}})}$
$\mathbb {Z} [{\sqrt {-14}}]$		$\mathbb {Z} [{\sqrt {14}}]$	???
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-15}})}$		$\mathbb {Z} [{\sqrt {15}}]$	N/A, not PID nor UFD
$\mathbb {Z} [{\sqrt {-17}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {17}})}$	Absolute value of the norm
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-19}})}$	None, though this is a PID	$\mathbb {Z} [{\sqrt {19}}]$
$\mathbb {Z} [{\sqrt {-21}}]$	N/A, not PID nor UFD	${\mathcal {O}}_{\mathbb {Q} ({\sqrt {21}})}$
$\mathbb {Z} [{\sqrt {-22}}]$		$\mathbb {Z} [{\sqrt {22}}]$	???
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-23}})}$		$\mathbb {Z} [{\sqrt {23}}]$	???
$\mathbb {Z} [{\sqrt {-26}}]$		$\mathbb {Z} [{\sqrt {26}}]$	N/A, not PID nor UFD
$\mathbb {Z} [{\sqrt {-29}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {29}})}$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-30}}]$		$\mathbb {Z} [{\sqrt {30}}]$	N/A, not PID nor UFD
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-31}})}$		$\mathbb {Z} [{\sqrt {31}}]$	???
$\mathbb {Z} [{\sqrt {-33}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {33}})}$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-34}}]$		$\mathbb {Z} [{\sqrt {34}}]$	N/A, not PID nor UFD
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-35}})}$		$\mathbb {Z} [{\sqrt {35}}]$
$\mathbb {Z} [{\sqrt {-37}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {37}})}$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-38}}]$		$\mathbb {Z} [{\sqrt {38}}]$	???
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-39}})}$		$\mathbb {Z} [{\sqrt {39}}]$	N/A, not PID nor UFD
$\mathbb {Z} [{\sqrt {-41}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {41}})}$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-42}}]$		$\mathbb {Z} [{\sqrt {42}}]$	N/A, not PID nor UFD
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-43}})}$	None, though this is a PID	$\mathbb {Z} [{\sqrt {43}}]$	???
$\mathbb {Z} [{\sqrt {-46}}]$	N/A, not PID nor UFD	$\mathbb {Z} [{\sqrt {46}}]$	???
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-47}})}$		$\mathbb {Z} [{\sqrt {47}}]$	???
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-51}})}$		$\mathbb {Z} [{\sqrt {51}}]$	N/A, not PID nor UFD
$\mathbb {Z} [{\sqrt {-53}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {53}})}$	???
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-55}})}$		$\mathbb {Z} [{\sqrt {55}}]$	N/A, not PID nor UFD
$\mathbb {Z} [{\sqrt {-57}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {57}})}$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-58}}]$		$\mathbb {Z} [{\sqrt {58}}]$	N/A, not PID nor UFD
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-59}})}$		$\mathbb {Z} [{\sqrt {59}}]$	???
$\mathbb {Z} [{\sqrt {-61}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {61}})}$	???
$\mathbb {Z} [{\sqrt {-62}}]$		$\mathbb {Z} [{\sqrt {62}}]$	???
$\mathbb {Z} [{\sqrt {-65}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {65}})}$	N/A, not PID nor UFD
$\mathbb {Z} [{\sqrt {-66}}]$		$\mathbb {Z} [{\sqrt {66}}]$
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-67}})}$	None, though this is a PID	$\mathbb {Z} [{\sqrt {67}}]$	???
$\mathbb {Z} [{\sqrt {-69}}]$	N/A, not PID nor UFD	${\mathcal {O}}_{\mathbb {Q} ({\sqrt {69}})}$	Absolute value of the norm but with one special adjustment
$\mathbb {Z} [{\sqrt {-70}}]$		$\mathbb {Z} [{\sqrt {70}}]$	N/A, not PID nor UFD
${\mathcal {O}}_{\mathbb {Q} ({\sqrt {-71}})}$		$\mathbb {Z} [{\sqrt {71}}]$	???
$\mathbb {Z} [{\sqrt {-73}}]$		${\mathcal {O}}_{\mathbb {Q} ({\sqrt {73}})}$	Absolute value of the norm
$\mathbb {Z} [{\sqrt {-74}}]$		$\mathbb {Z} [{\sqrt {74}}]$	N/A, not PID nor UFD