Definition 1.8.1 If $a,b$ lie in a commutative ring $R$, then a greatest common divisor (gcd) of $a,b$ is a common divisor $d\in R$ which is divisible by every common divisor; that is if $c\mid a$ and $c\mid b$, then $c\mid d$.

Definition 1.8.2 A principal ideal domain is a domain $R$ in which every ideal is a principal ideal. This term is usually abbreviated to PID.

Theorem 1.8.1 Let $R$ be a PID.

1. Every $a,b\in R$ has a gcd, say $d$, that is a linear combination of $a$ and $b$:
   $$d=sa+tb,$$
   where $s,t\in R$.

2. Euclid’s Lemma: If an irreducible element $p\in R$ divides a product $ab$, then either $p\mid a$ or $p\mid b$.

3. Unique Factorization: If $a\in R$ and $a=p_1\cdots p_m$, where $p_i$ are irreducible elements, then this factorization is unique in the following sense: if $a=q_1\cdots q_k$, where the $q_j$ is are irreducible elements, then $k=m$ and the $q$’s can be reindexed so that $p_i$ and $q_i$ are associates for all $i$.

Proof.

1. If $a,b$ are both $0$, then their gcd is $0$.

   Otherwise, since $R$ is a PID, $(a,b)$ is a principal ideal; that is $\mathrm{\exists }d\in R,(a,b)=(d)$.

   Let’s prove that $d=gcd(a,b)$.

   Because $a,b\in (d)$, $(d\mid a\wedge d\mid b)\Rightarrow d$ is a common divisor of $a$ and $b$.

   And $\mathrm{\exists }s,t\in R$ with $d=sa+tb$ for $d\in (a,b)$.

   Then $\mathrm{\forall }u\in R$ with $u$ is a common divisor of $a$ and $b$, then $\mathrm{\exists }v,w\in R$ with $a=vu,b=wu$.

   So $d=sa+tb=svu+swu=(sv+sw)u\Rightarrow u\mid d$.

   Therefore $d$ is gcd of $a$ and $b$, which is a linear combination of $a,b$.

2. If $p\nmid a$, then $1$ is the gcd of $p$ and $a$.

   Then we have $s,t\in R$ with $1=sp+ta$ for (1).

   So $b=apb+tab$. Since $p\mid ab$, it follows that $p\mid b$.

3. By induction on $M=max\{m,k\}$.

   If $M=1$, we have $p_1=a=q_1$.

   For inductive step, the given equation shows that $p_m\mid q_1\cdots q_k$. By (2), Euclid’s Lemma, there is some $i$ with $p_m\mid q_i$.

   Since $q_i$ is irreducible, $q_i=u{p}_m$ for some unit $u$; that is $q_i$ and $p_m$ are associates.

   Reindexing, we may assume that $q_k=u{p}_m$; canceling, we have $p_1\cdots p_{m-1}=q_1\cdots (q_{k-1}u)$.

   Since $q_{k-1}u$ is irreducible, the inductive hypothesis gives $m-1=k-1$ (hence, $m=k$) and, after reindexing, $p_i$ and $q_i$ are associates for all $i$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Definition 1.8.3 A euclidean ring is a domain $R$ that is equipped with a function
$$\partial :R\text{}\{0\}\to \mathbb{N},$$
called a degree function, such that

1. $\partial (f)\le \partial (fg)$ for all $f,g\in R$ with $f,g\ne 0$;

2. Division Algorithm: for all $f,g\in R$ with $f\ne 0$, there exist $q,r\in R$ with
   $$g=qf+r,$$
   where either $r=0$ or $\partial (r)<\partial (f)$.

Example 1.8.1

1. Let $R$ have a degree function $\partial$ that is identically $0$. If $f\in R$ and $f\ne 0$, the division algorithm gives an equation $1=qf+r$ with $r=0$ or $\partial (r)<\partial (f)$. This forces $r=0$, for $\partial (r)<\partial (f)=0$ is not possible. Therefore, $q=f^{-1}$ and $R$ is a field.

