# 'ED implies UFD' proof without PID?

Is there any way to prove 'ED implies UFD' without using the idea of PID?

The proof I know is the one in basic algebra books, the one that uses PID. I admit that the introduction of PID makes the proof easy, but on the other hand, all the PID and ring theory stuff seems to make the original proposition unnecessarily complicated. Is there a simpler and/or direct way to prove 'ED implies UFD'.

• In case anyone is wondering: ED means Euclidean domain, PID means principal ideal domain, and UFD means unique factorization domain. – Gerry Myerson Feb 18 '14 at 11:38
• Can you give some examples of books whose proofs you are trying to avoid? Most proofs that $\,\Bbb Z\,$ is a UFD easily generalize to any Euclidean domain. – Bill Dubuque Feb 28 '14 at 5:04

How hard this is depends on how you define Euclidean domain. It is simpler if you can assume that the Euclidean function satisfies $f(a) \le f(ab)$. Otherwise, you may have to use $g(a) = \min_{x\ne0} f(ax)$. This will give you existence of factorization into irreducibles. Uniqueness is another matter. See the details in Remarks about Euclidean Domains by Keith Conrad.

For a deeper look, see Factorization in Integral Domains by Pete L. Clark.

Unfortunately, these fine expositions do not contain the direct proof $ED \implies UFD$ that you're looking for.

Is there any way to prove 'ED implies UFD' without using the idea of PID?

Yes. If we want to prove that an Euclidean domain $D$ is an UFD we have to prove two things:

1. $D$ is an atomic domain (commonly known as factorization domain).
2. $D$ is an AP-domain. This means that every atom (aka irreducible element) is prime.

To prove the first item we need to assume that the euclidean valuation defined on $D$, let's say $\delta$, is submultiplicative, i.e., $\delta(ab)\ge \delta(a)$ for every $a,b\in D\setminus \{0\}$, which by the way, it's a property given in the standard definition of euclidean valuation. You can check the details in the paper by K. Conrad given in lhf's answer.

On the other hand, to prove item two we don't need to assume that $\delta$ is submultiplicative. It's enough to use the more general definition of an Euclidean domain as, e.g., is given in Dummit and Foote's book "Abstract Algebra". For further details you can see this answer.

Actually, although we can prove that an ED an UFD by the way that I wrote, there is a shorter version that doesn't use the implication that I used, i.e., Atomic domain $+$ AP-domain $\implies$ UFD.

Basically this shorter proof proves directly that an ED is an UFD just by showing that the two conditions for being an UFD are satisfied in an ED, i.e., the existence of a factorization for every nonzero and non-unit element and the uniqueness of such a factorization. The first condition is proved using the submultiplicative property in the same way that is used to prove that an ED is an atomic domain; and the second condition is proved using the fact that an ED is an GCD-domain, and this is enough because every GCD-domain is an AP-domain, see e.g. here or proposition 37 of Pete L. Clark's notes about factorization (he uses there the terminology EL-domain instead of AP-domain).

Now, the standar proof that an ED is a GCD-domain is very similar to my answer in the link above, but I found today a proof of this result in the book "Rings and factorization" by David Sharpe. More exactly, this result is the theorem 2.4.2 of Sharpe's book. By the way, this author doesn't prove that a PID is an UFD because he not even defines what an ideal is!

To finish, I'd say that essentially the second way to prove that an ED is an UFD uses the following implication: Atomic domain $+$ GCD-domain $\implies$ UFD (the converse being also true).

Let $R$ be a euclidean domain with eudlidean function $f$, i.e. it is an integral domain and $f: R \rightarrow \mathbb{N}_0$

1. $f(ab) \ge f(a)$ for every $a$, $b$ such that $ab \neq 0$
2. For every $a$ and $d \neq 0$, there is $q$ and $r$ such that $a=qd+r$ where either $r=0$ or $f(r)<f(d)$.

As noted, one can construct from a function with property 2 a function with both of the properties.

We now want to prove that

1. Every elements in $R$ can be factors into irreducibles.
2. Every irreducible is prime.

Let us check a few facts about the function $f$. Let $\epsilon$ be the minimum value of $f$. Then $f(1) = \epsilon$ because $x=1x$ for every $x$ implies that if $x \neq 0$, then $f(1) \le f(x)$. Hence for every unit $u$, $f(u)=\epsilon$. Conversely, if $f(u) = \epsilon$, then $u$ is a unit. This follows that if $u$ cannot divide some elements, then there should be elements $r$ such that $f(r) < f(d)$. Now we can prove that for every nonzero $a$ and a proper divisor $d$, $f(d) < f(a)$. Let $a=dq$. Let $q$ and $r$ be such that $d=ka+r$, $r=0$ or $f(r)<f(a)$. Because $d$ is a proper divisor, $r \neq 0$. Therefore $f(a)>f(r) = f(d(1-kq)) \ge f(d)$, since $k$ is not a unit so $1 \neq kq$.

Now we prove Bezout theorem. Let $a$ and $b$ are relatively prime; there is no common divisor of $a$ and $b$ which are non-unit. Let $u=ax+by$ be the non-zero element with least $f$ value among all elements of the form. Applying euclidean algorithm let $q$ and $r$ be such that $a= qu+r$ with $r=0 \vee f(r)<f(u)$. Since $f(r) \ge f(u)$, we have $u \mid a$. Similarly, $u \mid b$. Hence $u$ is a unit which completes the Bezout theorem; Whenever $a$ and $b$ are relatively prime in a ED, there is $x$, $y$ such that $ax+by=1$.

Now suppose that some element cannot be factored into irreducibles. Choose one with least value of $f$, say $n$. Since $n$ is not an irreducible, there is a proper divisor $d$ of $n$ so $n = qd$. Since $d$ and $q$ are proper divisors of $n$ we have that $f(d), f(q) < f(n)$. This shows that $d$ and $q$ can be factored into irreducibles which contradicts to the property of $n$. Therefore every elements in $R$ can be factored into irreducibles.

Now it remains to show that every irreducibles are prime. Let $p$ be an irreducible and $p \mid ab$ and $p \nmid a$. Since $a$ and $p$ are relatively prime, there is $x$ and $y$ such that $ax+py =1$. Then $b=bax+bpy= p(x+by)$ implies that $p|b$ which completes the proof.