[proofplan] The proof proceeds in two stages. First, we establish **existence** of a factorization into irreducibles by showing that any principal ideal domain satisfies the ascending chain condition on principal ideals (equivalently, $R$ is Noetherian), which prevents an element from being split into non-trivial factors indefinitely. Second, we establish **uniqueness** by proving that every irreducible element in a PID is prime, and then applying induction on the number of irreducible factors to show that any two factorizations agree up to reordering and associates. [/proofplan] [step:Show that every irreducible element in a PID is prime] Let $p \in R$ be irreducible, and suppose $p \mid ab$ for some $a, b \in R$. We must show that $p \mid a$ or $p \mid b$. Since $p \mid ab$, there exists $c \in R$ with $ab = pc$. Consider the ideal $(p, a)$ generated by $p$ and $a$. Since $R$ is a PID, there exists $d \in R$ with $(p, a) = (d)$. In particular $d \mid p$, so $p = d u$ for some $u \in R$. Since $p$ is irreducible, either $d$ is a unit or $u$ is a unit. **Case 1:** $u$ is a unit. Then $d = p u^{-1}$, so $(d) = (p)$. Since $a \in (d) = (p)$, we have $p \mid a$. **Case 2:** $d$ is a unit. Then $(d) = R$, so $(p, a) = R$. There exist $r, s \in R$ with $rp + sa = 1_R$. Multiplying both sides by $b$: \begin{align*} b = rpb + sab = rpb + spc = p(rb + sc). \end{align*} Hence $p \mid b$. In either case $p \mid a$ or $p \mid b$, so $p$ is prime. [guided] We want to show that irreducible elements in a PID are prime. Recall that an element $p$ is **irreducible** if $p$ is a nonzero non-unit and whenever $p = ab$, either $a$ or $b$ is a unit. An element $p$ is **prime** if $p$ is a nonzero non-unit and whenever $p \mid ab$, either $p \mid a$ or $p \mid b$. In general rings, prime implies irreducible but the converse can fail. The key property of PIDs that makes the converse hold is that every ideal is principal. Let $p \in R$ be irreducible, and suppose $p \mid ab$ for some $a, b \in R$, so $ab = pc$ for some $c \in R$. We want to show $p \mid a$ or $p \mid b$. The idea is to examine the ideal $(p, a)$. Since $R$ is a PID, we can write $(p, a) = (d)$ for some $d \in R$. Since $p \in (d)$, we have $d \mid p$, say $p = du$ for some $u \in R$. Now we use irreducibility of $p$: since $p = du$ and $p$ is irreducible, either $d$ is a unit or $u$ is a unit. **Case 1:** $u$ is a unit. Then $d$ and $p$ are associates, so $(d) = (p)$. Since $a \in (p, a) = (d) = (p)$, we conclude $p \mid a$. **Case 2:** $d$ is a unit. Then $(p, a) = (d) = R$, which means $p$ and $a$ generate the entire ring. So there exist $r, s \in R$ with $rp + sa = 1_R$. To bring $b$ into the picture, multiply through by $b$: \begin{align*} b = b \cdot 1_R = b(rp + sa) = rpb + sab. \end{align*} Since $ab = pc$, we substitute $sab = spc$: \begin{align*} b = rpb + spc = p(rb + sc). \end{align*} Hence $p \mid b$. Why does this argument fail in a ring that is not a PID? Because the ideal $(p, a)$ may not be principal, so we cannot produce the generator $d$ and run the irreducibility argument. For example, in $\mathbb{Z}[\sqrt{-5}]$, the element $2$ is irreducible but not prime: $2 \mid (1 + \sqrt{-5})(1 - \sqrt{-5}) = 6$ yet $2 \nmid (1 + \sqrt{-5})$ and $2 \nmid (1 - \sqrt{-5})$. The ideal $(2, 1 + \sqrt{-5})$ is not principal in that ring. [/guided] [/step] [step:Show that the ascending chain condition on principal ideals holds in a PID] Suppose $(a_1) \subset (a_2) \subset (a_3) \subset \cdots$ is an ascending chain of principal ideals in $R$. Define $I = \bigcup_{k=1}^{\infty} (a_k)$. We verify that $I$ is an ideal of $R$: if $x, y \in I$, then $x \in (a_m)$ and $y \in (a_n)$ for some $m, n \in \mathbb{N}$; taking $N = \max(m, n)$, both $x$ and $y$ lie in $(a_N)$, so $x - y \in (a_N) \subset I$; and for any $r \in R$ and $x \in (a_m)$, we have $rx \in (a_m) \subset I$. Hence $I$ is an ideal. Since $R$ is a PID, $I = (a)$ for some $a \in R$. Since $a \in I = \bigcup_{k=1}^{\infty} (a_k)$, there exists $n_0 \in \mathbb{N}$ with $a \in (a_{n_0})$. Then for all $k \ge n_0$: \begin{align*} (a_{n_0}) \subset (a_k) \subset I = (a) \subset (a_{n_0}). \end{align*} Hence $(a_k) = (a_{n_0})$ for all $k \ge n_0$, so the chain stabilizes. [guided] The ascending chain condition (ACC) on principal ideals states that every ascending chain $(a_1) \subset (a_2) \subset \cdots$ of principal ideals eventually stabilizes. This is the property that will guarantee existence of factorizations — it prevents us from splitting an element into non-trivial factors forever. Consider an ascending chain $(a_1) \subset (a_2) \subset (a_3) \subset \cdots$ in a PID $R$. Define the union $I = \bigcup_{k=1}^{\infty} (a_k)$. We first verify that $I$ is an ideal. Take any $x, y \in I$. Then $x \in (a_m)$ and $y \in (a_n)$ for some indices $m$ and $n$. Setting $N = \max(m, n)$, the chain condition gives $(a_m) \subset (a_N)$ and $(a_n) \subset (a_N)$, so both $x$ and $y$ lie in the ideal $(a_N)$. Therefore $x - y \in (a_N) \subset I$. Similarly, for any $r \in R$ and $x \in (a_m)$, we have $rx \in (a_m) \subset I$. So $I$ is an ideal of $R$. Now comes the key use of the PID hypothesis: since every ideal of $R$ is principal, $I = (a)$ for some $a \in R$. But $a$ itself must belong to the union $I = \bigcup_{k=1}^{\infty} (a_k)$, so $a \in (a_{n_0})$ for some index $n_0$. This gives $(a) \subset (a_{n_0})$. On the other hand, for every $k \ge n_0$, the chain gives $(a_{n_0}) \subset (a_k) \subset I = (a)$. Combining: \begin{align*} (a_{n_0}) \subset (a_k) \subset (a) \subset (a_{n_0}), \end{align*} so $(a_k) = (a_{n_0})$ for all $k \ge n_0$, and the chain stabilizes. Note that this argument actually proves a stronger fact: every ideal in a PID is finitely generated (since each ideal is generated by a single element), which means every PID is Noetherian. We only need the consequence for principal ideals in the existence argument below. [/guided] [/step] [step:Prove existence of factorization into irreducibles] Let $a \in R$ be a nonzero non-unit. We show $a$ can be written as a product of irreducible elements. If $a$ is irreducible, we are done. Otherwise, $a = a_1 b_1$ where neither $a_1$ nor $b_1$ is a unit. Then $(a) \subsetneq (a_1)$: indeed $a = a_1 b_1 \in (a_1)$ so $(a) \subset (a_1)$, and if $(a) = (a_1)$ then $a_1 = a u$ for some $u \in R$, giving $a = a u b_1$, hence $u b_1 = 1_R$ (since $R$ is an integral domain and $a \neq 0$), contradicting that $b_1$ is not a unit. If $a_1$ is irreducible, stop; otherwise factor $a_1 = a_2 b_2$ with neither factor a unit, and $(a_1) \subsetneq (a_2)$ by the same argument. Continuing, we obtain an ascending chain of principal ideals: \begin{align*} (a) \subsetneq (a_1) \subsetneq (a_2) \subsetneq \cdots. \end{align*} By the ascending chain condition established in the previous step, this chain must stabilize. Therefore the process terminates after finitely many steps, say at index $m$, meaning $a_m$ is irreducible. At termination we have $a = b_1 b_2 \cdots b_m \cdot a_m$. Each factor $b_k$ is a nonzero non-unit and lies in a strictly smaller principal ideal than $a_{k-1}$ (where $a_0 := a$). We apply the same argument to each $b_k$ that is not already irreducible. Each sub-factorization again produces a strictly ascending chain of principal ideals, which must stabilize by ACC. Therefore every factor is eventually expressed as a product of irreducibles, yielding a complete factorization of $a$ into irreducibles. [guided] We want to show that every nonzero non-unit $a \in R$ factors into irreducibles. The strategy is a descent argument: keep splitting $a$ into non-trivial factors, and use the ACC on principal ideals to guarantee this process terminates. If $a$ is already irreducible, the factorization is $a$ itself (a product of one irreducible). If not, then $a = a_1 b_1$ where neither $a_1$ nor $b_1$ is a unit. We claim $(a) \subsetneq (a_1)$. Since $a = a_1 b_1$, we have $a \in (a_1)$, so $(a) \subset (a_1)$. Suppose for contradiction that $(a) = (a_1)$. Then $a_1 = au$ for some $u \in R$. Substituting: $a = a_1 b_1 = au b_1$, so $a(1 - ub_1) = 0$. Since $R$ is an integral domain and $a \neq 0$, we get $ub_1 = 1_R$, which means $b_1$ is a unit — contradicting our assumption. So the inclusion $(a) \subsetneq (a_1)$ is strict. Now repeat: if $a_1$ is not irreducible, write $a_1 = a_2 b_2$ (neither a unit) and get $(a_1) \subsetneq (a_2)$. This produces an ascending chain $(a) \subsetneq (a_1) \subsetneq (a_2) \subsetneq \cdots$. By the ACC on principal ideals (the union $\bigcup (a_i)$ is an ideal, hence principal in a PID, say $(a_N)$, forcing the chain to stabilize at index $N$), this chain stabilizes. But each inclusion is strict, so the chain can only stabilize by terminating: at some finite index $m$, the element $a_m$ must be irreducible. What about the $b_k$ factors? Each $b_k$ is a nonzero non-unit (by construction), and any attempt to factor $b_k$ into non-trivial factors produces its own ascending chain, which also stabilizes by ACC. So every $b_k$ eventually decomposes into irreducibles as well. Collecting all the irreducible factors gives the desired factorization of $a$. Why is the ACC crucial here? Without it, we could have an element that splits forever, never reaching irreducibles. This is exactly what happens in rings like $\mathbb{Z}[x_1, x_2, x_3, \ldots] / (x_1 - x_2^2, x_2 - x_3^2, \ldots)$ where the element $x_1$ has no irreducible factorization. [/guided] [/step] [step:Prove uniqueness of factorization up to reordering and associates] Suppose $a \in R$ has two factorizations into irreducibles: \begin{align*} a = p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n, \end{align*} where each $p_i$ and each $q_j$ is irreducible. We prove $m = n$ and, after reordering, $p_i$ and $q_i$ are associates for each $i$ (i.e., $p_i = u_i q_i$ for some unit $u_i \in R^\times$). We proceed by induction on $m$. **Base case ($m = 1$).** Then $a = p_1$ is irreducible, and $p_1 = q_1 q_2 \cdots q_n$. Since $p_1$ is irreducible and the $q_j$ are all non-units, we must have $n = 1$ (otherwise $p_1$ would be a product of two or more non-units, contradicting irreducibility). So $n = 1$ and $p_1 = q_1$; they are trivially associates. **Inductive step.** Assume the result holds whenever one factorization has fewer than $m$ irreducible factors, where $m \ge 2$. Consider $p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n$. Since $p_1$ is irreducible in a PID, $p_1$ is prime (by the first step). Since $p_1 \mid q_1 q_2 \cdots q_n$, primality of $p_1$ implies $p_1 \mid q_j$ for some index $j$. After reordering, we may assume $p_1 \mid q_1$. Write $q_1 = p_1 v$ for some $v \in R$. Since $q_1$ is irreducible and $p_1$ is not a unit, $v$ must be a unit. Therefore $q_1 = p_1 v$ with $v \in R^\times$, i.e., $p_1$ and $q_1$ are associates. Now cancel $p_1$ from both sides. Since $R$ is an integral domain: \begin{align*} p_1 p_2 \cdots p_m = p_1 v \cdot q_2 \cdots q_n \implies p_2 \cdots p_m = v \cdot q_2 \cdots q_n = (vq_2) \cdot q_3 \cdots q_n. \end{align*} The element $vq_2$ is irreducible since $v$ is a unit and $q_2$ is irreducible. The left-hand side is a product of $m - 1$ irreducibles. By the induction hypothesis, $m - 1 = n - 1$ (so $m = n$) and, after reordering $q_2, \ldots, q_n$, each $p_i$ is an associate of the corresponding factor on the right for $i = 2, \ldots, m$. Combining with $p_1$ and $q_1$ being associates, we conclude that $m = n$ and, after a suitable reordering, $p_i$ and $q_i$ are associates for all $i \in \{1, \ldots, m\}$. [guided] We now prove uniqueness. Suppose $a$ has two factorizations $a = p_1 \cdots p_m = q_1 \cdots q_n$ into irreducibles. The argument proceeds by strong induction on $m$, the number of irreducible factors on the left side. **Base case ($m = 1$).** We have $p_1 = q_1 \cdots q_n$ with $p_1$ irreducible. If $n \ge 2$, then $p_1$ is a product of two or more non-units, contradicting irreducibility. So $n = 1$ and $p_1 = q_1$. **Inductive step ($m \ge 2$).** Every irreducible in a PID is prime. To see why: if $p$ is irreducible and $p \mid ab$, write $(p, a) = (d)$ since $R$ is a PID. Then $d \mid p$, and irreducibility of $p$ forces either $d \in R^\times$ — giving $(p, a) = R$, so $1_R = rp + sa$ for some $r, s$, and multiplying by $b$ yields $b = rpb + sab$, whence $p \mid b$ — or $d$ and $p$ are associates, giving $p \mid a$. Applying this to $p_1$: since $p_1$ is prime and $p_1 \mid q_1 q_2 \cdots q_n$, the definition of primality gives $p_1 \mid q_j$ for some $j$. (Concretely, apply the definition inductively: $p_1 \mid q_1(q_2 \cdots q_n)$ implies $p_1 \mid q_1$ or $p_1 \mid q_2 \cdots q_n$; if the latter, repeat.) Relabel so that $j = 1$. Since $p_1 \mid q_1$, write $q_1 = p_1 v$. Now $q_1$ is irreducible and $p_1$ is not a unit (irreducibles are by definition non-units). Since $q_1 = p_1 v$ and $q_1$ is irreducible, one of $p_1, v$ must be a unit. Since $p_1$ is not a unit, $v$ must be a unit. So $q_1$ and $p_1$ are associates. Cancel $p_1$ from both sides. Since $R$ is an integral domain and $p_1 \neq 0$: \begin{align*} p_1 p_2 \cdots p_m &= p_1 v \cdot q_2 \cdots q_n \\ \implies p_2 \cdots p_m &= (v q_2) \cdot q_3 \cdots q_n. \end{align*} The element $vq_2$ is irreducible: if $vq_2 = xy$ with $x, y$ non-units, then $q_2 = (v^{-1}x)y$, and since $v$ is a unit, $v^{-1}x$ is a non-unit iff $x$ is a non-unit, contradicting irreducibility of $q_2$. So the right side is a product of $n - 1$ irreducibles. The left side is a product of $m - 1$ irreducibles. By the induction hypothesis (applied to $m - 1 < m$), we get $m - 1 = n - 1$ and the factors match up to reordering and associates. This is where the proof would fail without the "irreducible implies prime" step. In $\mathbb{Z}[\sqrt{-5}]$, the element $6$ has two essentially different factorizations: $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$. All four factors are irreducible, but $2$ is not prime ($2 \mid (1 + \sqrt{-5})(1 - \sqrt{-5})$ yet $2 \nmid 1 + \sqrt{-5}$ and $2 \nmid 1 - \sqrt{-5}$), so the cancellation argument breaks down. [/guided] [/step] [step:Combine existence and uniqueness to conclude $R$ is a UFD] The existence step shows that every nonzero non-unit in $R$ factors as a product of irreducibles. The uniqueness step shows that any two such factorizations have the same number of irreducible factors and agree up to reordering and multiplication by units. Together, these are precisely the two conditions in the definition of a unique factorization domain. Therefore $R$ is a UFD. [/step]