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

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updates: 03 March 2011

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 $σ : R ∖ \{0\} \to ℕ .$ Let $R$ be an ideal of $R$ . To show: There exists an element $a \in R$ such that $I = (a)$ . Case $1$ : $I = (0)$ . Case $2$ : $I \neq (0)$ . Let $a \in I, a \neq 0$ such that $σ (a)$ is as small as possible. To show: $I \subseteq (a)$ . $(a) \subseteq I$ . Let $b \in I$ . To show: $b \in (a)$ . Then there exist $q, r \in R$ such that $b = a q + r$ where either $r = 0$ or $σ (r) < σ (a) .$ Since $r = b - a q$ and $b \in I$ , we have $r \in I$ . Since $a \in I$ is such that $σ (a)$ is as small as possible, we cannot have $σ (a) < σ (a) .$ So $r = 0$ . So $b = a q$ . So $b \in (a)$ . So $I \subseteq I$ . To show: $(a) \subseteq I$ . But $a \in I$ . So $(a) \subseteq I$ . So $I = (a)$ . So every ideal $I$ of $R$ is a principal ideal. So $R$ is a principal ideal domain. $□$

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

$p$ is a unit $\Leftrightarrow (p) = R$ .
$p$ divides $q \Leftrightarrow (q) \subseteq (p)$ .
$p$ is a proper divisor of $q \Leftrightarrow (q) ⊊ (p) ⊊ R$ .
$p$ is an associate of $q \Leftrightarrow (q) = (p)$ .
p is irreducible ⇔
- $(p) \neq 0$ ,
- $(p) \neq R$ ,
- If $q \in R$ and $(q) \supseteq (p)$ then either $(q) = (p)$ or $(q) = R$ .

		Proof.
	$\Rightarrow$ Assume $p$ is a unit. Let $u \in R$ such that $u p = 1 .$ Then $1 = u p \in (p)$ . So, if $r \in R$ then $r \cdot 1 \in (p) .$ So $R \subseteq (p) \subseteq R$ . So $(p) = R .$ $\Leftarrow$ Assume $(p) = R$ . Then $1 \in (p)$ . So $p u = 1$ for some $u \in R$ . So $p$ is a unit. $\Rightarrow$ Assume $p$ divides $q$ . So $p a = q$ for some $a \in R$ . So $q \in (p)$ . So $(q) \subseteq (p) .$ $\Leftarrow$ Assume $(q) \subseteq (p)$ . Then $q \in (p)$ . So $q = a p$ for some $a \in R$ . So $p$ divides $q$ . $\Rightarrow$ Assume $p$ is a proper divisor of $q$ . Let $a \in R$ such that $q = a p$ and such that $a$ is not a unit. To show: $(q) \subseteq (p)$ . $(q) \neq (p)$ . $(p) \neq R$ . Since $q = p a$ , $q \in (p)$ . So $(q) \subseteq (p)$ . Proof by contradiction. Assume $(q) = (p)$ . Then $p = b q$ for some $b \in R$ . So $q = p a = b a q$ . Thus, since $R$ is an integral domain, the cancellation law gives that $a b = 1$ . So $a$ is a unit. Contradiction, $a$ is not a unit. So $(q) \neq (p) .$ By part a), since $p$ is not a unit $(p) \neq R$ . $\Rightarrow$ Assume $p$ is an associate of $q$ . To show: $(p) \subseteq (q) .$ $(q) \subseteq (p) .$ Then $p = a q$ for some unit $a \in R$ . So $p \in (q)$ . So $(p) \subseteq (q)$ . Since $p = a q$ and $a$ is a unit, $q = a^{- 1} p$ . So $q \in (p)$ . So $(q) \subseteq (p)$ . So $(q) = (p) .$ $\Leftarrow$ Assume $(q) = (p) .$ To show $p = a q$ for some $a \in R$ . $a$ is a unit. Since $(p) \subseteq (q),$ $p \in (q)$ . So $p = a q$ for some $a \in R$ . Since $(q) \subset (p),$ $q \in (p)$ . So $q = b p$ for some $b \in R$ . So $p = a q = a b p$ . Then, by the cancellation law, $1 = a b$ . So $a$ is a unit. $\Rightarrow$ Assume $p$ is irreducible. To show: $(p) \neq (0) .$ $(p) \neq R .$ If $q \in R$ and $(q) \supseteq (p)$ then either $(q) = (p)$ or $(q) = R .$ Since $p \neq 0$ , $(p) \neq (0) .$ Since $p$ is not a unit, by part a), $(p) \neq R .$ Assume $q \in R$ and $(q) \supseteq (p) .$ Proof by contradiction. Assume $(q) \neq (p)$ and $(q) \neq R .$ Then $R ⊋ (q) ⊋ (p) .$ So, by part c), $q$ is a proper divisor of $p$ . This is a contradiction to $p$ being irreducible. So either $(q) = (p)$ or $(q) = R .$ $\Leftarrow$ Assume $(p) \neq 0,$ $(p) \neq R$ and if $q \in R$ and $(q) \supseteq (p)$ then either $(q) = (p)$ or $(q) = R$ To show: $p \neq 0 .$ $p$ is not a unit. $p$ has no proper divisor. Since $(p) \neq (0)$ , $p \neq 0$ . Since $p \neq 0$ , $p \neq 0$ . Since $(p) \neq R$ , by part a), $p$ is not a unit. Assumme $p$ has a proper divisor $q \in R$ . Then, by part c) $(p) ⊊ (q) ⊊ R .$ But this is a contradiction to the assumption that if $q \in R$ and $(q) \supseteq (p)$ then either $(q) = (p)$ or $(q) = R$ . So $p$ has no proper divisor. $□$

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

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

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) ⊊ (a_{1}) ⊊ (a_{2}) ⊊ \dots$

		Proof.
	Proof by contradiction. Suppose $a_{1}, a_{2}, \dots \in R$ is an infinite sequence of elements such that $(0) ⊊ (a_{1}) ⊊ (a_{2}) \dots$ We first show that $I = ⋃_{i \geq 1} (a_{i})$ is an ideal. To show: If $a \in I$ and $r \in R$ then $r a \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 (a_{n})$ for some $n \geq 1$ . So $r a \in (a_{n})$ . So $r a \in I$ . Let $a_{1}, a_{2} \in I$ . Then $a_{1} \in (a_{m})$ and $a_{2} \in (a_{n})$ for some $m, n \geq 1 .$ Then $a_{1}, a_{2} \in (a_{m + n})$ since $(a_{m}) \subseteq (a_{m + n})$ and $(a_{n}) \subseteq (a_{m + n})$ . So $a_{1} + a_{2} \in (a_{m + n}) .$ So $I$ is an ideal. Since $R$ is a principal ideal domain, there exists $a \in R$ such that $I = (a)$ . Since $a \in I$ , $a \in (a_{n})$ for some $n \geq 1$ . So $I = (a) \subseteq (a_{n}) \subseteq (a_{n + 1}) \subseteq I .$ So $(a_{n}) = (a_{n + 1})$ . But this is a contradiction to the assumption that $(a_{n}) ⊊ (a_{n + 1}) .$ So $R$ does not contain an infinite sequence of elements $a_{1}, a_{2} \dots$ such that such that $(0) ⊊ (a_{1}) ⊊ (a_{2}) ⊊ \dots .$ $□$

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} \dots p_{m}$ for some irreducible elements $p_{1}, \dots, p_{m} \in R$ If $x \in R$ and $x = p_{1} \dots p_{m}$ and $x = u q_{1} \dots 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 $σ : \{1, 2, \dots, m\} \to \{1, 2, \dots, m\}$ such that, for each $i$ , $q_{i} = u_{i} p_{σ_{(i)}}$ for some unit $u_{i} \in R$ . Proof by contradiction. Suppose $x \in R$ and $x$ cannot be written as $x = p_{1} \dots 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), $(0) ⊊ (a_{1}) ⊊ (a_{2}) \dots .$ But this is a contradiction to Lemma 1.4. So $x$ can be written as $x = p_{1} \dots p_{m}$ where all $p_{1}, \dots, p_{m}$ are irreducible. Suppose $x \in R$ and $x = p_{1} \dots p_{m} = u q_{1} \dots 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 $σ : \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$ such that $q_{i} = u_{i} p_{σ (i)}$ 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} \dots p_{m} = u q_{1} \dots 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), $(q_{1} \dots q_{m}) = (u q_{1} \dots q_{m}) = (p_{1}) .$ Since $p_{1}$ is irreducible, by Lemma 1.3 $p_{1}$ is a prime ideal. So $q_{j} \in (p_{1})$ for some $1 \leq j \leq n$ . So $(q_{j}) \subseteq (p_{1}) .$ Since $q_{j}$ is irreducible, $(q_{j}) = (p_{1}) .$ So $q_{j} = u_{1} p_{1}$ for some unit $u_{1} \in R$ . So $q_{1} \dots q_{j - 1} u_{1} p_{1} q_{j + 1} \dots q_{m} = p_{1} .$ By the cancellation law, $u_{1} q_{1} \dots 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 < n$ and $y = a_{1} a_{2} \dots a_{k} = u' b_{1} \dots b_{l}$ where $u'$ 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 $σ' : \{1, \dots, k\} \to \{1, \dots, k\}$ such that, for each $i$ , $b_{i} = u_{i} a_{σ' (i)}$ for some unit $u_{i} \in R$ . Assume that $x = p_{1} \dots p_{n} = q_{1} \dots 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} \dots p_{m} = u q_{1} \dots q_{n} .$ So $(u q_{1} \dots q_{m}) = (q_{1} \dots q_{m}) \subseteq (p_{n}) .$ So $q_{1} \dots q_{n} \in (p_{n}) .$ By Lemma 1.3 $(p_{n})$ is a prime ideal. So $q_{j} \in (p_{n})$ for some $j$ . So $(q_{j}) \subseteq (p_{n}) .$ So $(q_{j}) = (p_{n})$ 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} \dots p_{n} = u q_{1} \dots q_{j - 1} (u_{n} p_{n}) q_{j + 1} \dots q_{m} .$ By cancellation, $p_{1} \dots p_{n - 1} = (u u_{n}) q_{1} \dots q_{j - 1} q_{j + 1} \dots q_{m} .$ By the incuction hypothesis, $m - 1 = n - 1$ and there exists a bijective map $σ' : \{1, \dots, j - 1\} \cup \{j + 1, \dots, n\} \to \{1, 2, \dots, n - 1\}$ such that $u_{i} p_{σ' (i)} = q_{i}$ , where $u_{i}$ is a unit. So $m = n$ . Define $σ : \{1, \dots, n\} \to \{1, \dots, n\}$ by $σ (i) = \{\begin{cases} σ' (i), & if i \neq j, \\ n, & if i = j . \end{cases}$ Then $q_{i} = u_{i} p_{σ (i)}$ for each $1 \leq i \leq n$ . So $R$ is a unique factorization domain. $□$

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

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

		Proof.
	Let $P = \{p_{1}, p_{2}, \dots, p_{k}\}$ be a maximal set of irreducible elements such that Every $p_{j} \in P$ divides some $a_{i}$ , $0 \leq i \leq n$ . No two elements of $P$ are associate. Let $a_{i} = q_{1} \dots q_{m}$ be a factorization of $a i$ into irreducible elements. Each factor $q_{r}$ , $1 \leq r \leq m$ , is associate to some $p_{j} \in P$ . So $\begin{array}{rcl} a_{i} & = & u_{1} p_{j_{1}} u_{2} p_{j_{2}} \dots u_{r} p_{j_{r}} \\ = & u p_{1}^{e_{i 1}} p_{2}^{e_{i 2}} \dots p_{k}^{e_{i k}} \end{array}$ where $u \in R$ is a unit and $e_{i j}$ are integers $e_{i j} \geq 0$ . Let $e_{j} = {min}_{i} \{e_{i j}\} .$ Define $d = p_{1}^{e_{i 1}} p_{2}^{e_{i 2}} \dots p_{k}^{e_{i k}}$ . To show: $d$ divides $a_{i}$ for all $1 \leq i \leq n$ . If $d'$ divides $a_{i}$ for all $1 \leq i \leq n$ then $d'$ divides $d$ . Let $i$ be such that $1 \leq i \leq n$ . Since $e_{j} \leq e_{i j}$ for all $1 \leq j \leq k$ , $d = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}} divides a_{i} = u p_{1}^{e_{i 1}} p_{2}^{e_{i 2}} \dots p_{k}^{e_{i k}} .$ So $d$ divides $a_{i}$ for all $1 \leq i \leq n$ . Assume $d'$ divides $a_{i}$ for all $1 \leq i \leq n$ . Let $d' = q_{1} \dots q_{m}$ be a factorization of $d'$ into irreducible elements. Since $d'$ divides $a_{i}$ for all $1 \leq i \leq n$ , each factor $q_{r}$ of $d'$ divides $a_{i}$ for all $1 \leq i \leq n$ . So each $q_{r}$ is associate to some $p_{j_{r}}$ , otherwise $P' = P \cup \{q_{r}\}$ is a larger set satisfying 1) and 2). So, for each factor $q_{r}$ of $d'$ , $q_{r} = u_{r} p_{j_{r}}$ for some unit $u_{r} \in R$ and some $p_{j_{r}} \in P$ . So $d' = u_{1} p_{j_{1}} u_{2} p_{j_{2}} \dots u_{k} p_{j_{k}} = u p_{1}^{f_{1}} p_{2}^{f_{2}} \dots p_{k}^{f_{k}},$ where $u \in R$ is a unit and the $f_{j}$ are integers $f_{j} \geq 0$ . Since $d'$ divides $a_{i}$ for all $1 \leq i \leq n$ , then for each $f_{j}$ , $f_{j} \leq e_{i j} for all 1 \leq i \leq n .$ So, for each $f_{j}$ , $f_{j} \leq {min}_{i} \{e_{i j}\}$ . So, for each $f_{j}$ , $f_{j} \leq e_{j}$ . So $d' = 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'$ are both greatest common divisors of $a_{0}, a_{1}, \dots, a_{n}$ . Then $d$ divides $d'$ and $d'$ divides $d$ . So $d = a d'$ for some $a \in R$ and $d' = b d$ for some $b \in R$ . So $d = a b d$ . By the cancellation law, $a b = 1$ . So $a, b$ are units in $R$ . $□$

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)

page history