§2P. Euclidean Domains, Principal Ideal Domains, and Unique Factorization Domains

## Euclidean domains, principal ideal domains, and unique factorization domains

A Euclidean domain is a principal ideal domain.

 Proof. Assume $R$ is a Euclidean domain with size function $\sigma :R\setminus \left\{0\right\}\to ℕ.$ Let $R$ be an ideal of $R$. To show: There exists an element $a\in R$ such that $I=\left(a\right)$. Case $1$: $I=\left(0\right)$. Case $2$: $I\ne \left(0\right)$. Let $a\in I,a\ne 0$ such that $\sigma \left(a\right)$ is as small as possible. To show: $I\subseteq \left(a\right)$. $\left(a\right)\subseteq I$. Let $b\in I$. To show: $b\in \left(a\right)$. Then there exist $q,r\in R$ such that $b=aq+r$ where either $r=0$ or $\sigma \left(r\right)<\sigma \left(a\right).$ Since $r=b-aq$ and $b\in I$, we have $r\in I$. Since $a\in I$ is such that $\sigma \left(a\right)$ is as small as possible, we cannot have $\sigma \left(a\right)<\sigma \left(a\right).$ So $r=0$. So $b=aq$. So $b\in \left(a\right)$. So $I\subseteq I$. To show: $\left(a\right)\subseteq I$. But $a\in I$. So $\left(a\right)\subseteq I$. So $I=\left(a\right)$. So every ideal $I$ of $R$ is a principal ideal. So $R$ is a principal ideal domain. $\square$

Let $p,q\in R$ and $\left(p\right)$ and $\left(q\right)$ denote the ideals generated by the elements $p$ and $q$ respectively. Then

1. $p$ is a unit $⇔\left(p\right)=R$.
2. $p$ divides $q⇔\left(q\right)\subseteq \left(p\right)$.
3. $p$ is a proper divisor of $q⇔\left(q\right)⊊\left(p\right)⊊R$.
4. $p$ is an associate of $q⇔\left(q\right)=\left(p\right)$.
5. $p$ is irreducible $⇔$
• $\left(p\right)\ne 0$,
• $\left(p\right)\ne R$,
• If $q\in R$ and $\left(q\right)\supseteq \left(p\right)$ then either $\left(q\right)=\left(p\right)$ or $\left(q\right)=R$.

 Proof. $⇒$ Assume $p$ is a unit. Let $u\in R$ such that $up=1.$ Then $1=up\in \left(p\right)$. So, if $r\in R$ then $r\cdot 1\in \left(p\right).$ So $R\subseteq \left(p\right)\subseteq R$. So $\left(p\right)=R.$ $⇐$ Assume $\left(p\right)=R$. Then $1\in \left(p\right)$. So $pu=1$ for some $u\in R$. So $p$ is a unit. $⇒$ Assume $p$ divides $q$. So $pa=q$ for some $a\in R$. So $q\in \left(p\right)$. So $\left(q\right)\subseteq \left(p\right).$ $⇐$ Assume $\left(q\right)\subseteq \left(p\right)$. Then $q\in \left(p\right)$. So $q=ap$ for some $a\in R$. So $p$ divides $q$. $⇒$ Assume $p$ is a proper divisor of $q$. Let $a\in R$ such that $q=ap$ and such that $a$ is not a unit. To show: $\left(q\right)\subseteq \left(p\right)$. $\left(q\right)\ne \left(p\right)$. $\left(p\right)\ne R$. Since $q=pa$, $q\in \left(p\right)$. So $\left(q\right)\subseteq \left(p\right)$. Proof by contradiction. Assume $\left(q\right)=\left(p\right)$. Then $p=bq$ for some $b\in R$. So $q=pa=baq$. Thus, since $R$ is an integral domain, the cancellation law gives that $ab=1$. So $a$ is a unit. Contradiction, $a$ is not a unit. So $\left(q\right)\ne \left(p\right).$ By part a), since $p$ is not a unit $\left(p\right)\ne R$. $⇒$ Assume $p$ is an associate of $q$. To show: $\left(p\right)\subseteq \left(q\right).$ $\left(q\right)\subseteq \left(p\right).$ Then $p=aq$ for some unit $a\in R$. So $p\in \left(q\right)$. So $\left(p\right)\subseteq \left(q\right)$. Since $p=aq$ and $a$ is a unit, $q={a}^{-1}p$. So $q\in \left(p\right)$. So $\left(q\right)\subseteq \left(p\right)$. So $\left(q\right)=\left(p\right).$ $⇐$ Assume $\left(q\right)=\left(p\right).$ To show $p=aq$ for some $a\in R$. $a$ is a unit. Since $\left(p\right)\subseteq \left(q\right),$ $p\in \left(q\right)$. So $p=aq$ for some $a\in R$. Since $\left(q\right)\subset \left(p\right),$ $q\in \left(p\right)$. So $q=bp$ for some $b\in R$. So $p=aq=abp$. Then, by the cancellation law, $1=ab$. So $a$ is a unit. $⇒$ Assume $p$ is irreducible. To show: $\left(p\right)\ne \left(0\right).$ $\left(p\right)\ne R.$ If $q\in R$ and $\left(q\right)\supseteq \left(p\right)$ then either $\left(q\right)=\left(p\right)$ or $\left(q\right)=R.$ Since $p\ne 0$, $\left(p\right)\ne \left(0\right).$ Since $p$ is not a unit, by part a), $\left(p\right)\ne R.$ Assume $q\in R$ and $\left(q\right)\supseteq \left(p\right).$ Proof by contradiction. Assume $\left(q\right)\ne \left(p\right)$ and $\left(q\right)\ne R.$ Then $R⊋\left(q\right)⊋\left(p\right).$ So, by part c), $q$ is a proper divisor of $p$. This is a contradiction to $p$ being irreducible. So either $\left(q\right)=\left(p\right)$ or $\left(q\right)=R.$ $⇐$ Assume $\left(p\right)\ne 0,$ $\left(p\right)\ne R$ and if $q\in R$ and $\left(q\right)\supseteq \left(p\right)$ then either $\left(q\right)=\left(p\right)$ or $\left(q\right)=R$ To show: $p\ne 0.$ $p$ is not a unit. $p$ has no proper divisor. Since $\left(p\right)\ne \left(0\right)$, $p\ne 0$. Since $p\ne 0$, $p\ne 0$. Since $\left(p\right)\ne R$, by part a), $p$ is not a unit. Assumme $p$ has a proper divisor $q\in R$. Then, by part c) $\left(p\right)⊊\left(q\right)⊊R.$ But this is a contradiction to the assumption that if $q\in R$ and $\left(q\right)\supseteq \left(p\right)$ then either $\left(q\right)=\left(p\right)$ or $\left(q\right)=R$. So $p$ has no proper divisor. $\square$

