---
tag: 6Q9XRQBDPP
kind: proof
name: Proof that every principal ideal domain is a unique factorisation domain
msc: [13F15]
proves: 055HT85T3S
uses: [0RZYDVZ475, 06YMXJMXYS, 052SDEPZH7, 0MNHXBSX3M, 053E86NWVK, 019NFGFPR5, 0MYSA6MYNA, 030TZ0DQWT, 095ZHQ7WCJ, 05WAF5T0GZ, 06HC6HK0Z8, 0GJM24EXP9]
sources:
  - url: https://dummit.cos.northeastern.edu/docs/ringthy_4_arithmetic_and_factorization_in_domains.pdf
  - url: https://proofwiki.org/wiki/Principal_Ideal_Domain_is_Unique_Factorization_Domain
---

## Proof

Let $R$ be a [[principal ideal domain|0RZYDVZ475]]. A factorisation of $a$ means $a = p_1 \cdots p_n$ with $n \ge 1$ and all $p_i$ [[irreducible|052SDEPZH7]].

First we show that factorisations exist.

1. For $b \in R$, the set $b R = \set{b t : t \in R}$ is an ideal that contains $b$. Every ideal containing $b$ contains $b R$. So the [[ideal generated by|030TZ0DQWT]] $b$ is $(b) = b R$.
2. Let $a = b c$ with $a \neq 0$ and $c$ not a [[unit|019NFGFPR5]]. Then $(a) \subseteq (b)$. If $(b) \subseteq (a)$, then $b = a t$ for some $t$, so $a = a t c$.
3. In that case [[cancellation|0GJM24EXP9]] gives $t c = 1$, and $c$ is a unit, which is false. So $(a) \subsetneq (b)$.
4. Let $(a_0) \subsetneq (a_1) \subsetneq (a_2) \subsetneq \cdots$ be an infinite chain of principal ideals. Let $J$ be the union of the ideals $(a_n)$.
5. If $x \in (a_i)$ and $y \in (a_j)$, then both lie in $(a_k)$ with $k = \max(i, j)$. So $x - y \in J$ and $r x \in J$ for $r \in R$. Thus $J$ is an [[ideal|0MYSA6MYNA]].
6. Since $R$ is a principal ideal domain, $J = (d)$ for some $d$. Then $d \in (a_N)$ for some $N$, so $(a_{N+1}) \subseteq J = (d) \subseteq (a_N)$.
7. This contradicts $(a_N) \subsetneq (a_{N+1})$. So $R$ has no infinite strictly increasing chain of principal ideals.
8. Call an element bad if it is nonzero, not a unit, and has no factorisation. Suppose that some $a_0 \in R$ is bad.
9. The element $a_0$ is not irreducible, because an irreducible element is a factorisation of length $1$. So $a_0 = b c$ with $b$ and $c$ not units. Both are nonzero, since $a_0 \neq 0$.
10. If $b$ and $c$ both had factorisations, then joining them would give a factorisation of $a_0$. So $b$ or $c$ is bad. Call it $a_1$, and call the other factor $e$.
11. Then $a_0 = a_1 e$ with $e$ not a unit. By steps 2 and 3, $(a_0) \subsetneq (a_1)$.
12. Repeating steps 9 to 11 with $a_1$, then $a_2$, and so on, gives an infinite chain $(a_0) \subsetneq (a_1) \subsetneq \cdots$. This contradicts step 7.
13. So no element is bad. Every nonzero element that is not a unit has a factorisation.

Now we show uniqueness.

14. Let $p$ be irreducible. By [[the theorem on irreducible elements in a PID|095ZHQ7WCJ]], $(p)$ is a maximal ideal. Since [[maximal ideals are prime|05WAF5T0GZ]], $(p)$ is a [[prime ideal|06HC6HK0Z8]].
15. So if $p \mid a b$, then $a b \in (p)$, hence $a \in (p)$ or $b \in (p)$. Since $p \neq 0$ and $p$ is not a unit, $p$ is a [[prime element|0MNHXBSX3M]].
16. If a prime $p$ divides $q_1 \cdots q_m$, then $p$ divides some $q_j$. This follows by induction on $m$, writing $q_1 \cdots q_m = (q_1 \cdots q_{m-1}) q_m$.
17. If $q$ is irreducible and $u$ is a unit, then $u q$ is irreducible. It is nonzero and not a unit, since $q = u^{-1} (u q)$. If $u q = x y$, then $q = x (u^{-1} y)$, so $x$ or $y$ is a unit.
18. [[Associates|053E86NWVK]] form an equivalence relation: if $b = u a$ and $c = v b$ with units $u, v$, then $c = (v u) a$ and $a = u^{-1} b$.
19. Let $p_1 \cdots p_n = q_1 \cdots q_m$ with all $p_i, q_k$ irreducible and $n, m \ge 1$. By induction on $n$, we prove that $n = m$ and that some permutation $\sigma$ makes $p_i$ and $q_{\sigma(i)}$ associates.
20. By steps 15 and 16, $p_1$ divides some $q_j$, say $q_j = p_1 u$. Since $q_j$ is irreducible and $p_1$ is not a unit, $u$ is a unit. So $p_1$ and $q_j$ are associates.
21. Cancelling $p_1 \neq 0$ gives $p_2 \cdots p_n = u \prod_{k \neq j} q_k$. Here an empty product is $1$.
22. Let $n = 1$. If $m \ge 2$, step 21 gives $1 = u \prod_{k \neq j} q_k$, so each $q_k$ with $k \neq j$ is a unit. This is false, so $m = 1$, and $\sigma(1) = 1$ works.
23. Let $n \ge 2$. If $m = 1$, step 21 gives $p_2 (p_3 \cdots p_n) = u$, so $p_2$ is a unit. This is false, so $m \ge 2$.
24. Choose $k_0 \neq j$ and replace $q_{k_0}$ by $u q_{k_0}$, which is irreducible by step 17. Then step 21 writes $p_2 \cdots p_n$ as a product of $m - 1$ irreducibles, each an associate of one $q_k$ with $k \neq j$.
25. By the induction hypothesis, $n - 1 = m - 1$, and there is a bijection $\tau$ from $\set{2, \dots, n}$ to $\set{k : k \neq j}$ with $p_i$ an associate of $q_{\tau(i)}$, using step 18.
26. Put $\sigma(1) = j$ and $\sigma(i) = \tau(i)$ for $i \ge 2$. Then $n = m$, $\sigma$ is a permutation, and $p_i$ and $q_{\sigma(i)}$ are associates for each $i$.
27. By steps 13 and 26, $R$ is a [[unique factorisation domain|06YMXJMXYS]].

## Idea

Existence: if an element had no factorisation, we could keep splitting off a bad factor forever. This would give an infinite strictly increasing chain of principal ideals, and the union of such a chain is principal, which stops the chain. Uniqueness: in a principal ideal domain irreducible elements are prime. So each irreducible factor on one side divides, and so matches, a factor on the other side. We cancel it and use induction.