LEC ALG3 9

Euclidean Domains

Definition 114.1(Definition).

An integral domain $R$ is called Euclidean if there is a function $d:R\setminus \{0\}\to \mathbb{N}$ with the following properties¹:

1. $d(a)\le d(ab)$ for all nonzero $a,b\in R$,
2. for all $a,b\in R$ with $b\ne 0$ we can find $q$ and $r$ in $R$ such that $a=bq+r$, $r=0$ or $d(r)<d(b)$.

3db377

The two main results about Euclidean domains: A Euclidean Domain is a PID, and the Euclidean algorithm terminates after finitely many steps yielding a gcd. There can be gcds in rings that are not Euclidean, but it may be hard in those rings to compute a gcd by a method that avoids factorization.

Clare distinguishes between ‘Euclidean ring’ (not a domain) and ‘Euclidean domain’. For example, If $R$ is a Euclidean domain, and $I$ is a nonprime ideal in $R,$ then $R/I$ is a Euclidean ring which is not a domain.

Proposition 114.2(Proposition).

Every ER is a PIR.

Proof.

Let$I\ne (0)$ be a proper ideal of $R$. Let $b$ be an element of minimum norm² in $I$. Let $a\in I$. We can write $a=qb+r$, where $r=0$ or $\sigma (r)<\sigma (b)$. Since $r=a-qb\in I$, $r$ must be $0$. Thus, we have $I=(b)$.□

c12bf3

In particular, every Euclidean domain is a principal ideal domain.

Example 114.3(Example).

• $\mathbb{Z}[i]$ is a euclidean domain, with $d(a)=|a{|}^2$. Division with remainder is not unique: There may be as many as four choices for the remainder. See Artin (2011, p. 361).
• $\mathbb{Z}[x]$ is not a Euclidean domain, since it is not a principal ideal domain. $\mathbb{Q}[x]$ is a Euclidean domain.
• $\mathbb{Z}[\sqrt{-5}]$ is not a Euclidean domain, since it is not a principal domain. See Dummit & Foote (2004, p. 272). It is also not a UFD, since $6$ does not have unique factorization. Factorization does terminate, however: this can be shown using the field norm on $\mathbb{Q}[\sqrt{-5}]$.
• $\mathbb{Z}[(1+\sqrt{-19})/2]$ is a PID but not a Euclidean domain. See Claim 302.7.
• A polynomial ring $\mathbb{F}[x]$ in one variable over a field $\mathbb{F}$ is a Euclidean domain, with $d(f)$ equal to the degree of $f$.

Greatest common divisors

Definition 114.4(Definition).

A greatest common divisor of $a$ and $b$ is a nonzero element $d$ such that $d|a$ and $d|b$, and if $d^{\prime }|a$ and $d^{\prime }|b$ then $d^{\prime }|d$.

Clearly, $\gcd (a,b)$ is a generator for the unique smallest principal ideal containing $a$ and $b$. Note that while $\gcd (a,b)$ is not unique, $(\gcd (a,b))$ is.

A sufficient condition for $\gcd (a,b)$ to exist is $(a,b)$ being a principal ideal $(d)$ (this is not a necessary condition: $(2,x)\subseteq \mathbb{Z}[x]$ is a maximal ideal, so $(1)$ is the unique smallest principal ideal containing $2$ and $x$). It follows that gcds always exist in a principal ideal domain:

Proposition 114.5(Proposition).

Let $R$ be a PID, and let $a,b\in R$ not both be zero. Let $(d)=(a,b)$. $d$ is a gcd of $a$ and $b$.

Remark 114.6(Remark).

When it happens that $(\text{gcd}(a,b))=(a,b)$ (in PIDs, for instance), we get to write $\text{gcd}(a,b)=ra+sb$ for some $r,s\in R$. Note that this is not the case with $(2,x)$ in $\mathbb{Z}[x]$: $(1)$ is strictly larger than $(2,x)$, and cannot be written as a linear combination of $2$ and $x$.

9467ec

---

Unique Factorization Domains

Definition 114.7(Definition).

We say that factoring in an integral domain $R$ is unique if, whenever an element $a$ of $R$ is written in two ways as a product of irreducible elements, say

$$p_1\dots p_m=a=q_1\dots q_n,$$

then $m=n$, and if the right side is rearranged suitably, $q_i$ is an associate of $p_i$ for each $i$.

When the recursive factoring of every nonunit nonzero element terminates, we say that factoring terminates in $R$.

Definition 114.8(Definition).

An integral domain $R$ is a unique factorization domain if

1. Factoring terminates in $R$: every element $x$ factors as a product $x=\prod x_i$ of finitely many irreducible $x_i$.
2. The irreducible factorization of an element $a$ is unique.

