Skip to main content

Abstract algebra A Kursobjekt for Math 331

Aaron Greicius

Section 2.11 Euclidean domains

Definition 2.11.1. Euclidean domain.

A \(Euclidean domain\) is a pair \((R,N)\text{,}\) where \(R\) is an integral domain and \(N\) is a function \(N\colon R-\{0\}\rightarrow \Z_{\geq 0}\) satisfying the following generalized division algorithm condition: for all nonzero \(a\in R\) and all \(b\in R\text{,}\) there exists elements \(q,r\in R\) satisfying
  1. \(b=qa+r\text{,}\)
    🔗
    🔗
  2. either \(r=0\) or \(N(r)< N(a)\text{.}\)
    🔗
    🔗
🔗
🔗

Definition 2.11.2. Norm function on \(\C\).

Given \(z=a+bi\in \C\text{,}\) where \(a,b\in \R\text{,}\) we define
\begin{align*} N(z) \amp =z\overline{z}=(a+bi)(a-bi)=a^2+b^2\text{.} \end{align*}
We call the function \(N\colon \C\rightarrow \R_{\geq 0}\) the norm function on \(\C\text{.}\)
🔗
🔗

Specimen 31. Gaussian integers.

The subring \(\Z[i]=\{m+n i\mid m,n\in \Z\}\) of \(\C\) is called the ring of Gaussian integers. The pair \((\Z[i], N)\text{,}\) where \(N\colon \Z[i]-\{0\}\rightarrow \Z_{\geq 0}\) is the restriction of the norm function on \(\C\) to \(\Z[i]\text{,}\) is a Euclidean domain.
🔗
Given a nonzero \(z\in \Z[i]\) and any \(w\in\Z[i]\text{,}\) you can produce a pair \(q,r\) satisfying the division algorithm conditions as follows:
  1. find \(\alpha\in \Q[i]\) satisfying \(qz=w\text{;}\)
    🔗
    🔗
  2. write \(\alpha=q+(s+ti)\text{,}\) where \(q\in \Z[i]\) and \(\{\abs{s},\abs{t}\}\subseteq [0,1/2]\text{;}\)
    🔗
    🔗
  3. we have \(w=qz+r\text{,}\) where \(r=w-zq\) satisfies \(r=0\) or \(N(r)< N(z) \text{.}\)
    🔗
    🔗
🔗
🔗

Proof.

This proof is almost identical to the proof that \(\Z\) is a PID, as well as the proof that \(F[x]\) is a PID, where \(F\) is a field. And for good reason! Both those previous proofs make use of a form of the division algorithm, which is accessible thanks to these rings being Euclidean domains. We reprise the argument in full detail.
🔗
Clearly the zero ideal is principal. Let \(I\) be a nonzero ideal. The set \(N(I-\{0\})\) is a nonempty subset of \(\Z_{\geq 0}\text{,}\) and accordingly has a least element \(n\text{.}\) Let \(a\in I\) be an element of \(I-\{0\}\) satisfying \(N(a)=n\) for this minimum value. We claim that \(I=(a)\text{.}\) Indeed, since \(a\in I\text{,}\) we have \((a)\subseteq I\text{.}\) Next given any \(b\in I\text{,}\) we can write
\begin{align*} b \amp =qa+r \end{align*}
where \(q,r\in R\) and either \(r=0\) or \(N(r)< N(a)\text{.}\) Since \(r=b-qa\in I\text{,}\) and since \(n=N(a)\) is the least element of \(N(I-\{0\})\text{,}\) we must have \(r=0\text{.}\) But then \(b=aq\in (a)\text{,}\) showing that \(I\subseteq (a)\text{.}\) We conclude that \(I=(a)\text{,}\) as claimed.
🔗
🔗

Remark 2.11.4. Euclidean domains are principal.

Theorem 2.11.3 can be summarized as follows:
\begin{align*} \text{Euclidean domain} \amp \implies \text{PID} \text{.} \end{align*}
Surprisingly, the converse implication does not hold: that is,
\begin{align*} \text{PID} \amp \not\Rightarrow \text{Euclidean domain}\text{.} \end{align*}
For example, you can show that the ring \(\Z[\alpha]\text{,}\) \(\alpha=\tfrac{1}{2}+\tfrac{\sqrt{19}}{2}i\) is a PID, but not a Euclidean domain. (See the Dummit and Foote text.)
🔗
🔗

Definition 2.11.5. Greatest common divisor and least common multiple.

Let \(R\) be an integral domains. Given elements \(a,b\in R\) a greatest common divisor (or GCD) of \(a\) and \(b\) is an element \(d\in R\) satisfying the following conditions:
  1. \(d\mid a\) and \(d\mid b\text{;}\)
    🔗
    🔗
  2. if \(d'\in R\) satisfies \(d'\mid a\) and \(d'\mid b\text{,}\) then \(d'\mid d\text{.}\)
    🔗
    🔗
🔗
A least common multiple (or LCM) of \(a\) and \(b\) is an element \(m\in R\) satisfying the following conditions:
  1. \(a\mid m\) and \(b\mid m\text{;}\)
    🔗
    🔗
  2. if \(m'\in R\) satisfies \(a\mid m'\) and \(b\mid m'\text{,}\) then \(m\mid m'\text{.}\)
    🔗
    🔗