If $R$ is a principal domain and $p\in R$ is an irreducible element of $R$ then $\left(p\right)$ is a prime ideal.

 Proof. Let $p\in R$ be an irreducible element. Let $a,b\in R$ and suppose $ab\in \left(p\right)$. To show: If $a\notin \left(p\right)$ then $b\in \left(p\right).$ Assume $a\notin \left(p\right).$ Then let $d\in R$ such that $\left(d\right)=\left(a,p\right)$. Since $p\in \left(a,p\right)$, $\left(p\right)\subseteq \left(a,p\right)=d.$ Since $a\notin \left(p\right)$, $\left(d\right)=\left(a,p\right)\ne \left(p\right).$ Thus, since $p$ is irreducible, $\left(a,p\right)=\left(d\right)=\left(1\right)=R.$ So there exist $r,s\in R$ such that $ra+sp=1.$ So $b=rab+spb.$ Thus, since $ab\in \left(p\right)$ and $pb\in \left(p\right)$, it follows that $b\in \left(p\right)$. So $\left(p\right)$ is a prime ideal. $\square$

Let $R$ be a principal ideal domain. There does not exist an infinite sequence of elements ${a}_{1},{a}_{2},\dots \in R$ such that $0⊊ a1⊊ a2⊊⋯$

 Proof. Proof by contradiction. Suppose ${a}_{1},{a}_{2},\dots \in R$ is an infinite sequence of elements such that $\left(0\right)⊊\left({a}_{1}\right)⊊\left({a}_{2}\right)\cdots$ We first show that $I= ⋃ i≥1 ai$ is an ideal. To show: If $a\in I$ and $r\in R$ then $ra\in I$. If ${a}_{1},{a}_{2}\in I$ then ${a}_{1}+{a}_{2}\in I$. Let $a\in I$ and $r\in R$. Then $a\in \left({a}_{n}\right)$ for some $n\ge 1$. So $ra\in \left({a}_{n}\right)$. So $ra\in I$. Let ${a}_{1},{a}_{2}\in I$. Then ${a}_{1}\in \left({a}_{m}\right)$ and ${a}_{2}\in \left({a}_{n}\right)$ for some $m,n\ge 1.$ Then ${a}_{1},{a}_{2}\in \left({a}_{m+n}\right)$ since $\left({a}_{m}\right)\subseteq \left({a}_{m+n}\right)$ and $\left({a}_{n}\right)\subseteq \left({a}_{m+n}\right)$. So ${a}_{1}+{a}_{2}\in \left({a}_{m+n}\right).$ So $I$ is an ideal. Since $R$ is a principal ideal domain, there exists $a\in R$ such that $I=\left(a\right)$. Since $a\in I$, $a\in \left({a}_{n}\right)$ for some $n\ge 1$. So $I=\left(a\right)\subseteq \left({a}_{n}\right)\subseteq \left({a}_{n+1}\right)\subseteq I.$ So $\left({a}_{n}\right)=\left({a}_{n+1}\right)$. But this is a contradiction to the assumption that $\left({a}_{n}\right)⊊\left({a}_{n+1}\right).$ So $R$ does not contain an infinite sequence of elements ${a}_{1},{a}_{2}\cdots$ such that such that $\left(0\right)⊊\left({a}_{1}\right)⊊\left({a}_{2}\right)⊊\cdots .$ $\square$

