# norm-Euclidean number field

Definition.  An algebraic number field $K$ is a norm-Euclidean number field, if for every pair  $(\alpha,\,\beta)$  of the integers (http://planetmath.org/AlgebraicInteger) of $K$, where  $\beta\neq 0$,  there exist $\varkappa$ and $\varrho$ of the field such that

 $\alpha\;=\;\varkappa\beta+\varrho,\quad|\mbox{N}(\varrho)|<|\mbox{N}(\beta)|.$

Here N means the norm function in $K$.

Theorem 1.  A field $K$ is norm-Euclidean if and only if each number $\gamma$ of $K$ is in the form

 $\displaystyle\gamma\;=\;\varkappa+\delta$ (1)

where $\varkappa$ is an of the field and  $|\mbox{N}(\delta)|<1.$

Proof.  First assume the condition (1).  Let $\alpha$ and $\beta$ be integers of $K$,  $\beta\neq 0$.  Then there are the numbers  $\varkappa,\,\delta\in K$  such that $\varkappa$ is integer and

 $\frac{\alpha}{\beta}\;=\;\varkappa+\delta,\quad|\mbox{N}(\delta)|\;<\;1.$

Thus we have

 $\alpha\;=\;\varkappa\beta+\beta\delta\;=\;\varkappa\beta+\varrho.$

Here  $\varrho=\beta\delta$  is integer, since $\alpha$ and $\varkappa\beta$ are integers.  We also have

 $|\mbox{N}(\varrho)|\;=\;|\mbox{N}(\beta)|\cdot|\mbox{N}(\delta)|\;<\;|\mbox{N}% (\beta)|\cdot 1\;=\;|\mbox{N}(\beta)|.$

Accordingly, $K$ is a norm-Euclidean number field. Secondly assume that $K$ is norm-Euclidean.  Let $\gamma$ be an arbitrary element of the field.  We can determine (http://planetmath.org/MultiplesOfAnAlgebraicNumber) a rational integer $m\,(\neq 0)$ such that $m\gamma$ is an algebraic integer  of $K$.  The assumption  guarantees the integers $\varkappa$, $\varrho$ of $K$ such that

 $m\gamma\;=\;\varkappa m+\varrho,\quad\mbox{N}(\varrho)\;<\;\mbox{N}(m).$

Thus

 $\gamma=\frac{m\gamma}{m}=\varkappa+\frac{\varrho}{m},\quad\left|\mbox{N}\left(% \frac{\varrho}{m}\right)\right|=\frac{|\mbox{N}(\varrho)|}{|\mbox{N}(m)|}<1,$

Q.E.D.

Proof.  We recall that the greatest common divisor of two elements of a commutative ring means such a common divisor   of the elements that it is divisible by each common divisor of the elements.  Let now $\varrho_{0}$ and $\varrho_{1}$ be two algebraic integers of a norm-Euclidean number field $K$.  According the definition there are the integers $\varkappa_{i}$ and $\varrho_{i}$ of $K$ such that

 $\begin{cases}\varrho_{0}=\varkappa_{2}\varrho_{1}+\varrho_{2},\quad|\mbox{N}(% \varrho_{2})|<|\mbox{N}(\varrho_{1})|\\ \varrho_{1}=\varkappa_{3}\varrho_{2}+\varrho_{3},\quad|\mbox{N}(\varrho_{3})|<% |\mbox{N}(\varrho_{2})|\\ \varrho_{2}=\varkappa_{4}\varrho_{3}+\varrho_{4},\quad|\mbox{N}(\varrho_{4})|<% |\mbox{N}(\varrho_{3})|\\ \qquad\cdots\cdots\\ \varrho_{n-2}=\varkappa_{n}\varrho_{n-1}+\varrho_{n},\;\;|\mbox{N}(\varrho_{n}% )|<|\mbox{N}(\varrho_{n-1})|\\ \varrho_{n-1}=\varkappa_{n+1}\varrho_{n}+0,\end{cases}$

The ends to the remainder 0, because the numbers $|\mbox{N}(\varrho_{i})|$ form a descending sequence  of non-negative rational integers — see the entry norm and trace of algebraic number.  As in the Euclid’s algorithm in $\mathbb{Z}$, one sees that the last divisor $\varrho_{n}$ is one greatest common divisor of $\varrho_{0}$ and $\varrho_{1}$.  N.B. that $\varrho_{0}$ and $\varrho_{1}$ may have an infinite  amount of their greatest common divisors, depending the amount of the units in $K$.

Theorem 3.  The only norm-Euclidean quadratic fields $\mathbb{Q}(\sqrt{d})$ are those with

 $d\in\{-11,\,-7,\,-3,\,-2,\,-1,\,2,\,3,\,5,\,6,\,7,\,11,\,13,\,17,\,19,\,21,\,2% 9,\,33,\,37,\,41,\,57,\,73\}.$
 Title norm-Euclidean number field Canonical name NormEuclideanNumberField Date of creation 2013-03-22 16:52:26 Last modified on 2013-03-22 16:52:26 Owner pahio (2872) Last modified by pahio (2872) Numerical id 17 Author pahio (2872) Entry type Topic Classification msc 13F07 Classification msc 11R21 Classification msc 11R04 Related topic EuclideanValuation Related topic QuadraticImaginaryEuclideanNumberFields Related topic ListOfAllImaginaryQuadraticPIDs Related topic EuclideanField Related topic AlgebraicNumberTheory Related topic MixedFraction Defines norm-Euclidean