More generally, a greatest common divisor of elements \(a_1,a_2,\dots, a_n\) of \(R\) is an element \(d\in R\) such that \(d\mid a_i\) for all \(i\text{,}\) and if \(d'\in R\) satisfies \(d'\mid a_i\) for all \(i\text{,}\) then \(d'\mid d\text{.}\) Lastly, we say that elements \(a_1,a_2,\dots, a_n\) are relatively prime if they have \(1\) as a GCD.
🔗
🔗

Remark 2.11.6. GCDs and LCDs.

Although the definition of GCDs and LCMs is a straightforward generalization of the corresponding notion from the integers, you should proceed with caution when making use of these concepts. In particular, be aware of the following facts:
  • GCDs and LCMs need not exist in an arbitrary commutative ring;
    🔗
    🔗
  • if GCDs and LCMs do exist, they are only unique modulo multiplication by a unit.
    🔗
    🔗
The uniqueness issue is already in evidence in the context of the integers. To nonzero integers \(a, b\) will always have two GCDs, namely \(\gcd(a,b)\) and \(-\gcd(a,b)\text{,}\) where \(\gcd(a,b)\text{,}\) as you will recall, is defined to be the greatest positive integer dividing \(a\) and \(b\text{.}\)
🔗
🔗
Let \((R,N)\) be a Euclidean domain. Since \(R\) is a PID, GCDs exist for all sets \(\{a,b\}\ne \{0\}\text{.}\) Whereas in general it might be challenge to actually produce a GCD, the division algorithm condition for Euclidean domains provides us with an algorithm of sorts, called the Euclidean algorithm.
🔗

Proof.

First we prove (1), using Proposition 2.5.17. In general, assume we have \(b=qa+r\text{.}\) Since \(a\in (a,r)\) and \(b=qa+r\in (a,r)\text{,}\) we have \((a,b)\subseteq (a,r)\text{.}\) Similarly, since \(a\in (a,b)\) and \(r=b-qa\in (a,b)\text{,}\) we have \((a,r)\subseteq (a,b)\text{.}\)
🔗
From (1), it follows by induction that if we have a sequence of division algorithm instances as in (2), then we have
\begin{align*} (a,b) \amp =(a,r_1)=(r_1,r_2)=\dots =(r_n,r_{n+1})=(r_{n+1})\text{.} \end{align*}
It suffices, then, to show that there is such a sequence. The basic idea is that at each step
\begin{align*} r_{k} \amp =q_{k+2}r_{k+1}+r_{k+2}\text{,} \end{align*}
if \(r_{k+2}\ne 0\text{,}\) then we can apply the division algorithm to \(r_{k+2}\) and \(r_{k+1}\text{.}\) Since at each step where the remainder is nonzero, the successive remainder has strictly smaller \(N\)-value, the process must terminate: i.e., at some point we must have \(r_{k}=0\text{.}\) (To make this argument rigorous, we would have to re-case it as an induction argument. There nothing difficult in doing so, but we will spare you this technicality.)
🔗
Statement (3) follows immediately from (2), though again strictly speaking an induction argument should be used.
🔗
🔗

Example 2.11.10. GCD in polynomial ring.

Use the Euclidean algorithm to find a GCD \(h\) of \(f(x)=x^5+2x^3+x-1\) and \(g(x)=x^4+x^2+1\) in the ring \(\Q[x]\text{,}\) and write \(h=pf+qg\text{,}\) where \(p,q\in \Q[x]\text{.}\)
🔗
Solution.
We apply the Euclidean algorithm (using polynomial long division) to the set \(\{f,g\}\text{:}\)
\begin{align*} x^5+2x^3+x-1 \amp = x(x^4+x^2+1)+x^3-1\\ x^4+x^2+1 \amp = x(x^3-1) + x^2+x+1\\ x^3-1 \amp = (x-1)(x^2+x+1) + \boxed{0}\text{.} \end{align*}
Thus \(d(x)=x^2+x+1\) is a GCD of \(f\) and \(g\text{,}\) and we have
\begin{align*} d(x) \amp =x^4+x^2+1-x(x^3-1) \\ \amp =x^4+x^2+1-x(x^5+2x^3+x-1-x(x^4+x^2+1)) \\ \amp =(-x)(x^5+2x^3+x-1) +(x^2+1)(x^4+x^2+1)\\ \amp =(-x)f(x)-(x-1)g(x)\text{.} \end{align*}
🔗
🔗
🔗

Example 2.11.11. Ideal generator in \(\Z[i]\).

Find a Gaussian integer \(z\) satisfying \((2,1+3i)=(z)\) and express \(z\) as \(z=\alpha\cdot 2+\beta\cdot(1+3i)\) for elements \(\alpha, \beta\in \Z[i]\text{.}\)
🔗
Solution.
Since \(\Z[i]\) is a Euclidean domain, and hence a PID, we know that \((2,1+3i)\) is a principal ideal, generated by a GCD of \(2\) and \(1+3i\text{.}\) Noting that \(N(2)=4\) and \(N(1+3i)=10\text{,}\) we start a Euclidean algorithm by dividing \(1+3i\) by \(2\text{.}\)
\begin{align*} 1+3i \amp =(1+i)2+(-1+i)\\ 2 \amp =(-1+i)(-1-i)+\boxed{0}\text{.} \end{align*}
We conclude that \(z=-1+i\) is a GCD of \(2\) and \(1+3i\text{,}\) and hence that \((1+3i,2)=(-1+i)\text{.}\) Furthermore, we have
\begin{align*} (-1+i) \amp =(1+3i)-(1+i)2\text{.} \end{align*}
🔗
🔗
🔗
🔗
PrevTopNext