A principal ideal domain is a unique factorization domain.

 Proof. Let $R$ be a principal ideal domain. To show: If $x\in R$ then $x={p}_{1}\cdots {p}_{m}$ for some irreducible elements ${p}_{1},\dots ,{p}_{m}\in R$ If $x\in R$ and $x={p}_{1}\cdots {p}_{m}$ and $x=u{q}_{1}\cdots {q}_{n}$ where ${p}_{1},\dots ,{p}_{m},{q}_{1},\dots ,{q}_{n}$ are irreducible and $u$ is a unit then $m=n$ and there is a permutation $\sigma :\left\{1,2,\dots ,m\right\}\to \left\{1,2,\dots ,m\right\}$ such that, for each $i$, ${q}_{i}={u}_{i}{p}_{{\sigma }_{\left(i\right)}}$ for some unit ${u}_{i}\in R$. Proof by contradiction. Suppose $x\in R$ and $x$ cannot be written as $x={p}_{1}\cdots {p}_{m}$ where all ${p}_{1},\dots ,{p}_{m}$ are irreducible. Then $x=x$ is not irreducible. So $x={a}_{1}{b}_{1}$ for some ${b}_{1}\in R$ and some ${a}_{1}$ which is not irreducible and which is a proper divisor of $x$ in $R$. So $x={a}_{2}{b}_{2}{b}_{1}$ where ${a}_{1}={a}_{2}{b}_{2}$ for some ${b}_{2}\in R$ and some ${a}_{2}$ which is not irreducible and which is a proper divisor of ${a}_{1}$. We can continue this process and obtain a sequence of elements ${a}_{1},{a}_{2},\dots \in R$ such that ${a}_{i+1}$ is a proper divisor of ${a}_{i}$. So, by Proposition 1.2 c), $\left(0\right)⊊\left({a}_{1}\right)⊊\left({a}_{2}\right)\cdots .$ But this is a contradiction to Lemma 1.4. So $x$ can be written as $x={p}_{1}\cdots {p}_{m}$ where all ${p}_{1},\dots ,{p}_{m}$ are irreducible. Suppose $x\in R$ and $x={p}_{1}\cdots {p}_{m}=u{q}_{1}\cdots {q}_{m}$ where $u$ is a unit and ${p}_{1},\dots ,{p}_{n},{q}_{1},\dots ,{q}_{m}\in R$ are irreducible. To show: $m=n$ and there is a bijective map $\sigma :\left\{1,2,\dots ,n\right\}\to \left\{1,2,\dots ,n\right\}$ such that ${q}_{i}={u}_{i}{p}_{\sigma \left(i\right)}$ for some unit ${u}_{i}\in R$. The proof is by induction on $n$. Case $n=1$. Suppose $x\in R$ and $x={p}_{1}\cdots {p}_{m}=u{q}_{1}\cdots {q}_{m}$ where $u$ is a unit and ${p}_{1},\dots ,{p}_{n},{q}_{1},\dots ,{q}_{m}\in R$ are irreducible. Suppose $m>1$. Then using Proposition 1.2 d), $\left({q}_{1}\cdots {q}_{m}\right)=\left(u{q}_{1}\cdots {q}_{m}\right)=\left({p}_{1}\right).$ Since ${p}_{1}$ is irreducible, by Lemma 1.3 ${p}_{1}$ is a prime ideal. So ${q}_{j}\in \left({p}_{1}\right)$ for some $1\le j\le n$. So $\left({q}_{j}\right)\subseteq \left({p}_{1}\right).$ Since ${q}_{j}$ is irreducible, $\left({q}_{j}\right)=\left({p}_{1}\right).$ So ${q}_{j}={u}_{1}{p}_{1}$ for some unit ${u}_{1}\in R$. So ${q}_{1}\cdots {q}_{j-1}{u}_{1}{p}_{1}{q}_{j+1}\cdots {q}_{m}={p}_{1}.$ By the cancellation law, ${u}_{1}{q}_{1}\cdots {q}_{j-1}{q}_{j+1}=1.$ So ${q}_{1}$ is a unit. This is a contradiction to q1 being irreducible. So $m=1$. So $x={p}_{1}=u{q}_{1}$ where $u\in R$ is a unit. Induction assumption: Assume that if $k and $y={a}_{1}{a}_{2}\cdots {a}_{k}=u\text{'}{b}_{1}\cdots {b}_{l}$ where $u\text{'}$ is a unit and ${a}_{1},\dots ,{a}_{k},{b}_{1},\dots ,{b}_{l}\in R$ are irreducible then $k=l$ and there is a bijective map $\sigma \text{'}:\left\{1,\dots ,k\right\}\to \left\{1,\dots ,k\right\}$ such that, for each $i$, ${b}_{i}={u}_{i}{a}_{\sigma \text{'}\left(i\right)}$ for some unit ${u}_{i}\in R$. Assume that $x={p}_{1}\cdots {p}_{n}={q}_{1}\cdots {q}_{m}$ where $u\in R$ is a unit and ${p}_{1},\dots ,{p}_{n},{q}_{1},\dots ,{q}_{m}\in R$ are irreducible all irreducible. We know ${p}_{1}\cdots {p}_{m}=u{q}_{1}\cdots {q}_{n}.$ So $\left(u{q}_{1}\cdots {q}_{m}\right)=\left({q}_{1}\cdots {q}_{m}\right)\subseteq \left({p}_{n}\right).$ So ${q}_{1}\cdots {q}_{n}\in \left({p}_{n}\right).$ By Lemma 1.3 $\left({p}_{n}\right)$ is a prime ideal. So ${q}_{j}\in \left({p}_{n}\right)$ for some $j$. So $\left({q}_{j}\right)\subseteq \left({p}_{n}\right).$ So $\left({q}_{j}\right)=\left({p}_{n}\right)$ since ${q}_{j}$ is irreducible. So ${q}_{j}$ and ${p}_{n}$ are associates. So ${u}_{n}{p}_{n}={q}_{j}$ for some unit ${u}_{n}\in R$. Then ${p}_{1}\cdots {p}_{n}=u{q}_{1}\cdots {q}_{j-1}\left({u}_{n}{p}_{n}\right){q}_{j+1}\cdots {q}_{m}.$ By cancellation, ${p}_{1}\cdots {p}_{n-1}=\left(u{u}_{n}\right){q}_{1}\cdots {q}_{j-1}{q}_{j+1}\cdots {q}_{m}.$ By the incuction hypothesis, $m-1=n-1$ and there exists a bijective map $σ': 1,…,j-1 ∪ j+1,…,n → 1,2,…,n-1$ such that ${u}_{i}{p}_{\sigma \text{'}\left(i\right)}={q}_{i}$, where ${u}_{i}$ is a unit. So $m=n$. Define $\sigma :\left\{1,\dots ,n\right\}\to \left\{1,\dots ,n\right\}$ by Then ${q}_{i}={u}_{i}{p}_{\sigma \left(i\right)}$ for each $1\le i\le n$. So $R$ is a unique factorization domain. $\square$