2. The set of integers $\mathbb{Z}$ is a euclidean ring with degree function $\partial (m)=|m|$. Note that $\partial$ is multiplicative:
   $$\partial (mn)=|mn|=|m||n|=\partial (m)\partial (n).$$

3. When $k$ is a field, the domain $k[x]$ is a euclidean ring with degree function $\partial (f)=\mathrm{deg}(f)$, the usual degree of a nonzero polynomial $f$. Note that $\mathrm{deg}$ is additive:
   $$\partial (fg)=\mathrm{deg}(fg)=\mathrm{deg}(f)+\mathrm{deg}(g)=\partial (f)+\partial (g).$$

Theorem 1.8.2 A euclidean ring is a PID.

Proof.

Let $R$ be a euclidean ring with a degree function $\partial$.

Let $I$ be an ideal in $R$. If $I\ne (0)$, and then we have the $d\in I\text{}\{0\}$ with its degree is minimal in $I\text{}\{0\}$.

$\mathrm{\forall }a\in I$, by division algorithm, $a=qd+r$ with $\partial (r)<\partial (d)$ or $r=0$.

Since $r\in I$, it follows that $r=0$; so $a\in (d)$.

Therefore $I\subset (d)\subset I\Rightarrow (d)=I$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

Definition 1.8.4 If a degree function $\partial$ is multiplicative, that is, if $\partial (fg)=\partial (f)\partial (g)$, then $\partial$ is called a norm.

Example 1.8.2 The Gaussian integers $\mathbb{Z}[i]$ form a euclidean ring whose degree function
$$\partial (a+bi)=a^2+b^2$$
is a norm.

We now show that $\partial$ satisfies the first property of a degree function.

If $\beta =c+id\in \mathbb{Z}[i]$ and $\beta \ne 0$, then
$$1\le \partial (\beta ),$$
for $\partial (\beta )=a^2+b^2$ is a positive integer; it follows that if $\alpha ,\beta \in \mathbb{Z}[i]$ with $\beta \ne 0$, then
$$\partial (\alpha )\le \partial (\alpha )\partial (\beta )=\partial (\alpha \beta ).$$
Let us show that $\partial$ also satisfies the Division Algorithm.

Given $\alpha ,\beta \in \mathbb{Z}[i]$ and $\beta \ne 0$, regard $\alpha /\beta$ as an element of $\mathbb{C}$. Rationalizing the denominator gives $\alpha /\beta =\alpha \bar{\beta }/(\beta \bar{\beta })=\alpha \bar{\beta }/\partial (\beta )$, so that
$$\alpha /\beta =x+yi,$$
where $x,y\in \mathbb{Q}$.

Write $x=a+u$ and $y=b+v$, where $a,b\in \mathbb{Z}$ are integers closest to $x$ and $y$, respectively; thus $|u|,|v|\le \frac{1}{2}$. (If $x$ or $y$ has the form $m-\frac{1}{2}$, where $m$ is an integer, then we chose the integer $m$ as the closest integer.) It follows that
$$\alpha =\beta (a+bi)+\beta (u+vi).$$
Notice that $\beta (u+vi)\in \mathbb{Z}$, for it is equal to $\alpha -\beta (a+bi)$. Finally, we have
$$\partial (\beta (u+vi))=(u^2+v^2)\partial (\beta )\le (\frac{1}{4}+\frac{1}{4})\partial (\beta )=\frac{1}{2}\partial (\beta )<\partial (\beta ).$$
It’s easy to find that quotients and remainders in $\mathbb{Z}[i]$ may not be unique. For example, let $\alpha =3+5i$ and $\beta =2$. Then $\alpha /\beta =\frac{3}{2}+\frac{5}{2}i$; the possible choice are
$$\begin{array}{rl}a=1\text{ and }u=\frac{1}{2}& \text{ or }a=2\text{ and }u=-\frac{1}{2},\\ b=2\text{ and }v=\frac{1}{2}& \text{ or }b=3\text{ and }v=-\frac{1}{2}.\end{array}$$
Hence, there are four quotients and remainders after dividing $3+5i$ by $2$ in $\mathbb{Z}[i]$.

