Chapter 8: Euclidean Domains, Principal Ideal Domains, and Unique Factorization Domains

8.1 Euclidean Domains

Definition: Any function $N:R\to \mathbb{Z}^{+}\cap \{ 0 \}$ with $N(0)=0$ is called a norm on the integral domain $R$. If $N(a)>0,\ \forall a\neq0$, then $N$ is called a positive norm.
Definition: The integral domain $R$ is said to be a Euclidean Domain or possess a Division Algorithm if $\exists N$ a norm on $R$ such that $\forall a,b\in R$ with $b \neq 0$, $\exists q,r\in R$ such that $a=qb+r$ and either $r=0$ or $N(r)<N(b)$. $q$ is the quotient and $r$ is the remainder.
Proposition 1: Every ideal $I$ in a Euclidean Domain $R$ is principal. More precisely, if $I\neq \emptyset$ then $I=(d)$, where $d\in I$, $d\neq0$, and $N(d)$ is minimal.
Definition: Let $R$ be a commutative ring and let $a,b\in R$ with $b \neq 0$.

• $a$ is a multiple of $b$ if $\exists x \in R$ such that $a=bx$. Then $b$ divides $a$ and is a divisor of $a$.
• A greatest common divisor of $a,b$ is some $d\neq0$ such that
• $d \mid a$ and $d \mid b$
• if $d' \mid a$ and $d'\mid b$ then $d'\mid d$.

Fact: If $I$ is an ideal in $R$ generated by $a,b$, then $d=(a,b)$ if

• $I\subseteq(d)$
• if $I\subseteq(d')$ then $(d)\subseteq(d')$.

Proposition 2: If $a,b\in R$ such that $a,b \neq 0$ and $(a,b)=(d)$, then $d=(a,b)$.
Proposition 3: Let $R$ be an integral domain. Let $d,d'\in R$ such that $(d)=(d')$. Then, $\exists u\in R$ that is a unit such that $d'=ud$. In particular, if $d,d'$ are both GCDs of $a,b$, then $d'=ud$ for some unit $u$. (GCD is not necessarily unique).
Fact: For any $a,b\in R$ a Euclidean Domain, $(a,b)$ always exists and can be computed algorithmically (Euclidean Algorithm).
Theorem 4: Let $R$ be a Euclidean Domain and $a,b\in R$ such that $a,b \neq 0$. Let $d=r_{n}$ be the last nonzero remainder in the Euclidean Algorithm for $a,b$. Then

