Chapter 15

Hard

Euclidean Domains & Principal Ideal Domains

00 · Symbol Glossary

$N$Euclidean norm (valuation)

A function $N: R\setminus\{0\} \to \mathbb{Z}_{\geq0}$ measuring the "size" of a nonzero ring element, chosen so that division-with-remainder makes the remainder strictly smaller. $N(n)=\lvert n\rvert$ for $\mathbb{Z}$ ; $N(f)=\deg f$ for $F[x]$ .

$(a,b)$Ideal generated by two elements

$(a,b) := aR+bR = \{ar+bs : r,s\in R\}$ — the smallest ideal containing both $a$ and $b$ (Theorem 12.3's sum-of-principal-ideals).

$a \sim b$Associate elements

$a,b\in R$ are associates if $a=ub$ for some unit $u\in R^\times$ . In $\mathbb{Z}$ , $n$ and $-n$ are always associates; associates generate the same principal ideal.

$p \mid a$p divides a (ring version)

$a = pc$ for some $c\in R$ — the same divisibility notion from Chapter 01, now stated for a general ring.

01 · Euclidean Domains

Chapter 14's division algorithm for $F[x]$ and elementary school long division for $\mathbb{Z}$ share an identical shape. Abstracting that shape gives a single framework covering both at once.

Definition — Euclidean Domain

An integral domain $R$ is a Euclidean domain if there is a function $N: R\setminus\{0\}\to\mathbb{Z}_{\geq0}$ such that for all $a,b\in R$ with $b\neq0$ , there exist $q,r\in R$ with:

a = qb+r, \qquad r=0 \text{ or } N(r) < N(b)

02 · Examples

Example — Z with N(n) = |n|

Ordinary division with remainder: for $a,b\in\mathbb{Z}$ , $b\neq0$ , there exist $q,r$ with $a=qb+r$ , $0\le r<\lvert b\rvert$ — the familiar grade-school fact, now recognized as exactly Definition 15's requirement with $N(n)=\lvert n\rvert$ .

Example — F[x] with N(f) = deg f

Theorem 14.5 (Chapter 14) is precisely the Euclidean property for $F[x]$ with $N(f) := \deg f$ . Every polynomial ring over a field is a Euclidean domain.

Further afield: the Gaussian integers

$\mathbb{Z}[i] = \{a+bi : a,b\in\mathbb{Z}\} \subset \mathbb{C}$ is also Euclidean, with $N(a+bi) = a^2+b^2$ (the squared complex modulus). Dividing $\alpha$ by nonzero $\beta$ in $\mathbb{Z}[i]$ : compute $\alpha/\beta\in\mathbb{Q}[i]$ , round each coordinate to the nearest integer to get $q\in\mathbb{Z}[i]$ , and set $r=\alpha-q\beta$ ; a geometric argument (the rounding error in each coordinate is at most $\tfrac12$ ) shows $N(r)<N(\beta)$ . This example is not pursued further in this course, but signals that the framework reaches well beyond $\mathbb{Z}$ and $F[x]$ .

03 · Every Euclidean Domain Is a PID

Definition — Principal Ideal Domain (PID)

An integral domain in which every ideal is principal (of the form $(a)=aR$ for some $a\in R$ ) is a principal ideal domain.

Theorem 15.1 — Euclidean Domains Are PIDs

Every Euclidean domain is a principal ideal domain.

Proof

Let $R$ be Euclidean with norm $N$ , and let $I\trianglelefteq R$ . If $I=\{0\}$ , then $I=(0)$ , principal. Otherwise, the set $\{N(a) : a\in I, a\neq0\}$ is a nonempty set of nonnegative integers, so by well-ordering it has a least element; pick $d\in I$ , $d\neq0$ , achieving this minimum value of $N$ among nonzero elements of $I$ .

Claim: $I=(d)$ . Since $d\in I$ , absorption gives $(d)=dR\subseteq I$ .

For the reverse inclusion, take any $a\in I$ . By the Euclidean property, $a=qd+r$ with $r=0$ or $N(r)<N(d)$ . Now $r=a-qd$ ; since $a\in I$ and $qd\in I$ (absorption, as $d\in I$ ), subtraction-closure gives $r\in I$ . If $r\neq0$ , then $N(r)<N(d)$ contradicts $d$ 's minimality among nonzero elements of $I$ . So $r=0$ , giving $a=qd\in(d)$ .

Both inclusions hold: $I=(d)$ , principal. Since $I$ was an arbitrary ideal, $R$ is a PID.

Example — Confirming familiar facts as instances of Theorem 15.1

Every ideal of $\mathbb{Z}$ has the form $n\mathbb{Z}=(n)$ — this is exactly Theorem 3.6's subgroup classification, now recognized as a special case of Theorem 15.1 (since $\mathbb{Z}$ is Euclidean). Every ideal of $F[x]$ ( $F$ a field) is $(f)$ for some polynomial $f$ — a genuinely new fact, following the identical proof technique with $N=\deg$ .

04 · GCDs and Bézout's Identity in a PID

Definition — Greatest Common Divisor (PID version)

In a PID $R$ , for $a,b\in R$ not both zero, $(a,b) = (d)$ for some $d\in R$ (Theorem 15.1/the PID property). Any such $d$ is called a greatest common divisor of $a,b$ , written $\gcd(a,b)$ (well-defined up to multiplication by a unit — i.e. up to associates).

Theorem 15.2 — Bézout's Identity in a PID

For $a,b$ in a PID $R$ , $\gcd(a,b) = ra+sb$ for some $r,s\in R$ .

Proof

By definition, $\gcd(a,b)$ generates $(a,b)=aR+bR$ , so $\gcd(a,b) \in aR+bR$ , meaning $\gcd(a,b)=ra+sb$ for some $r,s\in R$ .

Example — Bézout in F[x]

In $\mathbb{Q}[x]$ : $\gcd(x^2-1, x-1) = x-1$ (since $x-1$ divides $x^2-1=(x-1)(x+1)$ , and any common divisor of both must divide their difference-based combinations down to degree $\le1$ ). Bézout's identity here is nearly immediate: $1\cdot(x^2-1) + (-(x+1))\cdot(x-1) = (x^2-1)-(x^2-1) = 0$ ... more usefully, $(x-1) = 1\cdot(x-1) + 0\cdot(x^2-1)$ , the trivial witness — illustrating that Bézout's identity is guaranteed to exist, though finding an interesting witness generally requires running the Euclidean algorithm (repeated division) explicitly, exactly as in $\mathbb{Z}$ .

05 · Not Every Domain Is a PID

Common mistake — Z[x] is a domain but not a PID

$\mathbb{Z}[x]$ is an integral domain (Corollary 14.3, since $\mathbb{Z}$ is a domain), but consider $I=(2,x) = \{2f(x)+xg(x) : f,g\in\mathbb{Z}[x]\}$ .

Claim: $I$ is not principal. Suppose $I=(h)$ for some $h\in\mathbb{Z}[x]$ . Since $2\in I=(h)$ , $h\mid2$ , so $2=h\cdot k$ for some $k\in\mathbb{Z}[x]$ ; by Theorem 14.2 (domain), $\deg h+\deg k=\deg(2)=0$ , forcing $\deg h=0$ : $h$ is a constant integer, $h\in\{\pm1,\pm2\}$ (the only integer divisors of $2$ ).

If $h=\pm1$ , then $(h)=\mathbb{Z}[x]$ (a unit generates everything). But every element of $I=(2,x)$ has the form $2f(x)+xg(x)$ , whose constant term is $2f(0)$ — always even. So $1\notin I$ (odd constant term), meaning $I\neq\mathbb{Z}[x]$ : contradiction.

If $h=\pm2$ , then $x\in I=(h)$ would require $x=2\cdot j(x)$ for some $j\in\mathbb{Z}[x]$ — impossible, since the coefficient of $x$ on the left is $1$ (odd) but on the right is $2\times(\text{coefficient of }j)$ , always even.

Both cases fail: no such $h$ exists. $I=(2,x)$ is not principal, so $\mathbb{Z}[x]$ is not a PID — even though $\mathbb{Z}$ itself is (it's Euclidean). This is the precise sense in which Chapter 14's $F[x]$ result needed $F$ to be a field, not merely a domain: $\mathbb{Z}$ fails to be a field, and that gap is exactly what breaks $\mathbb{Z}[x]$ 's PID property.

06 · Irreducible and Prime Elements

Definition — Irreducible and Prime Elements

Let $R$ be an integral domain and $p\in R$ nonzero and not a unit. $p$ is irreducible if $p=ab$ implies $a$ or $b$ is a unit (no genuine factorization exists). $p$ is prime if $p\mid ab$ implies $p\mid a$ or $p\mid b$ (equivalently, by Chapter 12, $(p)$ is a prime ideal).

Theorem 15.3 — Prime Implies Irreducible

In any integral domain, every prime element is irreducible.

Proof

Let $p$ be prime and suppose $p=ab$ . Since $p\mid p=ab$ , primality gives $p\mid a$ or $p\mid b$ ; say $p\mid a$ , so $a=pc$ for some $c\in R$ . Then $p=ab=pcb$ . Since $R$ is a domain and $p\neq0$ , cancellation (Theorem 11.5) gives $1=cb$ , so $b\in R^\times$ . Hence $p$ is irreducible (the case $p\mid b$ is symmetric).

Theorem 15.4 — In a PID, Irreducible Implies Prime

In a PID, every irreducible element is prime. (Combined with Theorem 15.3: in a PID, irreducible and prime coincide.)

Proof

Let $p$ be irreducible and suppose $p\mid ab$ . Consider the ideal $(p,a)$ ; since $R$ is a PID, $(p,a)=(d)$ for some $d\in R$ . Since $d\mid p$ (as $p\in(p,a)=(d)$ ) and $p$ is irreducible, either $d$ is a unit or $d$ is an associate of $p$ .

Case $d$ a unit: then $(p,a)=(d)=R$ , so $1\in(p,a)$ , giving $1=rp+sa$ for some $r,s\in R$ (Bézout). Multiply by $b$ : $b = rpb+sab$ . Since $p\mid ab$ (hypothesis) and $p\mid rpb$ (trivially), $p$ divides the right side, so $p\mid b$ .

Case $d$ an associate of $p$ : $d=up$ for a unit $u$ . Since $d\mid a$ (as $a\in(p,a)=(d)$ ), $a=dk=upk$ for some $k$ , so $p\mid a$ .

Either way, $p\mid a$ or $p\mid b$ : $p$ is prime.

Example — Irreducibility of x²+1 over different fields

In $\mathbb{R}[x]$ (a Euclidean domain, hence a PID by Theorem 15.1): $x^2+1$ is irreducible, since any factorization into two degree-1 factors would produce a real root, but $x^2+1$ has none ( $x^2\geq0$ for real $x$ , so $x^2+1\geq1>0$ always). By Theorem 15.4, $x^2+1$ is therefore also prime in $\mathbb{R}[x]$ — a fact that becomes essential in Chapter 18, where $\mathbb{R}[x]/(x^2+1)$ (a quotient by a prime, in fact maximal, ideal) is used to construct $\mathbb{C}$ from $\mathbb{R}$ purely algebraically.

07 · Exercises

EXERCISE 15.1

Recall the standard base- $b$ long division fact from arithmetic — this is exactly the Euclidean property.

For $a=17$ , $b=5$ : $17 = 3\times5+2$ , so $q=3$ , $r=2$ , and $N(r)=\lvert2\rvert=2 < 5=N(b)$ . This is exactly Definition 15's requirement, confirmed directly.

Confirm the Euclidean property of $\mathbb{Z}$ directly for $a=17$ , $b=5$ : find $q,r$ and check $N(r)<N(b)$ .

EXERCISE 15.2

Apply Theorem 15.1: since $\mathbb{Q}[x]$ is Euclidean, every ideal is generated by a single polynomial.

By Theorem 15.1, $I=(x^2-1,x^3-1)$ must equal $(d)$ for a single $d$ . Since $x-1$ divides both generators ( $x^2-1=(x-1)(x+1)$ , $x^3-1=(x-1)(x^2+x+1)$ ), $(x-1) \supseteq I$ . Conversely, $x-1$ is a $\mathbb{Q}$ -linear combination-with-polynomial-coefficients of the two generators (running the Euclidean algorithm on them would exhibit this explicitly), so $x-1\in I$ , giving $I=(x-1)$ .

$\gcd(x^2-1,x^3-1) = x-1$ .

Using Theorem 15.1, argue that $(x^2-1, x^3-1)$ in $\mathbb{Q}[x]$ must be a principal ideal, and identify its generator.

EXERCISE 15.3

Check whether $5$ can be factored nontrivially in $\mathbb{Z}$ , then apply Theorem 15.4 (since $\mathbb{Z}$ is a PID).

$5$ is irreducible in $\mathbb{Z}$ (its only factorizations are $5=1\times5$ or $5=(-1)\times(-5)$ , always involving a unit). Since $\mathbb{Z}$ is a PID (Euclidean, Theorem 15.1), Theorem 15.4 gives: $5$ is also prime in $\mathbb{Z}$ — matching the ordinary number-theoretic meaning of "prime," now derived from the general ring-theoretic machinery.

Using Theorem 15.4, confirm that $5\in\mathbb{Z}$ , already known to be irreducible, is also prime.

EXERCISE 15.4

Follow the exact structure of Section 05's FailBlock, replacing $2$ with $3$ .

By the identical argument to Section 05 (with $2$ replaced by $3$ ): if $(3,x)=(h)$ , degree considerations force $h$ constant, $h\in\{\pm1,\pm3\}$ . $h=\pm1$ fails since every element of $(3,x)$ has constant term divisible by 3, excluding $1$ . $h=\pm3$ fails since $x=3j(x)$ would need the coefficient of $x$ (which is $1$ ) to be a multiple of 3. $(3,x)$ is also not principal — confirming $\mathbb{Z}[x]$ 's failure to be a PID is not special to the prime 2.

Show, following the template of Section 05, that $(3,x)$ is also not a principal ideal of $\mathbb{Z}[x]$ .

08 · Chapter Summary

Concept	Statement
Euclidean domain	Domain with $N: R\setminus\{0\}\to\mathbb{Z}_{\geq0}$ giving division with $N(r)<N(b)$
Examples	$\mathbb{Z}$ ( $N=\lvert\cdot\rvert$ ); $F[x]$ ( $N=\deg$ ); $\mathbb{Z}[i]$ ( $N=$ norm)
PID	Every ideal is principal
Euclidean $\implies$ PID	Thm 15.1, via minimal-norm element of an ideal
GCD in a PID	Generator of $(a,b)$ ; Bézout's identity $ra+sb=\gcd(a,b)$ (Thm 15.2)
$\mathbb{Z}[x]$ is not a PID	$(2,x)$ is not principal — a domain that fails PID
Prime $\implies$ irreducible	Always, in any domain (Thm 15.3)
Irreducible $\implies$ prime	Only guaranteed in a PID (Thm 15.4)

Next: Chapter 16 — Chinese Remainder Theorem applies this chapter's gcd and Bézout machinery to solve simultaneous congruences, generalizing the classical number-theoretic result to arbitrary PIDs (and beyond, to general rings with coprime ideals).