Theorem 1.8.3 The ring $\mathbb{Z}[i]$ of Gaussian integers is a PID.

Definition 1.8.5 An element $u$ in a domain $R$ is a universal side divisor if $u$ is not a unit and, for every $x\in R$, either $u\mid x$ or there is a unit $z\in R$ with $u\mid (x+z)$.

Proposition 1.8.1 If $R$ is a euclidean ring but not a field, then $R$ has a universal side divisor.

Proof.

Let $\partial$ be the degree function on $R$, and define
$$S=\{\partial (v);v\ne 0\text{ and }v\text{ is not a unit}\}.$$
Since $R$ is not a field, then $S$ is a nonempty subset of the natural numbers and, hence, $S$ has a smallest element, say, $\partial (u)$.

Then we claim that $u$ is a universal side divisor.

If $x\in R$, there are elements $q$ and $r$ with $x=qu+r$. If $r=0$, then $u\mid x$; otherwise, $\partial (r)<\partial (u)$ shows that $r\notin S\Rightarrow r$ is a unit.

Therefore, $u$ is a universal side divisor. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$

The converse of Theorem 1.8.2 is false: there are PIDs that are not euclidean rings.

Example 1.8.3 If $\alpha =\frac{1}{2}(1+\sqrt{-19})$, then it is shown in algebraic number theory that the ring
$$\mathbb{Z}(\alpha )=\{a+b\alpha ;a,b\in \mathbb{Z}\}$$
is a PID ($\mathbb{Z}(\alpha )$ is the ring of algebraic integers in the quadratic number field $\mathbb{Q}(\sqrt{-19})$). In 1949, Motzkin proved that $\mathbb{Z}(\alpha )$ doesn’t have a universal side divisor, so it isn’t a euclidean ring.

Proposition 1.8.2 Let $R$ be a euclidean ring, not a field, whose degree function $\partial$ is a norm.

1. An element $\alpha \in R$ is a unit if and only if $\partial (\alpha )=1$.
2. If $\alpha \in R$ and $\partial (\alpha )=p$, where $p$ is a prime number, then $\alpha$ is irreducible.
3. The only units in the ring $\mathbb{Z}[i]$ of Gaussian integers are $\pm 1$ and $\pm i$.

Proof.

1. $\partial (1)=\partial (1\cdot 1)=\partial (1)\partial (1)\Rightarrow$ $\partial (1)=1$ or $\partial (1)=0$.

   If $\partial (1)=0$, then $\mathrm{\forall }a\in R\text{}\{0\},\partial (a)=\partial (1a)=\partial (1)\partial (a)=0$; hence, by the Division Algorithm, $1=qa+r$ with $r=0$.

   Every element is a unit, contradicting $R$ is not a field.

   Therefore $\partial (1)=1$.

   • ($\Rightarrow$).

     $1=\partial (1)=\partial (\alpha {\alpha }^{-1})=\partial (\alpha )\partial ({\alpha }^{-1})$.

     For $\partial (\alpha )$ and $\partial ({\alpha }^{-1})$ are positive integers, $\partial (\alpha )=1$.

   • ($\Leftarrow$).

     $1=q\alpha +r$ with $r=0$ or $\partial (r)<\partial (\alpha )=1$.

     If $r\ne 0$, that is $\partial (r)=0$, then $1=q^{\prime }r+r^{\prime }$ with $r^{\prime }=0$, by the Division Algorithm.

     Thus, $r$ is a unit and, hence, $\partial (r)=1$, which contradicts $\partial (r)=0$.

2. If $\alpha =uv$, then $p=\partial (\alpha )=\partial (u)\partial (v)$.

   For $p$ is prime, $\partial (u)=1$ or $\partial (v)=1$ and, hence, $u$ is a unit or $v$ is a unit.

3. If $a+bi\in \mathbb{Z}[i]$ is a unit, then $a^2+b^2=\partial (a+bi)=1$.

   Since $a,b\in \mathbb{Z}$, $a=\pm 1\wedge b=0$ or $a=0\wedge b=\pm 1$. $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}$