Let $R$ be a unique factorization domain and let ${a}_{0},{a}_{1},\dots ,{a}_{n}\in R.$ Then

1. $gcd\left({a}_{0},{a}_{1},\dots ,{a}_{n}\right)$ exists.
2. $gcd\left({a}_{0},{a}_{1},\dots ,{a}_{n}\right)$ is unique up to multiplication by a unit.

 Proof. Let $P=\left\{{p}_{1},{p}_{2},\dots ,{p}_{k}\right\}$ be a maximal set of irreducible elements such that Every ${p}_{j}\in P$ divides some ${a}_{i}$, $0\le i\le n$. No two elements of $P$ are associate. Let ${a}_{i}={q}_{1}\dots {q}_{m}$ be a factorization of $ai$ into irreducible elements. Each factor ${q}_{r}$, $1\le r\le m$, is associate to some ${p}_{j}\in P$. So $ai = u1pj1 u2pj2… urpjr = u p1ei1 p2ei2 … pkeik$ where $u\in R$ is a unit and ${e}_{ij}$ are integers ${e}_{ij}\ge 0$. Let ${e}_{j}={min}_{i}\left\{{e}_{ij}\right\}.$ Define $d={p}_{1}^{{e}_{i1}}{p}_{2}^{{e}_{i2}}\dots {p}_{k}^{{e}_{ik}}$. To show: $d$ divides ${a}_{i}$ for all $1\le i\le n$. If $d\text{'}$ divides ${a}_{i}$ for all $1\le i\le n$ then $d\text{'}$ divides $d$. Let $i$ be such that $1\le i\le n$. Since ${e}_{j}\le {e}_{ij}$ for all $1\le j\le k$, $d= p1e1 p2e2 … pkek divides ai=u p1ei1 p2ei2 … pkeik .$ So $d$ divides ${a}_{i}$ for all $1\le i\le n$. Assume $d\text{'}$ divides ${a}_{i}$ for all $1\le i\le n$. Let $d\text{'}={q}_{1}\dots {q}_{m}$ be a factorization of $d\text{'}$ into irreducible elements. Since $d\text{'}$ divides ${a}_{i}$ for all $1\le i\le n$, each factor ${q}_{r}$ of $d\text{'}$ divides ${a}_{i}$ for all $1\le i\le n$. So each ${q}_{r}$ is associate to some ${p}_{{j}_{r}}$, otherwise $P\text{'}=P\cup \left\{{q}_{r}\right\}$ is a larger set satisfying 1) and 2). So, for each factor ${q}_{r}$ of $d\text{'}$, ${q}_{r}={u}_{r}{p}_{{j}_{r}}$ for some unit ${u}_{r}\in R$ and some ${p}_{{j}_{r}}\in P$. So $d'= u1 pj1 u2 pj2… uk pjk= u p1f1 p2f2 … pkfk ,$ where $u\in R$ is a unit and the ${f}_{j}$ are integers ${f}_{j}\ge 0$. Since $d\text{'}$ divides ${a}_{i}$ for all $1\le i\le n$, then for each ${f}_{j}$, $fj≤ eij for all 1≤i≤n .$ So, for each ${f}_{j}$, ${f}_{j}\le {min}_{i}\left\{{e}_{ij}\right\}$. So, for each ${f}_{j}$, ${f}_{j}\le {e}_{j}$. So $d\text{'}=u{p}_{1}^{{f}_{1}}{p}_{2}^{{f}_{2}}\dots {p}_{k}^{{f}_{k}}$ divides $d={p}_{1}^{{e}_{1}}{p}_{2}^{{e}_{2}}\dots {p}_{k}^{{e}_{k}}$. So $d$ is a greatest common divisor of ${a}_{0},{a}_{1},\dots ,{a}_{n}$. Assume $d$ and $d\text{'}$ are both greatest common divisors of ${a}_{0},{a}_{1},\dots ,{a}_{n}$. Then $d$ divides $d\text{'}$ and $d\text{'}$ divides $d$. So $d=ad\text{'}$ for some $a\in R$ and $d\text{'}=bd$ for some $b\in R$. So $d=abd$. By the cancellation law, $ab=1$. So $a,b$ are units in $R$. $\square$

## References

[CM] H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, Fourth edition. Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], 14. Springer-Verlag, Berlin-New York, 1980. MR0562913 (81a:20001)

[GW1] F. Goodman and H. Wenzl, The Temperly-Lieb algebra at roots of unity, Pacific J. Math. 161 (1993), 307-334. MR1242201 (95c:16020)