Logo

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

8.1 Euclidean Domains

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

Fact: If II is an ideal in RR generated by a,ba,b, then d=(a,b)d=(a,b) if

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

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

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 RR be a PID and let a,b∈Ra,b\in R such that a,b≠0a,b \neq 0. Let (d)=(a,b)(d)=(a,b). Then

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

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

Definition: Let RR be an integral domain.

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 RR in which ∀r∈R\forall r\in R with r≠0r \neq 0 which is not a unit satisfies:

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∈Ra,b\in R a UFD with a,b≠0a,b \neq 0 and suppose a=up1e1…pnena=up_{1}^{e_{1}}\dots p_{n}^{e_{n}} and b=vp1f1…pnfnb=vp_{1}^{f_{1}}\dots p_{n}^{f_{n}} are prime factorizations where u,vu,v are units, the primes are distinct, and ei,fi≥0e_{i},f_{i}\geq0. Then d=p1min(e1,f1)…pnmin(en,fn)d=p_{1}^{\mathrm{min}(e_{1},f_{1})}\dots p_{n}^{\mathrm{min}(e_{n},f_{n})} is the gcd.
Theorem 14: {Fields}⊂{Euclidean Domains}⊂{PID}⊂{UFD}⊂{Integral Domains}\{ \mathrm{Fields} \}\subset\{ \mathrm{Euclidean\ Domains} \}\subset\{ \mathrm{PID} \}\subset\{ \mathrm{UFD} \}\subset \{ \mathrm{Integral\ Domains} \}.
Corollary 15: (Fundamental Theorem of Arithmetic) Z\mathbb{Z} is a UFD.
Corollary 16: Let RR be a PID. Then there exists a multiplicative Dedekind-Hasse norm on RR.
Lemma 17: The prime number p∈Zp \in \mathbb{Z} divides some n2+1∈Zn^{2}+1\in \mathbb{Z}   ⟺  \iff p=2p=2 or pp is a prime ≡1  (mod  4)\equiv 1 \; (\text{mod} \; 4 ).
Proposition 18:

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