> [!NOTE] Lemma (ED$\implies$UFD) > If $(R, \partial)$ is a [[Euclidean Domain|Euclidean domain]], then $R$ is [[Unique Factorisation Domain|unique factorisation domain]]. ###### Proof that ED$\implies$UFD We prove existence of factorisation as follows. Let $W$ be the set of elements in $R$ that are non-zero, not units and cannot be expressed as a product irreducibles. Suppose $W$ is non-empty then by the [[Well-Ordering Principle|well-ordering principle]], there exists $a\in W$ with the smallest value $\partial(a)$. Since $a$ is irreducible, we must have $a=bc$ where neither $b$ nor $c$ are units. By [[Euclidean Valuation of Proper Divisor is Strictly Less]], we have $\partial(b)<\partial(a)$ and $\partial(c)<\partial(a)$. As $\partial(a)$ is minimal among the elements of $W$, we see that $b,c$ do not belong to $W$. Thus $b,c$ are product of irreducible elements. But $a=bc$, so $a$ is a product of irreducible elements, giving a contradiction. *Recall that the principles of induction and well-ordering are equivalent so we may prove existence of factorisation by induction instead.* Now we prove uniqueness of factorisation. Let $p_{1},p_{2},\dots q_{m}$ and $q_{1},\dots,q_{r}$ be irreducible and $u,v$ units such that $up_{1}p_{2}\cdots p_{m}=vq_{1}q_{2}\cdots q_{n}\tag{1}$. By [[Irreducible Elements of Euclidean Domain are Prime|Euclid's lemma]] we have that the $p_{i}$ and $q_{j}$ are prime. That is, since $p_{m}\mid vq_{1}\cdots q_{n}$ we have $p_{m}\mid v$ or $p_{m}\mid q_{i}$ where $i=1,2,3\dots$ or $n$. However, as $v$ is a unit we have $p_{m}\not \mid u$. Thus, after rearranging the $q_{j}$ we have that $p_{m}\mid q_{n}$. But $q_{n}$ is irreducible and $p_{m}$ is not a unit. Therefore $p_{n}$ and $q_{n}$ are [[Associates in Integral Domain are Necessarily Unit Multiples of Each Other|associates]]. We may write $p_{m}=wq_{n}$ where $w$ is a unit. Hence $(1)$ yields $up_{1}p_{2}\cdots p_{m-1}wq_{n}=vq_{1}q_{2}\cdots q_{n-1}q_{n}$By [[Cancellation Law for Integral Domains]], $(uw)p_{1}p_{2}\cdots p_{m-1}=vq_{1}q_{1} \cdots q_{n-1}.$Note that $uw$ is a unit. Now we repeat the argument to obtain after rearrangement, $p_{m-1} \sim q_{n-1}$ etc. If $m>n$, then eventually we will obtain, $u'p_{1}p_{2} \cdots p_{m-n}=v$where $u'$ is a unit, from which we get that $p_{1} \mid v$ giving a contradiction as $p_{1}$ is not a unit. Similarly we get a contradiction if $m<n$. Hence $m=n$. ![[Pasted image 20241216171856.png|400]]