9fb28b

Proposition 114.9(Proposition).

Let $R$ be an integral domain. Factoring terminates in $R$ iff $R$ does not contain an infinite strictly increasing chain $(a_1)<(a_2)<\dots$ of principal ideals.

We will rarely encounter rings in which factoring fails to terminate; in practice it is the uniqueness that gives trouble.

Proposition 114.10(Proposition).

Let $R$ be an integral domain in which factoring terminates. Then $R$ is a UFD iff every irreducible element is a prime element.

Proof.

Let$R$ be a ring in which every irreducible element is prime, and suppose that an element $a$ factors in two ways into irreducible elements, say $p_1\dots p_m=a=q_1\dots q_n$, where $m\le n$. If $n=1$, then $m=1$ and $p_1=q_1$. Suppose $n>1$. Since $p_1$ is prime, it divides one of the factors $q_1,\dots ,q_n$, say $q_1$. Since $q_1$ is irreducible and. since $p_1$ is not a unit, $q_1$ and $p_1$ are associates, say $p_1=u{q}_1$, where $u$ is a unit. We move the unit factor over to $q_2$, replacing $q_1$ by $u{q}_1$ and $q_2$ by $u^{-1}{q}_2$. The result is that now $p_1=q_1$. Then we cancel $p_1$ and use induction on $n$.

Conversely, suppose that there is an irreducible element $p$ that is not prime. Then there are elements $a$ and $b$ such that $p$ divides $r:=ab$, say $pc=r$, but $p$ does not divide $a$ or $b$. By factoring $a$, $b$, and $c$ into irreducible elements, we obtain two inequivalent factorizations of $r$.□

414a66

Proposition 114.11(Proposition).

Every PID is a UFD.

Proof.

Let$R$ be a PID. Since every irreducible element of $R$ is prime, we only need to show that factoring terminates. Suppose we are given an infinite weakly increasing chain

$$(a_1)\subseteq (a_2)\subseteq (a_3)\subseteq \dots .$$

The union $J=\bigcup (a_n)$ is an ideal (this is true for any increasing chain of ideals in a ring): if $u$ and $v$ are in $J$, they must both be in $(a_n)$ for some $n$, so, $u+v$ and $ru$ for any $r\in R$ are also in $I_n$ and therefore they are in $J$. Since $R$ is a PID, $J$ is principal, say $J=(b)$. Since $b$ is in the union of the ideals $(a_n)$, it must be in one of them. But if $b$ is in $(a_n)$, then $(b)\subseteq (a_n)$. On the other hand, $(a_n)\subseteq (a_{n+1})\subseteq (b)$. Therefore $(b)=(a_n)=(a_{n+1})$. The chain is not strictly increasing.□

97c00a

It follows from Proposition 2 and Proposition 11 that every Euclidean domain is a UFD.

Divisibility in a UFD can be deduced from irreducible factorizations:

Proposition 114.12(Proposition).

Let $R$ be a UFD.

1. Let $a=p_1\dots p_m$ and $b=q_1\dots q_n$ be irreducible factorizations of two elements of $R$. Then $a|b$ iff $m\le n$ and, when $q_j$ are arranged suitably, $p_i$ is an associate of $q_i$ for $i=1,\dots ,m$.
2. Any pair of elements $a,b$, not both zero, has a gcd.

In particular, for one variable polynomial rings over fields, we have these results:

Theorem 114.13(Theorem).

Let $F[x]$ be the polynomial in one variable over a field $F$.

1. Two polynomials $f$ and $g$, not both zero, have a unique monic greatest common divisor $d$, and there are polynomials $r$ and $s$ such that $rf+sg=d$. Remark 6
2. Every irreducible polynomial in $F[x]$ is prime. Proposition 112.5 (4)
3. Every monic polynomial in $F[x]$ can be written uniquely as a product of irreducible monic polynomials.

Proposition 114.14(Proposition).

A polynomial $f$ of degree $n$ with coefficients in a field $F$ has at most $n$ roots in $F$.

497a71

Footnotes

1. $(1)$ is redundant: every integral domain with $d$ satisfying $(2)$ can be equipped with $d^{\prime }$ satisfying $(1)$ and $(2)$. See Conrad (n.d.). ↩

2. $\mathbb{N}$ is well ordered! ↩

---

References

Artin, M. (2011). Algebra (2. ed). Pearson Education, Prentice Hall.

Conrad, K. (n.d.). REMARKS ABOUT EUCLIDEAN DOMAINS.

Dummit, D. S., & Foote, R. M. (2004). Abstract Algebra (3rd ed). Wiley.