## 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

$p_1 ... p_r = q_1 ... q_s$

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)$$.

Ben Lynn blynn@cs.stanford.edu 💡