2.4: Principal Ideals and Euclidean Domains
 Page ID
 82465
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\ #1 \}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\ #1 \}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left#1\right}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)In this section, we'll seek to answer the questions:
 What are principal ideals, and what are principal ideal domains?
 What are Euclidean domains, and how are they related to PIDs?
One of the ways in which mathematicians study the structure of an abstract object is by considering how it interacts with other (related) objects. This is especially true of its subobjects. Thus, in linear algebra, we are often concerned with subspaces of a vector space as a means of understanding the vector space, or even submatrices as a way of understanding a matrix (see, e.g., the cofactor expansion formula for the determinant). In real analysis and topology, the important subobjects are usually open sets, or subsequences, and the study of a graph's subgraphs is an important approach to many questions in graph theory.
In this section, we begin a settheoretic structural exploration of the notion of ring by considering a particularly important class of subring which will be integral to our understanding of factorization.
These subrings are called ideals. They arose in the work of Kummer and Dedekind as a way of trying to recover some notion of unique factorization in rings that do not have properties like the fundamental theorem of arithmetic in \(\mathbb{Z}\text{.}\)
A subset \(I\) of a (not necessarily commutative) ring \(R\) is called an ideal if:
 \(\displaystyle 0\in I\)
 for all \(x,y\in I\text{,}\) \(x+y\in I\text{;}\) and,
 for all \(x\in I\) and for all \(r\in R\text{,}\) \(xr\in I\) and \(rx\in I\text{.}\)
Observe that the third requirement for a set \(I\) to be an ideal of \(R\) is simplified slightly if \(R\) is commutative (which, we recall, all of our rings are).
There are many important examples and types of ideals, but there are also some trivial ideals contained in every ring.
Let \(R\) be a ring. Then \(R\) and \(\{0\}\) are ideals of \(R\text{.}\)
All ideals are subrings.
The following theorem provides a useful characterization of when an ideal \(I\) is in fact the whole ring.
Let \(R\) be a ring and \(I\) an ideal of \(R\text{.}\) Then \(I = R\) if and only \(I\) contains a unit of \(R\text{.}\)
The most important type of ideals (for our work, at least), are those which are the sets of all multiples of a single element in the ring. Such ideals are called principal ideals.
Let \(R\) be commutative with identity and let \(a\in R\text{.}\) The set
\begin{equation*} \langle a \rangle= \{ra : r\in R\} \end{equation*}
is an ideal (called the principal ideal generated by \(a\)).
The element \(a\) in the theorem is known as a generator of \(\langle a \rangle\text{.}\)
Let \(R\) be commutative with identity, and let \(x,y,z\in R\text{.}\) Give necessary and sufficient conditions for \(z\in \langle x \rangle\) and, separately, \(\langle x \rangle \subseteq \langle y \rangle\text{.}\)
That is, fill in the blanks: “\(z\in \langle x \rangle \Leftrightarrow\) _________” and “\(\langle x \rangle\subseteq \langle y \rangle \Leftrightarrow\) _________.”
Justify your answers.
Principal ideals may have more than one generator.
Let \(R\) be a ring and \(a\in R\text{.}\) Then \(\langle a \rangle= \langle ua \rangle\text{,}\) where \(u\) is any unit of \(R\text{.}\)
In \(R = \mathbb{Z}\text{,}\) describe the principal ideals generated by
 2
 \(\displaystyle 9\)
 9
 0
 27
 3
Determine the subset relations among the above ideals.
It is the case in many familiar settings that all ideals are principal. Such domains are given a special name.
An integral domain \(R\) in which every ideal is principal is known as a principal ideal domain(PID).
The ring \(\mathbb{Z}\) is a principal ideal domain.
 Hint

Use properties specific to \(\mathbb{Z} \text{,}\) perhaps from Section 1.
Find an integer \(d\) such that \(I = \langle d \rangle\subseteq \mathbb{Z}\text{,}\) if
 \(\displaystyle I = \{4x+10y: x,y\in\mathbb{Z}\}\)
 \(\displaystyle I = \{6s+7t : s,t\in\mathbb{Z}\}\)
 \(\displaystyle I = \{9w+12z : w,z\in\mathbb{Z}\}\)
 \(\displaystyle I = \{am+bn : m,n\in\mathbb{Z}\}\)
You do not need to prove that each of the sets above are ideals (though you should make sure you can do it).
Let \(R\) be a principal ideal domain and \(x,y\in R\) be not both zero. Let \(I = \{xm+yn: m,n\in R\}\text{.}\) Then:
 \(I\) is an ideal, and
 \(I = \langle d \rangle\text{,}\) where \(d\) is any greatest common divisor of \(x\) and \(y\text{.}\)
