Abstract Algebra – 1.8 Euclidean Rings and Principal Ideal Domains

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$:
    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$.


  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 $\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$.

  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=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

  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
    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:

  3. 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:

Theorem 1.8.2 A euclidean ring is a PID.


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


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.

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


  1. $\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$).


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

  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\land b=0$ or $a=0\land b=\pm 1$. $\square$


发送评论 编辑评论

 ̄﹃ ̄
∠( ᐛ 」∠)_
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
( ๑´•ω•) "(ㆆᴗㆆ)
Source: github.com/k4yt3x/flowerhd