'ED implies UFD' proof without PID?

Question

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'.

Answer 1

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.

Answer 2

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

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 element 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’s theorem. Let $a$ and $b$ be relatively prime; there is no common divisor of $a$ and $b$ which are not units. Let $u=ax+by$ be the non-zero element with least value of $f$ among all elements of the form. Applying the Euclidean algorithm we get $q$ and $r$ be such that $a= qu+r$ with $r=0 $ or $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 element in $R$ can be factored into irreducibles.

Now it remains to show that every irreducible is 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.