## ED implies PID implies UFD

**Theorem:** Every Euclidean domain is a principal ideal domain.

**Proof:**
For any ideal \(I\), take a nonzero element of minimal norm \(b\).
Then \(I\) must be generated by \(b\),
because for any \(a \in I\) we have \(a = b q + r \) for some \(q,r\) with
\(N(r) \lt N(b)\), and we must have \(r = 0\) otherwise \(r\) would be a nonzero
element of smaller norm than \(b\), which is a contradiction.

**Fact:** If \(R\) is a UFD then \(R[x]\) is also a UFD.

**Theorem:** Every principal ideal domain is a unique factorization domain.

**Proof:** We show it is impossible to find an infinite sequence
\(a_1, a_2,...\) such that \(a_i\) is divisible by \(a_{i+1}\) but is not an
associate. Once done we can iteratively factor an element as
we are guaranteed this process terminates.

Suppose such a sequence exists. Then the \(a_i\) generate the sequence of distinct principal ideals \((a_1) \subset (a_2) \subset ...\). The union of these ideals is some principal ideal \((a)\). So \(a \in (a_n)\) for some \(n\), which implies \((a_i) = (a_n)\) for all \(i \ge n\), a contradiction.

Uniqueness: each irreducible \(p\) generates a maximal ideal \((p)\) because if \((p) \subset (a) \subset R\) then \(p =a b\) for some \(b \in R\) implying that \(a\) or \(b\) is a unit, thus \((a) = (p)\) or \((a) = R\). Thus \(R/(p)\) is a field. Next suppose a member of \(R\) has two factorizations

Consider the ideals \((p_i), (q_i)\). Relabel so that \(p_1\) generates a minimal ideal amongst these (in other words, \((p_1)\) does not strictly contain another one of the ideals). Now we show \((p_1) = (q_i)\) for some \(i\). Suppose not. Then \((p_1)\) does not contain any \(q_i\), thus \(q_i\) is nonzero modulo \((p_1)\) for all \(i\), which is a contradiction because the left-hand side of the above equation is zero modulo \((p_1)\).

Relabel so that \((p_1) = (q_1)\). Then \(p_1 = u q_1\) for some unit \(u\). Cancelling gives \(u p_2 ... p_r = q_2 ... q_s\). The element \(u p_2\) is also irreducible, so by induction we have that factorization is unique.∎

The converse of the above theorem is not always true. Consider the ring \(\mathbb{Z}[x]\). The ideal \((2,x)\) is not principal: suppose \((2,x) = (a)\) for some \(a\). Since this ideal contains the even integers, \(a\) must be some integer (multiplication never reduces the degree of an element), and in fact it must be (an associate of) 2. But \((2)\) does not contain polynomials with odd coefficients, so \((2,x) \ne (2)\).

*blynn@cs.stanford.edu*💡