A Euclidean domain (ED) is a domain \(R\) together with a norm function \(N: R \to \Z_{\geq 0}\) such that \(N(0) = 0\) and the following property holds: for any two elements \(a, b \in R\) with \(b \ne 0\text{,}\) there are elements \(q\) and \(r\) of \(R\) such that
\begin{equation*}
a = qb + r \;\text{and either}\; r = 0 \;\text{or}\; N(r) < N(b).
\end{equation*}
Qual Watch.
Stating Definition 10.1 was Part (a) of [cross-reference to target(s) "jan-2020-4" missing or not unique] on the [cross-reference to target(s) "jan-2020" missing or not unique] qualifying exam.
In a Euclidean domain, division with remainder is possible, and the remainder is always smaller than the divisor. This property is similar to the Division Algorithm for integers, which is what makes Euclidean domains so useful in number theory and algebra.
Lets take a look at some examples to deepen our understanding.
Example10.2.Trivial Norm.
A "degenerate example" is a field \(F\) equipped with the trivial norm \(N(r) = 0\) for all \(r\text{.}\) Given \(a,b \in F\) with \(b \ne 0\text{,}\) we have \(a =(ab^{-1})b + 0\text{.}\) Note that in this example there is no need to include \(r=0\) in the description of the Division Algorithm, since \(b \ne 0\) implies \(|0| < |b|\text{.}\) This is not the case in other examples. Also observe that as we’ve defined remainders they are not unique. For example, in dividing \(13\) by \(5\text{,}\) both
are considered valid. This calculation shows, more generally, that if \(b\) is a unit, then for all \(a\) there exists an equation \(a = bq + r\) with \(r = 0\text{,}\) not matter what norm \(N\) is used. One could make remainders (and hence quotients) unique for \(\Z\) by insisting that remainders always be non-negative, but this is not part of the abstract theory since it doesn’t generalize to all cases well.
Example10.3.Polynomial Rings over Fields are Euclidean Domains.
The next classical example is \(F[x]\) with \(F\) a field and where we define the norm to be polynomial degree: \(N(f(x)) = \deg(f(x))\) if \(f\neq 0\) and \(N(0)=0\text{.}\) This ring is a Euclidean Domain because of the familiar long division for polynomials, as proved in Theorem 8.63.
Example10.4.Guassian Integers are a Euclidean Domain.
The ring \(R = \Z[i]\) of Gaussian integers is a Euclidean domain with \(N\) being the usual complex (Euclidean) square norm \(N(a+bi)=a^2+b^2\text{.}\) Let \(\alpha\text{,}\)\(\beta\)\(\in \Z[i]\) and let \(\frac{\alpha}{\beta}=p+qi \in \Q(i)\) (here we use that the fraction field of \(\Z[i]\) is \(\Q(i)\)). Now pick \(s,t\in\Z\) so that \(|p-s|\leq 1/2\) and \(|q-t|\leq 1/2\text{.}\) We have
Set \(q=s+ti\) and set \(r=\beta(p+qi)-\beta(s+ti)=\beta(s+ti-(p+qi))\) and notice that \(q\in \Z[i]\) because \(s,t\in\Z\) and \(r\in \Z[i]\) by closure. If \(r=0\) we’re good, and if \(r\neq 0\) then, using that the complex squared norm is multiplicative as well as the Pythagorean Theorem and the choice for \(s,t\text{,}\) we have
Thus the norm function \(N\) makes \(\Z[i]\) into a Euclidean domain.
Definition10.5.GCD.
Given elements \(a, b\text{,}\) not both \(0\text{,}\) of a Euclidean domain \(R\) with Euclidean norm \(N\text{,}\) a \(\gcd\) of \(a\) and \(b\) is an element \(g \in\R\) such that:
\(g | a\) and \(g | b\text{;}\) and
If \(d | a\) and \(d | b\text{,}\) then \(N (d) \leq N (g)\text{.}\)
Remark10.6.
Note that \(b\mid a\) is equivalent to \(b\in\igen a\text{.}\)
