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.
-
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$. -
Euclid's Lemma: If an irreducible element $p\in R$ divides a product $ab$, then either $p\mid a$ or $p\mid b$.
-
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.
-
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 $\exists d\in R,(a,b)=(d)$.
Let's prove that $d=\gcd(a,b)$.
Because $a,b\in (d)$, $(d\mid a\land d\mid b)\Rightarrow d$ is a common divisor of $a$ and $b$.
And $\exists s,t\in R$ with $d=sa+tb$ for $d\in(a,b)$.
Then $\forall u\in R$ with $u$ is a common divisor of $a$ and $b$, then $\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$.
-
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$.
-
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=up_m$ for some unit $u$; that is $q_i$ and $p_m$ are associates.
Reindexing, we may assume that $q_k=up_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$. $\square$
Definition 1.8.3 A euclidean ring is a domain $R$ that is equipped with a function
$$\partial:R\textbackslash\{0\}\to \mathbb N,
$$
called a degree function, such that
-
$\partial(f)\le \partial(fg)$ for all $f,g\in R$ with $f,g\ne 0$;
-
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
-
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.
-
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).
$$ -
When $k$ is a field, the domain $k[x]$ is a euclidean ring with degree function $\partial(f)=\deg(f)$, the usual degree of a nonzero polynomial $f$. Note that $\deg$ is additive:
$$
\partial(fg)=\deg(fg)=\deg(f)+\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\textbackslash\{0\}$ with its degree is minimal in $I\textbackslash\{0\}$.
$\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$. $\square$
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\overline\beta/(\beta\overline\beta)=\alpha\overline\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{align}
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{align}
$$
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. $\square$
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.
- An element $\alpha\in R$ is a unit if and only if $\partial(\alpha)=1$.
- If $\alpha\in R$ and $\partial(\alpha)=p$, where $p$ is a prime number, then $\alpha$ is irreducible.
- The only units in the ring $\mathbb Z[i]$ of Gaussian integers are $\pm 1$ and $\pm i$.
Proof.
-
$\partial(1)=\partial(1\cdot 1)=\partial(1)\partial(1)\Rightarrow$ $\partial(1)=1$ or $\partial(1)=0$.
If $\partial(1)=0$, then $\forall a\in R\textbackslash\{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'r+r'$ with $r'=0$, by the Division Algorithm.
Thus, $r$ is a unit and, hence, $\partial(r)=1$, which contradicts $\partial(r)=0$.
-
-
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.
-
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\land b=0$ or $a=0\land b=\pm 1$. $\square$