Euclidean domain

A Euclidean domain admits division with remainder measured by a decreasing Euclidean function.

For a field $F$, polynomial division makes the one-variable polynomial ring $F[X]$ a Euclidean domain with Euclidean function equal to the polynomial degree. For a divisor $g\ne 0$, subtract a suitable scalar multiple of $X^{\mathrm{deg}f-\mathrm{deg}g}g$ to cancel the leading coefficient of the current remainder. Its degree strictly decreases. Iteration terminates at $f=qg+r$, where $r=0$ or $\mathrm{deg}r<\mathrm{deg}g$. Division by the leading coefficient is valid because it is nonzero in a field.

Let $R$ be a Euclidean domain with Euclidean function $\nu$, and let $I$ be a nonzero ideal. Choose $b\in I\setminus \{0\}$ minimizing the nonnegative integer $\nu (b)$. For $a\in I$, divide $a=qb+r$ with $r=0$ or $\nu (r)<\nu (b)$. Since $r=a-qb\in I$, the latter case contradicts minimality. Hence every $a$ is a multiple of $b$, giving $I=(b)$. The zero ideal is $(0)$, so every ideal is a principal ideal and $R$ is a principal ideal domain.

The ring of integers $\mathbb{Z}[(1+\sqrt{-7})/2]$ is a Euclidean domain for $N(z)=z\overline{z}$. In its lattice choose the nearest row, whose imaginary-coordinate error is at most $\sqrt{7}/4$, then the nearest point on that row, whose real-coordinate error is at most $1/2$. Every complex number is thus within squared distance $11/16<1$ of a lattice point, giving Euclidean division. The suborder $\mathbb{Z}[\sqrt{-7}]$ has the nonprincipal ideal $(2,1+\sqrt{-7})$ and consequently is not a Euclidean domain for any Euclidean function.

A Euclidean function on an integral domain $R$ assigns a nonnegative integer to every nonzero element so that, for $a,b\in R$ with $b\ne 0$, there are $q,r\in R$ satisfying $a=bq+r$ and either $r=0$ or $d(r)<d(b)$.

A Gaussian integer has the form $a+bi$ with $a,b\in \mathbb{Z}$. Its multiplicative norm is $N(a+bi)=a^2+b^2$, which makes $\mathbb{Z}[i]$ a Euclidean domain.

The product of a Gaussian integer with its complex conjugate. It is multiplicative: $N(zw)=N(z)N(w)$, which gives the Brahmagupta-Fibonacci identity.

An odd Gaussian integer is primary when it satisfies the displayed congruence. The four units have distinct images in $(\mathbb{Z}[i]/(1+i{)}^3{)}^{\times }$, a group of order four; hence every odd ideal has a unique primary generator. Indeed $v_{1+i}(-2)=2$ and $v_{1+i}(i-1)=v_{1+i}(-i-1)=1$.

If $\alpha =a+bi$ is a Gaussian integer and $P$ is a nonzero prime ideal of $R=\mathbb{Z}[\alpha ]$, then $R/P$ is a finite field. Complex conjugation preserves $R$, so a nonzero $\beta \in P$ gives the positive integer $\beta \bar{\beta }\in P$. Primality supplies a rational prime $p\in P$. Since $\alpha$ satisfies the monic polynomial $t^2-2at+a^2+b^2$, the ring $R/P$ is a quotient of ${\mathbb{F}}_p[t]/(\bar{F})$ and has at most $p^2$ elements. It is a finite integral domain, hence a field. The proof does not require $R$ to be a principal ideal domain.

For a primitive cube root of unity $\omega$, the Eisenstein integers form the triangular latticeTheir multiplicative norm is $N(a+b\omega )=a^2-ab+b^2$.

For an Eisenstein integer $z=a+b\omega$, with $\omega =(-1+i\sqrt{3})/2$, the norm is $N(z)=z\overline{z}=a^2-ab+b^2$. It is a positive integer for $z\ne 0$, since $N(z)=(a-b/2{)}^2+3b^2/4$, and is multiplicative by the multiplicativity of the complex modulus. An element is a unit exactly when its norm is one: one direction follows from multiplicativity and integrality, and the other from the inverse $z^{-1}=\overline{z}$.

Let $p\ge 3$ be a prime number dividing $n^2+3$, and set $\omega =(-1+i\sqrt{3})/2$. The case $p=3$ is $N(1-\omega )=3$. For $p>3$, useThe Eisenstein integer $p$ divides this product, but divides neither factor: divisibility by the rational integer $p$ in the basis $1,\omega$ requires both integer coefficients to be divisible by $p$, whereas the second coefficients are $2$ and $-2$. Thus $p$ is not a prime element of $\mathbb{Z}[\omega ]$.

The Euclidean norm on the Eisenstein integers makes this ring a principal ideal domain. Since irreducible elements of a principal ideal domain are prime, $p$ admits a factorization $p=uv$ into two nonunits. The positive integral Eisenstein norm is multiplicative, and its value is one exactly on units: when $N(u)=1$, its complex conjugate is an inverse. Thus $N(u),N(v)>1$ and $N(u)N(v)=p^2$, forcing both norms to be $p$. Writing $u=a+b\omega$ proves the displayed representation.

Every complex number can be written uniquely as $x+y\omega$ with real $x,y$, where $\omega =(-1+i\sqrt{3})/2$. Round $x,y$ separately to integers $m,n$. The error is $s+t\omega$ with $|s|,|t|\le 1/2$, andFor Eisenstein integers $\alpha ,\beta$ with $\beta \ne 0$, apply this to $\alpha /\beta$ to choose $q=m+n\omega$. The remainder $r=\alpha -q\beta$ is an Eisenstein integer and $N(r)\le 3N(\beta )/4<N(\beta )$ if nonzero. Thus the Eisenstein norm is a Euclidean function and these integers form a Euclidean domain. Coordinate rounding suffices; no closest-point theorem is needed.