2.7. PIDs and Euclidean Domains.
Rings were invented in order to generalize mathematical domains which are parralel to the properties of integers and polynomials, since there exist many mathematical structures which share such properties. Two major properites of interest include the fundamental theorem of arithmetic and factorization via Euclid's algorithm. These concepts generalize to rings, specifically to Principal Ideal Domains, which we will demonstrate in this section.
First we begin with defintions.
Let \(R\) be a commutative ring, and suppose \(a, b \in R\) are nonzero. Then
- [1.] We say \(a\) divides \(b\) if \(b = ac\) for some \(c \in R\). This is denoted as \(a\mid b\).
- [2.] Let \(a\) not be a unit. Then \(a\) is irreducible if \(a = bc\) implies \(b\) or \(c\) is a unit.
- [3.] If \(a\) is not a unit, then \(a\) is prime if \(a | bc\) implies \(a|b\) or \(a | c\).
As a consquence of these definitions, we have the following proposition.
Let \(R\) be an integral domain and suppose \(a, b \in R\) are nonzero. Then
- 1. If \(\left< a \right>\) is the principal ideal generated by \(a\), then \(a \mid b\) if and only if \(\left< b \right> \subset \left< a \right>\).
- 2. The element \(a\) is a prime element of \(R\) if and only if \(\left< a \right>\) is a prime ideal.
- 3. If \(a \mid b\) then \(au \mid bv\) for any units \(u,v \in R\)
- 4. If \(a \mid b\) and \(a\) is not a unit then \(b\) is not a unit.
- 5. If \(p\) is prime and \(p \mid a_1a_2\cdots a_n\) then \(p \mid a_i\) for some \(i \in \{1, 2, \dots, n\}\).
- 1. (\(\implies\)) Suppose \(a \mid b\). Then \(b = ac\) for some \(c \in R\). Now observe that
Since \(\left< a \right>c \subset \left< a \right>\), we have that \(\left< b \right> \subset \left< a \right>\), as desired.
(\(\impliedby\)) Now suppose that \(\left< b \right> \subset \left< a \right>\). Then \(b \in \left< a \right>\), so that \(b = ac\) for some \(c \in R\). Hence, \(a \mid b\), which proves the result. * 2. This is just the definition of an element being prime in \(R\). * 3. Suppose \(a \mid b\) and let \(u, v\) be units. Since \(b = ac\) for some \(c\in R\), we see that \(bu = acv = avc\). Therefore \(bu \mid av\). (Since \(u, v\) were units, they are not zero divisors, so they did not change the value of the equation.) * 4. Suppose \(a\) is not a unit and \(a \mid b\) for some \(b \in R\). Suppose for the sake of contradiction that \(b\) is a unit. Then \(b = ac\) for some \(c \in R\), and furthermore there exists a \(d \in R\) such that \(br = 1\).
Therefore, \(bd = acd \implies 1 = acd\). Hence \(a\) is a unit since \(a(bd) = (bd)a= 1\). But this is a contradiction since we said \(a\) was not a unit, which completes the proof. * 5. Let \(p\) be a prime element and suppose \(p \mid a_1a_2 \cdots a_n\) for elements \(a_1, a_2, \dots, a_n \in R\). Then \(a_1a_2\cdots a_n = pb\) for some \(b \in R\). Hence we see that \(a_1a_2\cdots a_n \in Rp\). Since \(p\) is prime, \(Rp\) is a prime ideal and hence one element \(a_i\) where \(i \in \{1, 2, \dots, a_n\}\) must be in \(P\). In other words, \(p \mid a_i\) for some \(i \in \{1, 2, \dots, n\}\), as desired.
The above propsition generalizes rules that we hold to be familiar in \(\ZZ\). For example, we know the units of \(\ZZ\) are \(\{1, -1\}\), and it is obvious to us that if \(a \mid b\) for some integers \(a, b\) then \(-1\cdot a \mid -1\cdot b\) and \(1 \cdot a \mid 1 \cdot b\). We also know that if \(p\) is prime integer and \(p \mid a_1a_2\cdots a_n\) for some integers \(a_1, a_2 \dots, a_n\) then \(p \mid a_i\) for some \(i \in \{1, 2, \dots, n\}\). The proposition just tells us that our intuition on \(\ZZ\) does in fact generalize to integral domains, and what we've seen in \(\ZZ\) is just a tiny snap shot of algebra at work.
Let \(R\) be an integral domain. If \(p \in R\) is prime then \(p\) is also irreducible.
Let \(p \in R\) be prime and suppose \(p = qm\) for some \(q, m \in R\). Then by definition we know that \(p \mid q\) or \(p \mid m\). Without loss of generality suppose \(p \mid q\). Then \(q = pc\) for some \(c \in R\). Then we have that
where we used the cancellation law, valid on integral domains. Then \(m\) is a unit, and hence by definition this implies that \(p\) is irreducible.
\textcolor{Red}{Keep in mind that the converse of the above statement is not true. It will, however, turn out to be true for PIDs.}
We now see that greatest common divisors can be generalized to integral domains.
Let \(R\) be an integral domain and let \(A \subset R\) be nontrivial. Then we define
Say \((R, +, \cdot)\) is an integral domain. That is, a commutative rwith \(1 \ne 0\) having no zero divisors. We say it is a Euclidean Domain if
- 1. We have a map \(N: R \to mathbb{Z}_{\ge 0}\) with \(N(0)= 0\).
- 2. Given \(a, b \in R\), we can find \(q, r \in R\) with \(a = bq + r\) and either \(r = 0\) or \(N(r) < N(b)\).
Every ideal in a Euclidean Domain is principal. That is,
Question: Are there PIDs that are not Euclidean Domains?
\subsection*{Unique Factorization Domain}
Say \((R, +, \cdot)\) is an integral domain. Pick \(r \in R\) that is neither zero nor a unit, i.e., \(r \not\in R^{\times}\cup\{0\}\).
We say that \(R\) is irreducible if when \(r=ab\) either \(a \in R^{\times}\) or \(b \in R^{\times}\). Otherwise, we say that r is reducible.
Example. Say \(R = \ZZ\). Then
We say \(R\) is a Unique Factorization Domain (UFD) if the following holds for all \(r \in R^{\times} \cup \{0\}\):
- 1. \(r = p_1p_2\cdots p_m\) is a finite product of irreducibles \(p_i \in R\).
- 2. If \(r = q_1q_2\cdots q_m\) is another factorization into irreducibles, then \(n = m\) and \(q_i=q_i \cdot p_i\) for some \(u_i \in R^{\times}\).
Again, let \(R = \ZZ\) and observe that \(r = 6 = 2 \cdot 3 = (-2)\cdot(-3)\). Really, we see that \(2 = (-1)\cdot 2\) and \(3 = (-1)\cdot 3\).
Say \(R\) is a UFD. Given \(r \not\in R^{\times} \cup\{0\}\), the following are equivalent:
- 1. If \(I = (r)\) is a nonzero prime ideal of \(R\).
- 2. \(r\) is irreducible.
Remark: We avoid saying "\(r\) is prime", we say "\(I = (r)\) is prime".
- \(\bm{i \implies ii}\) Assume \(I = (r)\) is a prime Write \(r = a \cdot b\). We want to show either \(a \in R^{\times}\) and \(b \in R^{\times}\).
We have \(a \cdot b = r \in I\), so by definition either \(a \in I\) or \(b \in I\). Either \(a = v \cdot r\) where \(b = u \cdot r\) for some \(u, v \in R\).
Hence either \(r = a \cdot b = (v \cdot r)\cdot b\) or \(r = (v \cdot a) \cdot r\). Since \(R\) is an integral domain, the cancellation law holds. Hence either
Since \(r \not\in R^{\times}\cup\{0\}\), either \(v \cdot b = 1\) or \(u \cdot a = 1\). Hence either \(b \in R^{\times}\) or \(a \in R^{\times}\) is a unit. * \(\bm{ii \implies i}\). Assume \(r \in R\). We'll show that \(I\) is a proper ideal. Since \(r \not\in R^{\times}\), we know that \(I \ne R\).
Now we show that \(I\) is prime. Say \(a, b \in R\) satisfying \(a \cdot b \in I\). We must show that either \(a \in I\) or \(b \in I\). Since \(a \cdot b \in I\), we can write \(a \cdot b = r \cdot c\) for some \(c \in R\). \ \ Case #1. Either \(a, b = 0\). Then either \(a, b \in I\). \ \ Case #2. Either \(a, b \in R^{\times}\). Without loss of generality, say \(a \cdot u = 1\). Then \(b = u \cdot r \cdot c \in I\). \ \ Case #3. \(a, b \not\in R^{\times}\cup\{0\}\). Since \(R\) is a UFD, factor \(a\) and \(b\).
Hence \(a \cdot b = p_1\cdots p_nq_1 \cdots q_m\). But \(r\) is an irreducible that divides \(a \cdot b = c \cdot r\). Thus either \(q_i = u \cdot r\) or \(p_j = v \cdot r\) for some \(i, j\). But then either
if for example \(i, j= 1\).
Say \((R, +, \cdot)\) is an integral domain. We say \(R\) is a principal ideal domain (PID) if every ideal \(I = (r)\) is principal.
- 1. If \(R\) is a Euclidean Domain, then \(R\) is a PID.
- 2. If \(R\) is a PID, then \(R\) is a UFD.
Here's a diagram of what we have so far.
We showed (1) before. Now we show (2). Assume \(R\) is a PID. We'll show that every \(r \in R\) that is nonzero has unique factorization.
where \(u \in R^{\times}\) and \(p_i\) are irreducibles. We will in two parts: (i) existence (of at least one factorzation) and (ii) uniqueness (of at most one factorization).
- Existence. Consider
We want to show that \(S = \varnothing\). Thus assume otherwise. Pick some \(I_1 = (r_1)\) in \(S\). Then \(r_1 \not\in R^{\times}\cup\{0\}\) and \(r_1\) is not irreducible. This means that \(r_1\) is reducible, so write
Consider \(I_2 = (r_2)\) and \(I_2' = (r_2')\). If both \(r_2, r_2'\) have factorizations into irreducibles, then so would \(r_1 = r_2\cdot r_2'\). Thus without loss of generality, \(r_2\) does not have a factorization into irreducibles. Thus the ideal \(I_2 \in S\). Observe \(I_1 \subsetneqq I_2\). We then have a chain of proper ideals:
Let \(\displaystyle I = \bigcup_{n \ge 1} I_n = (r_0)\) as the maximal ideal. ask: is \(I \in S\)? If \(I \in S\), then we see that \(I\) is not maximal. If \(I \not\in S\), then \(r_0\) can be written as a product of irreducibles. * Uniqueness. We show uniqueness. Consider a proof by induction via the following statement:
We will show \(P(n)\) is true for \(n=0,1,2\). * Base Case. If \(r \ne 0\) has a factorization into \(n = 0\) irreducibles, then \(r = u\) is a unit. Say it has a second factorization
$$
r = u \cdot q_1 \cdots q_n \text{ for } m>0.
$$
Then
$$
1 = (u^{-1}\cdot v \cdot q_1 \cdots q_m)\cdot q_m
$$
So $q_m \in R^{\times}$ is a unit. This is a contradiction
* **Induction.** Suppose that $P(n_0)$ is true for some $n_0 \ge 0$.
Then we'll show that $P(n_0 + 1)$ is true. Consider $r
\ne 0$ that is the product of $n$ irreducibles:
\begin{align*}
r & = u \cdot p_1 \cdots p_n\\
& = (u \cdot p_1 \cdots p_{n_0}) \cdot p_n
\end{align*}
Say we have a second factorization:
$$
r = v \cdot q_1 \cdots q_m.
$$
We then have the following facts:\\
$P = (p_n)$ is a prime ideal of $R$. (Recall $I = (r)$
is prime if and only if $r$ is irreducible.)\\
$\overline{Q_i} = q_i \cdot P$ is a coset in
$\overline{R} = R/P$. Not all $\overline{q_i} \ne
\overline{0}$. Why? Because
$$
\overline{u} \cdot \overline{q_1} \cdots \overline{q_m}\overline{p_m} = \overline{u\cdot q_1 \cdots q_m} \cdot \overline{p_m} = 0.
$$
Since $\overline{R}$ is an integral domain, without
of generality, suppose $\overline{q_m} =
\overline{0}$. Hence $q_m = q_m \cdot p_n$. Now
consider
$$
(u \cdot p_1 \cdots p_{n_0}) \cdot p_n
=
r
=
(u_m\cdot v \cdot q_1 \cdots q_{m-1})\cdot p_n.
$$
Since we're in an integral domain, we can use the
cancellation law. Hence we have that
$$
u\cdot p_1 \cdots p_{n_0} = (u_m \cdot v)\cdot q_1 \cdots q_{m-1}.
$$
Now we can invoke the inductive hypothesis. We see
that $m - 1 = n_0$ and $q_i = u_i \cdot p_i$ for some
unit $u_i \in R^{\times}$. However, this is equivalent
to saying that $m = n$. and as we showed $q_m = u_m
\cdot p_n$, we have that the factorizations are the
same. Hence $P(n)$ is true for all positive integers.
Primes, irreducibles and Maximal Ideals.\
Say \((R, +, \cdot)\) is a PID. Then the following are equivalent for \(r \in R\) with \(r \not\in R^{\times}\cup\{0\}\):
- i. \(r\) is irreducible.
- ii \(I = (r)\) is a prime ideal.
- iii. \(I=(r)\) is a maximal ideal.
First observe that \(i \iff ii\) since they are true in a UFD, and we know that a PID is a UFD. Hence we just need to show that \(ii \iff iii\).
We show that \((ii \iff iii)\). By way of contradiction, sy \(I = (r)\) is a prime that is not maximal. Then we can find an ideal \(M = (a)\) such that \(I \subsetneqq M \subsetneqq R\). This means that \(a | r\). That is, one can find \(a, b \in R\) such that \(r = a\cdot b\).
Since \(I\) is prime and \(a \cdot b \in I\), either \(a \in I\) or \(b \in I\). If \(a \in I\), then \(M = (a) \subset I\), which would imply that \(M = I\). Thus we have a contradiction.
Thus we need that \(b \in I\). Since \(b \in I = (r)\), write \(b = u \cdot r\). Then \(r = a \cdot b = (u \cdot a) \cdot r\). Since \(r \ne 0\), we find \(u \cdot a = 1\). This means that \(a \in R^\times\) so \(M = (a) = R\). But \(M \subsetneqq R\), so again we find a contradiction.
Thus we see that \(I\) must be a maximal ideal. The other direction, that every maximal ideal is a prime ideal, is trivial.
\section{Dedekind-Hasse Norms.} Motivating questions.*
- 1. Are there examples of PIDs that are not Euclidean Domains?
- 2. Are there examples of PIDs that are not \(\ZZ\)?
Say \((R, +, \cdot)\) is an integral domain. A norm is a map \(\mathbb{N} : R \to \mathbb{Z}_{\ge 0}\). such that \(\mathbb{N}(0) = 0\).
On the other hand, a Dedekind-Hasse Norm is a norm \(\mathbb{N}\) satisfying
- DH1. \({N}(0) = 0\)
- DH2. \(N(a) > 0\) for all \(a > 0\)
-
DH3. For all nonzero \(a, b \in R\), either
- 1. \(b\) divides \(a\), i.e., \(a = q \cdot b\) or
- 2. there exits \(s, t \in R\) such that
\[ x = s \cdot a - t \cdot b \in (a , b) \]satisfies \(0 < N(x) < N(b)\).
Remark: If in (DH3) we can always choose \(s = 1\), then we say that \(R\) is a Euclidean Domain.
Examples.\ Let \(R = \mathbb{Z}\). This a Euclidean Domain. The statement (DH3) is the Euclidean algorithm for \(N(a) = |a|\). \ \ Let \(R\) be any integral domain. Then \(S = R[x]\) is also an integral domain. We define a norm on \(S\) be saying \(N(g(x)) = \text{deg}(g)\) if \(g \ne 0\). If \(g(x) \equiv 0\) is the zero polynomial, then \(\deg(g) = -\infty\). So define \(N(0) = 0\). This is not Dedekind-Hasse. As an example, consider \(R = \ZZ\). Then let \(I =(2, x)\) in \(S\). This is not a principal ideal.
Now consider \(F\) a field. Let \(S' = F[x]\) which is a PID. Define \(N(g(x= 2^{\deg(g)}\). And \(N(0) = 2^{-\infty} = 0\).