We conclude that there exist \(s,t\in R\) such that \(d = xs + yt\text{.}\)
We have so far abstracted and axiomatized several important algebraic properties of \(\mathbb{Z}\) that we discussed in § 1. In particular, we have our usual operations of addition and multiplication, and their interactions; we have notions of divisibility/factorization, irreducibility, and primality; we also have cancellation and greatest common divisors.
Our last major abstraction from \(\mathbb{Z}\) is the division algorithm. The main obstacle to postulating domains with a division algorithm is a clear notion of comparison relations. That is, if \(R\) is an arbitrary domain with \(r,s\in R\text{,}\) is it possible to clearly and sensibly say which of \(r\) or \(s\) is “bigger” ? (Recall that this was a requirement for the division algorithm with nonzero remainders.) However, if there is a way to relate elements of a domain \(R\) to \(\mathbb{N}_0\text{,}\) we can sensibly define a division algorithm.
Let \(R\) be an integral domain. We call \(R\) a Euclidean Domain if there is a function \(\delta : R\setminus \{0\} \to \mathbb{N}_0\) such that:
 If \(a,b\in R\setminus \{0\}\text{,}\) then \(\delta(a) \le \delta(ab)\text{.}\)
 If \(a,b\in R\text{,}\) \(b\ne 0\text{,}\) then there exist \(q,r\in R\) such that \(a = bq+r\text{,}\) where either \(r = 0\) or \(\delta(r) \lt \delta(b)\text{.}\)
We call the function \(\delta\) a norm for \(R\text{.}\)
\(\delta\): This is the lowercase Greek letter delta.
Thus, a Euclidean domain is an integral domain with a division algorithm that behaves in a familiar way. In the remainder of this section, we will investigate the properties of Euclidean domains. First, we consider some examples.
The field \(\mathbb{Q}\) is a Euclidean domain under ordinary addition and multiplication, with \(\delta(x) = 0\) for all \(x\in \mathbb{Q}\text{.}\)
Is \(\mathbb{Z}\) a Euclidean domain? If so, what is the norm function \(\delta\text{,}\) and why does this function have the required properties of a norm?
Let \(F\) be a field and \(S\subseteq F[x]\) a set containing a nonzero polynomial. Prove that \(S\) contains a polynomial \(f\) such that \(\deg(f) \le \deg(g)\) for all nonzero \(g\in S\text{.}\)
Let \(F\) be a field and \(f(x),g(x)\in F[x]\) with \(g(x)\ne 0\text{.}\) If \(\deg f(x) \ge \deg g(x) > 0\text{,}\) and \(f(x) = a_0 + a_1 x + \cdots + a_m x^m\) and \(g(x) = b_0 + b_1 x + \cdots + b_n x^n\text{,}\) then \(h(x) = f(x)  a_m b_n^{1} x^{mn} g(x)\) has degree strictly less than \(\deg f(x)\text{.}\)
Let \(F\) be a field and \(f(x),g(x)\in F[x]\) with \(g(x)\ne 0\text{.}\) Then there exist unique \(q(x), r(x) \in F[x]\) such that
\begin{equation*} f(x) = g(x) q(x) + r(x)\text{,} \end{equation*}
where \(\deg(r(x)) \lt \deg g(x)\text{.}\)
 Hint

For existence, consider three cases: \(f(x) = 0\text{;}\) \(f(x) \ne 0\) and \(\deg f \lt \deg g\text{;}\) \(f(x) \ne 0\) and \(\deg f \ge \deg g\text{.}\) In the last case, use induction on \(m = \deg f(x)\text{.}\) For uniqueness, mimic the uniqueness proof of Theorem 1.2.4.
Let \(F\) be a field. Then the ring \(F[x]\) is a principal ideal domain.
 Hint

Mimic the proof of Theorem 2.4.6 and use Lemma 2.4.2 !
Is \(F[x]\) a Euclidean domain for all fields \(F\text{?}\) If so, what is the norm function \(\delta\text{,}\) and why does this function have the required properties of a norm? If not, why not? Prove your answer.
In fact, every Euclidean domain is a PID.
Every Euclidean domain is a principal ideal domain.
 Hint

Mimic the proof of Theorem 2.4.6 .
Where do Euclidean domains and PIDs fit in the hierarchy of abstraction found in Exploration 2.3.5?