• $d\in(a,b)$, the set of GCDs
• $(d)=(a,b)$, i.e. $d$ can be written as an $R$-linear combination of $a,b$, or $\exists x,y\in R$ such that $d=ax+by$. (Bezout's Identity).

Fact: The equation $ax+by=N$ is solvable in integers $x,y$ $\iff$ $(a,b) \mid N$.
Fact: For any integral domain let $\widetilde{R}=R^{\times}\cup \{ 0 \}$ denote the collection of units of $R$ together with $0$. An element $u\in R-\widetilde{R}$ is called a universal side divisor if $\forall x \in R$ then $\exists z\in \widetilde{R}$ such that $u \mid x-z$ in $R$, i.e. there is a type of "division algorithm" for $u$ such that $x=qu+z$ for some $q\in R$. The existence of universal side divisors is a weakening of the Euclidean condition.
Proposition 5: Let $R$ be an integral domain that is not a field. If $R$ is a Euclidean Domain then there are universal side divisors in $R$.

8.2 Principal Ideal Domains (P.I.D.s)

Definition: A Principal Ideal Domain is an integral domain in which every ideal is principal.
Proposition 6: Let $R$ be a PID and let $a,b\in R$ such that $a,b \neq 0$. Let $(d)=(a,b)$. Then

• $d\in(a,b)$.
• $\exists x,y\in R$ such that $d=ax+by$.
• $d$ is unique up to multiplication by $u\in R^{\times}$ (unit).

Proposition 7: Every nonzero prime ideal in a PID is a maximal ideal.
Corollary 8: If $R$ is any commutative ring such that the polynomial ring $R[x]$ is a PID then $R$ is a field.
Definition: $N$ is a Dedekind-Hasse norm if $N$ is a positive norm and $\forall a,b\in R$ such that $a,b \neq 0$ either $a\in(b)$ or $\exists c\in(a,b)$ such that $N(c)<N(b)$. In other words, either $b\mid a\in R$ or $\exists s,t\in R$ with $0<N(sa-tb)<N(b)$.
Proposition 9: The integral domain $R$ is a PID $\iff$ $R$ has a Dedekind-Hasse norm.

8.3 Unique Factorization Domains (U.F.D.s)

Definition: Let $R$ be an integral domain.

• Suppose $r\in R$ is nonzero and not a unit. Then $r$ is irreducible in $R$ if whenever $r=ab$ with $a,b\in R$, at least one of $a,b$ must be a unit in $R$. Otherwise, $r$ is reducible.
• The nonzero element $p \in R$ is prime in $R$ if $(p)$ is a prime ideal. That is, $p\neq 0$ is prime if it is not a unit and, whenever $p\mid ab$ for any $a,b\in R$, then either $p\mid a$ or $p \mid b$.
• Any $a,b\in R$ such that $a=ub$ for some unit $u\in R$, then $a,b$ are considered associate.

Proposition 10: In an integral domain a prime element is always irreducible. The converse is, in general, not true.
Proposition 11: In a PID a nonzero element is a prime $\iff$ it's irreducible.
Definition: A Unique Factorization Domain is an integral domain $R$ in which $\forall r\in R$ with $r \neq 0$ which is not a unit satisfies:

• $r$ can be written as a finite product of not necessarily distinct irreducibles $p_{i}\in R$, i.e. $r=p_{1}\dots p_{n}$.
• the decomposition is unique up to associates, namely, if $r=q_{1}\dots q_{m}$ is another valid factorization into irreducibles, then $m=n$ and there is a bijective map with $p_{i}\mapsto q_{j}$ such that $p_{i}$ is associate with $q_{j}$.

Proposition 12: In a UFD a nonzero element is a prime $\iff$ it is irreducible. (Stronger version of proposition 11).
Proposition 13: Let $a,b\in R$ a UFD with $a,b \neq 0$ and suppose $a=up_{1}^{e_{1}}\dots p_{n}^{e_{n}}$ and $b=vp_{1}^{f_{1}}\dots p_{n}^{f_{n}}$ are prime factorizations where $u,v$ are units, the primes are distinct, and $e_{i},f_{i}\geq0$. Then $d=p_{1}^{\mathrm{min}(e_{1},f_{1})}\dots p_{n}^{\mathrm{min}(e_{n},f_{n})}$ is the gcd.
Theorem 14: $\{ \mathrm{Fields} \}\subset\{ \mathrm{Euclidean\ Domains} \}\subset\{ \mathrm{PID} \}\subset\{ \mathrm{UFD} \}\subset \{ \mathrm{Integral\ Domains} \}$.
Corollary 15: (Fundamental Theorem of Arithmetic) $\mathbb{Z}$ is a UFD.
Corollary 16: Let $R$ be a PID. Then there exists a multiplicative Dedekind-Hasse norm on $R$.
Lemma 17: The prime number $p \in \mathbb{Z}$ divides some $n^{2}+1\in \mathbb{Z}$ $\iff$ $p=2$ or $p$ is a prime $\equiv 1 \; (\text{mod} \; 4 )$.
Proposition 18:

• (Fermat's Theorem on sums of squares) Let $p$ be a prime. $p=a^{2}+b^{2}$ for $a,b\in \mathbb{Z}$ $\iff$ $p=2$ or $p \equiv 1\; (\text{mod} \; 4 )$. The representation is unique up to changing signs or interchanging $a,b$.
• The irreducible elements in the Gaussian integers $\mathbb{Z}[i]$ as follows: (a) $1+i$ (norm $=2$) (b) primes $p \in \mathbb{Z}$ with $p \equiv 3 \; (\text{mod} \; 4 )$ (norm $=p^{2}$).
• $a+bi,a-bi$, i.e. the distinct irreducible factors of $p=a^{2}+b^{2}$, for primes $p \in \mathbb{Z}$ with $p\equiv 1\; (\text{mod} \; 4 )$ (norm $=p$).

Corollary 19: Let $n$ be a positive integer. Then, we can write $n=2^{k}p_{1}^{a_{1}}\dots p_{r}^{a_{r}}q_{1}^{b_{1}}\dots q_{r}^{b_{r}}$ where $p_{1},\dots,p_{r}\equiv 1\; (\text{mod} \; 4 )$ and are distinct primes and $q_{1},\dots,q_{s}\equiv 3\; (\text{mod} \; 4 )$ and are distinct primes. Then $n$ can be written as a sum of two squares in $\mathbb{Z}$ $\iff$ each $b_{i}$ is even. Then, the number of distinct representations of $n$ as a sum of two squares is $4(a_{1}+1)\dots(a_{r}+1)$