Contents / Abstract Algebra / Polynomial Rings and Unique Factorization

Chapter 7

Polynomial Rings and Unique Factorization

Degrees add over a domain, and what breaks without it; the division algorithm, remainder and factor theorems, and the bound on the number of roots; Euclidean domains are PIDs and PIDs are UFDs, with a separating example at each gap in the containment chain; irreducible and prime coinciding in a PID; and irreducibility testing by Gauss's lemma, the rational root theorem and Eisenstein's criterion.

Introduction

The integers are the ring everybody learns arithmetic in, and the Fundamental Theorem of Arithmetic is the reason that arithmetic is orderly: every integer larger than $1$ is a product of primes in exactly one way. This chapter asks which other rings behave like that, and the answer turns out to be organised by a single short chain of classes,

field \subset Euclidean domain \subset PID \subset UFD \subset integral domain,

each inclusion strict. The chapter's job is to prove the two inclusions in the middle, exhibit a ring separating each pair, and then show that polynomial rings supply the most important examples at every level.

The engine is division with remainder. Given a way to divide and leave something strictly smaller, one gets the Euclidean algorithm; from the Euclidean algorithm one gets that every ideal is generated by a single element; from that one gets that irreducible elements are prime; and from that one gets unique factorization. Each arrow in the chain is a short argument, and every one of them is proved below. What makes the chain worth setting up is that it applies verbatim to $Z$ , to $F [x]$ for any field $F$ , and to the Gaussian integers $Z [i]$ — three rings whose arithmetic looks nothing alike and whose factorization theory is identical.

The other half of the chapter is the practical question the theory leaves open. Unique factorization guarantees that a polynomial over $Q$ has a factorization into irreducibles and that it is essentially unique; it says nothing whatever about how to find it, or how to certify that a given polynomial is one of the atoms. So we develop the working tests: the rational root theorem for linear factors, reduction modulo a prime, and Eisenstein's criterion, which is proved here rather than quoted and then used to produce two infinite families of irreducible polynomials over $Q$ .

Throughout, ring means commutative ring with identity $1 \neq = 0$ , $R^{\times}$ denotes the group of units of $R$ , and $F$ always denotes a field. Familiarity with ideals and quotient rings, as developed in Ideals and Quotient Rings, and with the definition of an integral domain from Integral Domains and Fields, is assumed.

7.1Polynomials over a ring

A polynomial is not a function. This is the first thing to get straight, because the distinction is invisible over $R$ and fatal over a finite ring. Over the field $F_{2} = Z /2 Z$ , the polynomials $x^{2} + x$ and $0$ take the same value at every element of $F_{2}$ , yet they are different elements of $F_{2} [x]$ : one has degree $2$ and the other is the zero polynomial. A polynomial is its sequence of coefficients, and $x$ is a formal symbol subject to no relation at all.

Definition 7.1 (Polynomial ring). Let $R$ be a commutative ring. A polynomial over $R$ is a sequence $(a_{0}, a_{1}, a_{2}, \dots)$ of elements of $R$ with only finitely many $a_{i}$ nonzero, written

f = a_{0} + a_{1} x + a_{2} x^{2} + \dots + a_{n} x^{n} .

Addition is coefficientwise and multiplication is the convolution

(i \sum a_{i} x^{i}) (j \sum b_{j} x^{j}) = k \sum i + j = k \sum a_{i} b_{j} x^{k} .

With these operations the set of all polynomials over $R$ is a commutative ring, the polynomial ring $R [x]$ , containing $R$ as the subring of constant sequences.

Checking the ring axioms is routine and unilluminating; the only one worth a glance is associativity of multiplication, where both $(f g) h$ and $f (g h)$ produce the coefficient $\sum_{i + j + k = n} a_{i} b_{j} c_{k}$ in degree $n$ , visibly symmetric in the three factors.

Definition 7.2 (Degree, leading coefficient, monic). Let $f = a_{0} + a_{1} x + \dots + a_{n} x^{n} \in R [x]$ be nonzero with $a_{n} \neq = 0$ . Its degree is $de g f = n$ , its leading coefficient is $lc (f) = a_{n}$ , and $f$ is monic if $a_{n} = 1$ . The degree of the zero polynomial is left undefined, or set to $- \infty$ where a uniform convention helps.

Notation. We write $de g 0 = - \infty$ whenever it makes a statement uniform, with the conventions $- \infty + n = - \infty$ and $- \infty < n$ for every integer $n$ . This is bookkeeping, not mathematics: it lets $de g (f g) = de g f + de g g$ be stated without a proviso.

The degree is the substitute, in $R [x]$ , for the absolute value on $Z$ : a measure of size that behaves well under multiplication and that cannot decrease forever. Everything in the chapter rests on how exactly it behaves.

Proposition 7.3 (Degree of a sum). For $f, g \in R [x]$ ,

de g (f + g) \leq max (de g f, de g g),

with equality whenever $de g f \neq = de g g$ .

Proof. The coefficient of $x^{k}$ in $f + g$ is $a_{k} + b_{k}$ , which is zero whenever both $a_{k}$ and $b_{k}$ are, so no power above $max (de g f, de g g)$ survives. If $de g f > de g g$ then the coefficient of $x^{d e g f}$ in $f + g$ is $lc (f) + 0 = lc (f) \neq = 0$ , giving equality. Strict inequality is possible only when the degrees agree and the leading coefficients cancel, as in $(x^{2} + x) + (- x^{2} + 1) = x + 1$ .∎

Theorem 7.4 (Degrees add over a domain). Let $R$ be an integral domain and let $f, g \in R [x]$ be nonzero. Then $f g \neq = 0$ ,

de g (f g) = de g f + de g g, lc (f g) = lc (f) lc (g) .

Proof. Write $f = a_{m} x^{m} + \dots$ and $g = b_{n} x^{n} + \dots$ with $a_{m}, b_{n} \neq = 0$ , where the omitted terms have lower degree. By the convolution formula the coefficient of $x^{k}$ in $f g$ is $\sum_{i + j = k} a_{i} b_{j}$ . For $k > m + n$ every term of that sum has $i > m$ or $j > n$ , hence $a_{i} = 0$ or $b_{j} = 0$ , so the coefficient vanishes. For $k = m + n$ the only pair $(i, j)$ with $i + j = k$ , $i \leq m$ and $j \leq n$ is $(m, n)$ , so the coefficient is exactly $a_{m} b_{n}$ .

Now the hypothesis enters: $R$ is a domain and $a_{m}, b_{n}$ are nonzero, so $a_{m} b_{n} \neq = 0$ . Therefore $f g$ has a nonzero coefficient in degree $m + n$ and none above it, which is the claim.∎

The single step that used the hypothesis was $a_{m} b_{n} \neq = 0$ , and without it the theorem is false, not merely unproved.

Example 7.5 (Degrees collapsing over $Z /4 Z$ ). In $(Z /4 Z) [x]$ compute the product of $f = 2 x + 1$ and $g = 2 x + 1$ , and of $f = 2 x$ and $g = 2 x + 3$ . What happens to the degrees?

Solution.

$(2 x + 1)^{2} = 4 x^{2} + 4 x + 1 = 1$ in $(Z /4 Z) [x]$ , since $4 \equiv 0$ . So two polynomials of degree $1$ multiply to a polynomial of degree $0$ : $de g (f g) = 0 \neq = 1 + 1$ .
$(2 x) (2 x + 3) = 4 x^{2} + 6 x = 2 x$ , of degree $1$ rather than $2$ .
The cause in both cases is the zero-divisor pair $2 \cdot 2 = 0$ in $Z /4 Z$ : the leading coefficients multiply to zero and the top term disappears.
Note also what the first computation shows about units: $2 x + 1$ is its own inverse, so $(Z /4 Z) [x]$ has a unit of degree $1$ . Both of the results below therefore genuinely need their hypothesis.

□

Corollary 7.6 ( $R [x]$ is a domain exactly when $R$ is). $R [x]$ is an integral domain if and only if $R$ is.

Proof. ( $\Leftarrow$ ) If $R$ is a domain and $f, g \in R [x]$ are nonzero, then $f g \neq = 0$ by the theorem Degrees add over a domain.

( $\Rightarrow$ ) If $R$ is not a domain, pick nonzero $a, b \in R$ with $ab = 0$ . These are nonzero constant polynomials in $R [x]$ whose product is $0$ , so $R [x]$ is not a domain either. (And $R [x]$ is commutative with $1 \neq = 0$ whenever $R$ is, so no other axiom is in question.)∎

Corollary 7.7 (Units of a polynomial ring over a domain). If $R$ is an integral domain then

R [x]^{\times} = R^{\times},

that is, the only invertible polynomials are the invertible constants.

Proof. A unit of $R$ is certainly a unit of $R [x]$ . Conversely suppose $f g = 1$ with $f, g \in R [x]$ . Both are nonzero, so by the theorem Degrees add over a domain, $de g f + de g g = de g 1 = 0$ . Degrees of nonzero polynomials are non-negative, so $de g f = de g g = 0$ and both are constants; $f g = 1$ then says $f \in R^{\times}$ .∎

Remark. The example Degrees collapsing over $Z /4 Z$ shows the corollary fails without the hypothesis, since $2 x + 1$ is a non-constant unit there. In general $f = a_{0} + \dots + a_{n} x^{n}$ is a unit of $R [x]$ iff $a_{0} \in R^{\times}$ and $a_{1}, \dots, a_{n}$ are all nilpotent — a result we shall not need, but which explains the $Z /4 Z$ example precisely: $2$ is nilpotent there.

Division with remainder

Long division of polynomials needs to divide by the leading coefficient of the divisor. Over a field that is always possible; over a general ring it is possible exactly when that leading coefficient is a unit, and the cleanest statement is the one for a monic divisor.

Theorem 7.8 (Division algorithm). Let $R$ be a commutative ring and let $g \in R [x]$ be monic. For every $f \in R [x]$ there exist unique $q, r \in R [x]$ with

f = q g + r, r = 0 or de g r < de g g .

Proof. Existence, by strong induction on $de g f$ . Let $n = de g g$ . If $f = 0$ or $de g f < n$ , take $q = 0$ and $r = f$ . Otherwise let $m = de g f \geq n$ and suppose the statement holds for every polynomial of degree less than $m$ . Put

f_{1} = f - lc (f) x^{m - n} g .

The subtracted polynomial is monic-times-a-constant of degree exactly $m$ with leading coefficient $lc (f)$ — here is where monicity of $g$ is used, since it makes $lc (x^{m - n} g) = 1$ — so the degree- $m$ terms cancel and $f_{1} = 0$ or $de g f_{1} < m$ . By the inductive hypothesis $f_{1} = q_{1} g + r$ with $r = 0$ or $de g r < n$ , whence

f = (q_{1} + lc (f) x^{m - n}) g + r .

Uniqueness. Suppose $q g + r = q^{'} g + r^{'}$ with both remainders zero or of degree $< n$ . Then $(q - q^{'}) g = r^{'} - r$ . If $q \neq = q^{'}$ then, because $g$ is monic, the left-hand side has degree $de g (q - q^{'}) + n \geq n$ : the leading coefficient of $(q - q^{'}) g$ is $lc (q - q^{'}) \cdot 1 \neq = 0$ , so no collapse is possible even if $R$ has zero-divisors. But the right-hand side is $0$ or of degree $< n$ , a contradiction. Hence $q = q^{'}$ and then $r = r^{'}$ .∎

Corollary 7.9 (Division algorithm in $F [x]$ ). Let $F$ be a field and $f, g \in F [x]$ with $g \neq = 0$ . There are unique $q, r \in F [x]$ with $f = q g + r$ and $r = 0$ or $de g r < de g g$ .

Proof. Let $c = lc (g)$ , which is invertible because $F$ is a field, so $c^{- 1} g$ is monic. By the theorem Division algorithm, $f = q_{0} (c^{- 1} g) + r$ uniquely with $r = 0$ or $de g r < de g (c^{- 1} g) = de g g$ . Set $q = c^{- 1} q_{0}$ . Uniqueness transfers because $q \mapsto c^{- 1} q$ is a bijection of $F [x]$ .∎

Pitfall. Over $Z [x]$ there is no division algorithm. Dividing $f = x^{2}$ by $g = 2 x + 1$ would need $q$ with leading coefficient $\frac{1}{2} \in / Z$ , and indeed no $q, r \in Z [x]$ with $de g r < 1$ satisfy $x^{2} = q (2 x + 1) + r$ : reducing modulo $2$ gives $x^{2} \equiv q (0) \cdot 1 + r (mod 2)$ with the right side of degree $\leq 0$ . The monic case is the whole of what survives, and it is exactly what the theorem Division algorithm asserts.

Example 7.10 (Long division in $Q [x]$ ). Divide $f = 2 x^{4} - 3 x^{3} + x - 5$ by $g = x^{2} - x + 2$ .

Solution.

Leading terms: $2 x^{4} / x^{2} = 2 x^{2}$ . Subtract $2 x^{2} g = 2 x^{4} - 2 x^{3} + 4 x^{2}$ , leaving $- x^{3} - 4 x^{2} + x - 5$ .
Next: $- x^{3} / x^{2} = - x$ . Subtract $- x g = - x^{3} + x^{2} - 2 x$ , leaving $- 5 x^{2} + 3 x - 5$ .
Next: $- 5 x^{2} / x^{2} = - 5$ . Subtract $- 5 g = - 5 x^{2} + 5 x - 10$ , leaving $- 2 x + 5$ .
The remainder $- 2 x + 5$ has degree $1 < 2 = de g g$ , so we stop:

2 x^{4} - 3 x^{3} + x - 5 = (2 x^{2} - x - 5) (x^{2} - x + 2) + (- 2 x + 5) .

Check by expanding: $(2 x^{2} - x - 5) (x^{2} - x + 2) = 2 x^{4} - 3 x^{3} + 3 x - 10$ , and adding $- 2 x + 5$ gives $2 x^{4} - 3 x^{3} + x - 5$ . ✓

□

Definition 7.11 (Evaluation homomorphism). For $a \in R$ , the map $ev_{a} : R [x] \to R$ sending $f = \sum a_{i} x^{i}$ to $f (a) = \sum a_{i} a^{i}$ is a ring homomorphism. An element $a \in R$ with $f (a) = 0$ is a root of $f$ .

That $ev_{a}$ respects multiplication is exactly the commutativity of $R$ : expanding $(f g) (a)$ by the convolution formula and comparing with $f (a) g (a)$ needs $a$ to commute with every coefficient. This is why "substitute a number" is a legitimate algebraic operation and not merely a notational one, and it is the only fact used in the next two results.

Theorem 7.12 (Remainder theorem). Let $R$ be a commutative ring, $f \in R [x]$ and $a \in R$ . The remainder on dividing $f$ by $x - a$ is the constant $f (a)$ :

f = q \cdot (x - a) + f (a) for a unique q \in R [x] .

Proof. $x - a$ is monic of degree $1$ , so the theorem Division algorithm gives unique $q, r$ with $f = q (x - a) + r$ and $r = 0$ or $de g r < 1$ ; either way $r$ is a constant. Apply the homomorphism $ev_{a}$ of the definition Evaluation homomorphism: $f (a) = q (a) (a - a) + r = r$ .∎

Corollary 7.13 (Factor theorem). $a$ is a root of $f$ if and only if $(x - a) ∣ f$ in $R [x]$ .

Proof. By the theorem Remainder theorem, $f = q (x - a) + f (a)$ . If $f (a) = 0$ then $f = q (x - a)$ . Conversely if $f = h (x - a)$ then $f (a) = h (a) \cdot 0 = 0$ .∎

Theorem 7.14 (Root bound over a domain). Let $R$ be an integral domain and let $f \in R [x]$ be nonzero of degree $n$ . Then $f$ has at most $n$ distinct roots in $R$ .

Proof. Induct on $n$ . If $n = 0$ then $f$ is a nonzero constant and has no roots. Suppose $n \geq 1$ and the claim holds below $n$ . If $f$ has no root we are done. Otherwise let $a$ be a root; by the corollary Factor theorem, $f = (x - a) q$ , and by the theorem Degrees add over a domain, $de g q = n - 1$ .

Let $b \neq = a$ be any other root. Then $0 = f (b) = (b - a) q (b)$ , and $b - a \neq = 0$ , so — because $R$ is a domain — $q (b) = 0$ . Hence every root of $f$ other than $a$ is a root of $q$ , of which there are at most $n - 1$ by induction. Counting $a$ itself, $f$ has at most $n$ roots.∎

Example 7.15 (A quadratic with four roots over $Z /8 Z$ ). Find every root of $f = x^{2} - 1$ in $Z /8 Z$ and explain why the theorem Root bound over a domain is not violated.

Solution.

Test all eight residues: $0^{2} = 0$ , $1^{2} = 1$ , $2^{2} = 4$ , $3^{2} = 9 = 1$ , $4^{2} = 16 = 0$ , $5^{2} = 25 = 1$ , $6^{2} = 36 = 4$ , $7^{2} = 49 = 1$ .
So $x^{2} = 1$ for $x \in {1, 3, 5, 7}$ : a degree- $2$ polynomial with four roots.
There is no contradiction because $Z /8 Z$ is not a domain: $2 \cdot 4 = 0$ . The proof breaks exactly at the step " $b - a \neq = 0$ forces $q (b) = 0$ ".
Concretely, $x^{2} - 1 = (x - 1) (x + 1)$ , and at $x = 3$ the two factors are $2$ and $4$ , a pair of nonzero elements whose product is $0$ . The extra roots come from splitting zero, not from splitting the polynomial. ✓

□

Corollary 7.16 (Polynomials and functions agree over an infinite domain). If $R$ is an infinite integral domain and $f, g \in R [x]$ satisfy $f (a) = g (a)$ for all $a \in R$ , then $f = g$ as polynomials.

Proof. $f - g$ has every element of $R$ as a root. If $f - g \neq = 0$ it has finitely many roots by the theorem Root bound over a domain, contradicting $∣ R ∣ = \infty$ . So $f = g$ .∎

This is the precise sense in which the opening warning is a finite phenomenon: over $R$ or $Q$ one may identify a polynomial with the function it defines, and over $F_{2}$ one may not, since $x^{2} + x$ and $0$ induce the same function on a two-element set.

Intuition. Think of $F [x]$ as the integers with the number line replaced by a ruler marked in degrees. "Bigger" means "higher degree"; division with remainder makes the leftover strictly shorter on that ruler; and a ruler with only non-negative integer markings cannot shrink forever. Every theorem in the next two sections is a consequence of that one sentence, applied to whatever ring comes with a suitable ruler.

Exercises for §7.1 →

7.2Euclidean domains

Abstracting the ruler gives the class of rings in which the Euclidean algorithm runs. The definition asks for very little — a size function and a division step — and delivers a surprising amount.

Definition 7.17 (Divisibility, associates, gcd). Let $R$ be a domain and $a, b \in R$ . Say $a ∣ b$ if $b = a c$ for some $c \in R$ ; equivalently $(b) \subseteq (a)$ . Elements $a, b$ are associates if $a = u b$ for a unit $u$ , equivalently $(a) = (b)$ . An element $d$ is a greatest common divisor of $a$ and $b$ if $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ . A gcd, when it exists, is unique up to associates.

The last clause is forced: if $d$ and $d^{'}$ are both gcds then each divides the other, so $d = u d^{'}$ with $u$ a unit. In $Z$ one normalises by taking $d > 0$ ; in $F [x]$ one normalises by taking $d$ monic, using the corollary Units of a polynomial ring over a domain to see that the monic representative is unique.

Definition 7.18 (Euclidean domain). An integral domain $D$ is a Euclidean domain if there is a function $N : D ∖ {0} \to Z_{\geq 0}$ , called a Euclidean function, such that for all $a, b \in D$ with $b \neq = 0$ there exist $q, r \in D$ with

a = q b + r, r = 0 or N (r) < N (b) .

Nothing requires $q$ and $r$ to be unique, and in general they are not — in $Z$ with $N (n) = ∣ n ∣$ one may write $7 = 2 \cdot 3 + 1$ or $7 = 3 \cdot 3 - 2$ , and both are legitimate. Uniqueness is a bonus that $Z$ (with the usual $0 \leq r < ∣ b ∣$ normalisation) and $F [x]$ happen to enjoy; no proof below uses it.

Proposition 7.19 (The standard Euclidean domains). Each of the following is a Euclidean domain.

Any field $F$ , with $N (a) = 0$ for all $a \neq = 0$ .
$Z$ , with $N (n) = ∣ n ∣$ .
$F [x]$ for $F$ a field, with $N (f) = de g f$ .
The Gaussian integers $Z [i] = {a + bi : a, b \in Z}$ , with $N (a + bi) = a^{2} + b^{2}$ .

Proof. (1) Given $a$ and $b \neq = 0$ , write $a = (a b^{- 1}) b + 0$ .

(2) Is the ordinary division algorithm: for $b \neq = 0$ take $q = ⌊ a / b ⌋$ if $b > 0$ (and the corresponding ceiling if $b < 0$ ), so that $0 \leq r < ∣ b ∣$ .

(3) Is the corollary Division algorithm in $F [x]$ .

(4) Given $α, β \in Z [i]$ with $β \neq = 0$ , the quotient $α / β = u + v i$ lies in $Q [i]$ . Choose integers $m, n$ with $∣ u - m ∣ \leq \frac{1}{2}$ and $∣ v - n ∣ \leq \frac{1}{2}$ , and set $q = m + ni$ , $r = α - qβ$ . Since $N$ is multiplicative on $Q [i]$ ,

N (r) = N (β) N (\frac{α}{β} - q) = N (β) ((u - m)^{2} + (v - n)^{2}) \leq N (β) \cdot (\frac{1}{4} + \frac{1}{4}) = \frac{1}{2} N (β) < N (β) .

∎

Method 7.20 (The Euclidean algorithm). To compute a gcd of $a$ and $b \neq = 0$ in a Euclidean domain:

Divide: $a = q_{1} b + r_{1}$ with $r_{1} = 0$ or $N (r_{1}) < N (b)$ .
Replace the pair $(a, b)$ by $(b, r_{1})$ and repeat.
The sizes $N (b) > N (r_{1}) > N (r_{2}) > \dots$ form a strictly decreasing sequence of non-negative integers, so some $r_{k} = 0$ after finitely many steps.
The last nonzero remainder $r_{k - 1}$ is a gcd of $a$ and $b$ . Normalise it (positive in $Z$ , monic in $F [x]$ ).

Correctness of the algorithm is the observation that ${$ common divisors of $a$ and $b} = {$ common divisors of $b$ and $r_{1}}$ , because $r_{1} = a - q_{1} b$ and $a = q_{1} b + r_{1}$ each express one of the pair in terms of the other two. The set of common divisors is therefore unchanged at every step, and at the final step it is the set of divisors of $r_{k - 1}$ .

Figure 7.21. Each division step drops the degree, and a strictly decreasing sequence of non-negative integers must reach zero. Here

g cd (x^{5} - x^{4} + 2 x^{3} - 2 x^{2} + x - 1, x^{4} - 1)

terminates after four steps.

Example 7.22 (The Euclidean algorithm in $Q [x]$ ). Compute $g cd (x^{4} - 1, x^{3} - x^{2} + x - 1)$ in $Q [x]$ , monic.

Solution.

$x^{4} - 1 = (x + 1) (x^{3} - x^{2} + x - 1) + 0 \cdot x^{2} + 0$ . Expanding, $(x + 1) (x^{3} - x^{2} + x - 1) = x^{4} - 1$ exactly, so the first remainder is $0$ .
The algorithm therefore stops at once, and the gcd is the divisor itself, $x^{3} - x^{2} + x - 1$ , already monic.
Sanity check by factoring: $x^{4} - 1 = (x - 1) (x + 1) (x^{2} + 1)$ and $x^{3} - x^{2} + x - 1 = (x - 1) (x^{2} + 1)$ . The common part is $(x - 1) (x^{2} + 1) = x^{3} - x^{2} + x - 1$ . ✓

□

Example 7.23 (Bézout coefficients in $Q [x]$ ). Find $u, v \in Q [x]$ with $u (x^{3} - 2 x + 1) + v (x^{2} - 1) = g cd$ , and identify the gcd.

Solution.

Divide: $x^{3} - 2 x + 1 = x (x^{2} - 1) + (- x + 1)$ .
Divide again: $x^{2} - 1 = (- x - 1) (- x + 1) + 0$ .
The last nonzero remainder is $- x + 1$ ; normalised monic the gcd is $x - 1$ .
Back-substitute from step 1: $- x + 1 = (x^{3} - 2 x + 1) - x (x^{2} - 1)$ , so multiplying by $- 1$ ,

x - 1 = (- 1) (x^{3} - 2 x + 1) + x (x^{2} - 1) .

Check at $x = 2$ : the right side is $- (8 - 4 + 1) + 2 (3) = - 5 + 6 = 1 = 2 - 1$ . ✓

□

Example 7.24 (Division in the Gaussian integers). Divide $α = 11 + 10 i$ by $β = 4 + i$ in $Z [i]$ , producing $q$ and $r$ with $N (r) < N (β)$ .

Solution.

$\frac{α}{β} = \frac{( 11 + 10 i ) ( 4 - i )}{( 4 + i ) ( 4 - i )} = \frac{44 - 11 i + 40 i + 10}{17} = \frac{54 + 29 i}{17}$ .
Numerically $54/17 \approx 3.18$ and $29/17 \approx 1.71$ , so round to $q = 3 + 2 i$ .
$r = α - qβ = (11 + 10 i) - (3 + 2 i) (4 + i) = (11 + 10 i) - (12 + 3 i + 8 i - 2) = (11 + 10 i) - (10 + 11 i) = 1 - i$ .
$N (r) = 1 + 1 = 2 < 17 = N (β)$ , as required by the definition Euclidean domain. ✓

□

Theorem 7.25 (Every Euclidean domain is a PID). Let $D$ be a Euclidean domain with Euclidean function $N$ . Then every ideal of $D$ is principal.

Proof. Let $I \subseteq D$ be an ideal. If $I = {0}$ then $I = (0)$ and we are done. Otherwise the set ${N (a) : a \in I, a \neq = 0}$ is a nonempty set of non-negative integers, so by well-ordering it has a least element; choose $d \in I ∖ {0}$ attaining it.

Certainly $(d) \subseteq I$ , since $I$ is an ideal containing $d$ . For the reverse, take any $a \in I$ and divide: $a = q d + r$ with $r = 0$ or $N (r) < N (d)$ . Now $r = a - q d$ is a difference of elements of $I$ , hence $r \in I$ . If $r \neq = 0$ then $N (r) < N (d)$ contradicts the minimality of $N (d)$ among nonzero elements of $I$ . So $r = 0$ and $a = q d \in (d)$ .

Therefore $I = (d)$ .∎

The proof is worth rereading, because it is the template for the whole subject: a size function that strictly drops, plus well-ordering of $Z_{\geq 0}$ , forces a minimal element to generate everything.

Corollary 7.26 (Bézout's identity). In a Euclidean domain, any $a, b$ not both zero have a gcd $d$ , and $d = u a + v b$ for some $u, v \in D$ .

Proof. The set $I = (a, b) = {u a + v b : u, v \in D}$ is an ideal, so by the theorem Every Euclidean domain is a PID it equals $(d)$ for some $d$ , and $d \in I$ gives the representation $d = u a + v b$ . Since $a, b \in (d)$ , $d$ is a common divisor. If $c ∣ a$ and $c ∣ b$ then $c ∣ u a + v b = d$ , so $d$ is a greatest common divisor in the sense of the definition Divisibility, associates, gcd.∎

Pitfall. Bézout's identity is a statement about ideals, not about the Euclidean algorithm, and it fails in rings with gcds but no Bézout property. In $Z [x]$ the polynomials $2$ and $x$ have gcd $1$ , yet $1 \neq = 2 u + xv$ for any $u, v \in Z [x]$ — evaluate at $x = 0$ and reduce mod $2$ . So "gcd exists" is strictly weaker than "gcd is a linear combination".

Corollary 7.27 ( $F [x]$ is a principal ideal domain). For any field $F$ , every ideal of $F [x]$ is principal, generated by $0$ or by the unique monic polynomial of least degree in it.

Proof. $F [x]$ is Euclidean by the proposition The standard Euclidean domains, hence a PID by the theorem Every Euclidean domain is a PID, whose proof selects a nonzero element of least degree as generator. Scaling by the inverse of its leading coefficient makes it monic without changing the ideal, and two monic generators of the same ideal are associates by the definition Divisibility, associates, gcd, hence equal by the corollary Units of a polynomial ring over a domain.∎

Exercises for §7.2 →

7.3Principal ideal domains and unique factorization

We now have one implication of the chain. This section proves the second, and separates all the classes by example.

Definition 7.28 (Principal ideal domain). An integral domain $R$ is a principal ideal domain (PID) if every ideal of $R$ is of the form $(a) = a R$ for some $a \in R$ .

Definition 7.29 (Irreducible and prime). Let $R$ be a domain and $p \in R$ nonzero and not a unit.

$p$ is irreducible if $p = ab$ implies $a$ or $b$ is a unit.
$p$ is prime if $p ∣ ab$ implies $p ∣ a$ or $p ∣ b$ ; equivalently, $(p)$ is a nonzero prime ideal.

The two conditions say different things. Irreducibility is about factoring $p$ ; primality is about what $p$ divides. In $Z$ they famously coincide, and Euclid's lemma — the assertion that they coincide — is precisely the hard input to the Fundamental Theorem of Arithmetic. In general only one direction is free.

Proposition 7.30 (Prime implies irreducible). In any integral domain, every prime element is irreducible.

Proof. Let $p$ be prime and suppose $p = ab$ . Then $p ∣ ab$ , so $p ∣ a$ or $p ∣ b$ ; say $a = p c$ . Then $p = p c b$ , and cancelling $p$ (legitimate in a domain, as $p \neq = 0$ ) gives $1 = c b$ , so $b$ is a unit. The other case is symmetric.∎

Example 7.31 (An irreducible element that is not prime). In $R = Z [- 5] = {a + b - 5 : a, b \in Z}$ , show that $2$ is irreducible but not prime.

Solution.

Use the norm $N (a + b - 5) = a^{2} + 5 b^{2}$ , which is multiplicative and takes non-negative integer values, with $N (α) = 1$ exactly for the units $\pm 1$ .
If $2 = α β$ then $4 = N (α) N (β)$ . A factor of norm $2$ would need $a^{2} + 5 b^{2} = 2$ , impossible over the integers ( $b = 0$ forces $a^{2} = 2$ ). So ${N (α), N (β)} = {1, 4}$ and one of them is a unit: $2$ is irreducible.
But $2 ∣ 6 = (1 + - 5) (1 - - 5)$ , while $2 ∤ 1 \pm - 5$ : dividing would give $\frac{1}{2} \pm \frac{1}{2} - 5 \in / R$ . So $2$ is not prime.
Consequently $6 = 2 \cdot 3 = (1 + - 5) (1 - - 5)$ are two genuinely different factorizations into irreducibles, and $Z [- 5]$ is a domain that is not a UFD. ✓

□

Theorem 7.32 (In a PID irreducible implies prime). Let $R$ be a PID and $p \in R$ irreducible. Then $p$ is prime. Hence in a PID the irreducible elements are exactly the prime elements.

Proof. Suppose $p ∣ ab$ and $p ∤ a$ ; we show $p ∣ b$ . Consider the ideal $(p, a)$ . Since $R$ is a PID, $(p, a) = (d)$ for some $d$ . Then $d ∣ p$ , so $p = d e$ and irreducibility forces $d$ or $e$ to be a unit.

If $e$ is a unit then $(d) = (p)$ , so $a \in (p)$ , i.e. $p ∣ a$ — excluded. Hence $d$ is a unit and $(p, a) = R$ . Write $1 = u p + v a$ for some $u, v \in R$ and multiply by $b$ :

b = u p b + v ab .

Both terms on the right are divisible by $p$ : the first visibly, the second because $p ∣ ab$ . So $p ∣ b$ . The converse direction is the proposition Prime implies irreducible.∎

Corollary 7.33 (Maximality of nonzero prime ideals). In a PID $R$ , every nonzero prime ideal is maximal. Consequently, for $p$ irreducible, $R / (p)$ is a field.

Proof. Let $(p)$ be a nonzero prime ideal, so $p$ is prime, hence irreducible by the proposition Prime implies irreducible. Suppose $(p) \subseteq (d) \subseteq R$ . Then $d ∣ p$ , so $p = d e$ with $d$ or $e$ a unit; correspondingly $(d) = R$ or $(d) = (p)$ . Thus no ideal sits strictly between $(p)$ and $R$ , which is maximality, and a quotient by a maximal ideal is a field.∎

Applied to $F [x]$ , which is a PID by the corollary $F [x]$ is a principal ideal domain, this is the construction that produces every field extension in Galois Theory: $F [x] / (p)$ is a field containing a root of $p$ , namely the class of $x$ .

Definition 7.34 (Unique factorization domain). An integral domain $R$ is a unique factorization domain (UFD) if every nonzero non-unit $a \in R$ can be written

a = p_{1} p_{2} \dots p_{k}

with each $p_{i}$ irreducible, and this is unique in the following sense: if $a = q_{1} \dots q_{ℓ}$ is another such factorization then $k = ℓ$ and, after reordering, $p_{i}$ and $q_{i}$ are associates for each $i$ .

Proving that a ring is a UFD splits into two genuinely separate tasks, and it is worth naming them because they fail independently. Existence asks that the factoring process terminate; uniqueness asks that the atoms be prime. The first is where the Noetherian condition enters.

Lemma 7.35 (Ascending chain condition on principal ideals). Let $R$ be a PID and let $(a_{1}) \subseteq (a_{2}) \subseteq (a_{3}) \subseteq \dots$ be an ascending chain of ideals. Then the chain stabilises: there is $n$ with $(a_{n}) = (a_{n + 1}) = \dots$ .

Proof. Put $I = ⋃_{k \geq 1} (a_{k})$ . This is an ideal: it is closed under addition because the chain is totally ordered by inclusion, so any two elements lie in a common $(a_{k})$ , and it is closed under multiplication by $R$ because each $(a_{k})$ is.

Since $R$ is a PID, $I = (d)$ for some $d$ . As $d \in I$ , we have $d \in (a_{n})$ for some $n$ . Then for every $m \geq n$ ,

(d) \subseteq (a_{n}) \subseteq (a_{m}) \subseteq I = (d),

so all these ideals are equal and the chain is constant from $n$ onwards.∎

Theorem 7.36 (Every PID is a UFD). Every principal ideal domain is a unique factorization domain.

Proof. Existence. Call $a$ bad if it is a nonzero non-unit with no factorization into irreducibles. Suppose $a_{1}$ is bad. Then $a_{1}$ is not itself irreducible, so $a_{1} = b c$ with $b, c$ both non-units. If both $b$ and $c$ factored into irreducibles, so would $a_{1}$ ; hence at least one is bad — call it $a_{2}$ . Since $a_{1} = a_{2} \cdot (non-unit)$ , we get $(a_{1}) ⊊ (a_{2})$ : the inclusion holds as $a_{2} ∣ a_{1}$ , and it is strict because equality would make the cofactor a unit. Iterating produces a strictly ascending chain

(a_{1}) ⊊ (a_{2}) ⊊ (a_{3}) ⊊ \dots

which contradicts the lemma Ascending chain condition on principal ideals. So no bad element exists: every nonzero non-unit factors into irreducibles.

Uniqueness. Suppose $p_{1} \dots p_{k} = q_{1} \dots q_{ℓ}$ with all factors irreducible, and induct on $k$ . If $k = 0$ the left side is a unit, forcing $ℓ = 0$ (an irreducible never divides a unit). For $k \geq 1$ : $p_{1}$ is irreducible, hence prime by the theorem In a PID irreducible implies prime, and $p_{1} ∣ q_{1} \dots q_{ℓ}$ , so $p_{1} ∣ q_{j}$ for some $j$ ; reorder so $j = 1$ . Write $q_{1} = p_{1} u$ . Since $q_{1}$ is irreducible and $p_{1}$ is not a unit, $u$ is a unit, so $p_{1}$ and $q_{1}$ are associates. Cancel $p_{1}$ from both sides (valid in a domain):

p_{2} \dots p_{k} = u q_{2} \dots q_{ℓ},

and absorb $u$ into $q_{2}$ , which remains irreducible. By induction $k - 1 = ℓ - 1$ and the remaining factors match up to associates and order.∎

Remark. Existence used only the ascending chain condition and uniqueness used only "irreducible $\Rightarrow$ prime". Splitting the proof this way is not decoration: a domain satisfying ACCP in which some irreducible is not prime — $Z [- 5]$ , by the example An irreducible element that is not prime — has factorizations that terminate but do not match. Conversely, there are domains in which irreducibles are prime but factorizations never terminate, such as the ring of all algebraic integers, where $2 = 2 \cdot 2 = 42^{4} = \dots$ has no irreducible factors at all.

Corollary 7.37 (Factorization in $F [x]$ ). For any field $F$ , $F [x]$ is a UFD, and every nonzero $f \in F [x]$ has a unique expression

f = c p_{1}^{e_{1}} \dots p_{k}^{e_{k}}

with $c \in F^{\times}$ , the $p_{i}$ distinct monic irreducibles and $e_{i} \geq 1$ .

Proof. $F [x]$ is a PID by the corollary $F [x]$ is a principal ideal domain, hence a UFD by the theorem Every PID is a UFD. To get the normalised form, factor $f$ into irreducibles, divide each irreducible factor by its leading coefficient to make it monic, and collect the resulting constants into $c$ ; by the corollary Units of a polynomial ring over a domain the units of $F [x]$ are exactly the constants $F^{\times}$ , so this is the only freedom available, and gathering equal factors gives the exponents.∎

Proposition 7.38 ( $Z [x]$ is a UFD that is not a PID). The ideal $(2, x) \subseteq Z [x]$ is not principal. Hence $Z [x]$ is a UFD (by Gauss's theorem, below) which is not a PID.

Proof. First identify the ideal: $2 f + xg$ has constant term $2 f (0)$ , which is even, and conversely a polynomial with even constant term $2 c + x \cdot h$ lies in $(2, x)$ . So $(2, x)$ is exactly the set of polynomials with even constant term; in particular $1 \in / (2, x)$ , so it is a proper ideal.

Suppose $(2, x) = (d)$ . Then $d ∣ 2$ , and since degrees add over the domain $Z$ (the theorem Degrees add over a domain), $de g d \leq de g 2 = 0$ , so $d$ is a constant, $d \in {\pm 1, \pm 2}$ .

If $d = \pm 1$ then $(d) = Z [x] \neq = (2, x)$ .
If $d = \pm 2$ then every element of $(d)$ has all coefficients even, yet $x \in (2, x)$ does not.

Both cases are impossible, so $(2, x)$ is not principal.∎

Theorem 7.39 (The factorization hierarchy). For integral domains,

field ⊊ Euclidean domain ⊊ PID ⊊ UFD ⊊ domain,

and each inclusion is strict:

$Z$ is Euclidean but not a field.
$Z [\frac{1 + - 19}{2}]$ is a PID that admits no Euclidean function.
$Z [x]$ is a UFD that is not a PID.
$Z [- 5]$ is a domain that is not a UFD.

Proof. The inclusions are the proposition The standard Euclidean domains (a field is Euclidean), the theorem Every Euclidean domain is a PID, the theorem Every PID is a UFD, and the definition of a UFD.

For strictness: (1) $2$ has no inverse in $Z$ , and $Z$ is Euclidean. (3) is the proposition $Z [x]$ is a UFD that is not a PID. (4) is the example An irreducible element that is not prime, where $6$ has two inequivalent factorizations. Claim (2) is quoted rather than proved: the argument shows this ring has no universal side divisor, a feature every Euclidean domain that is not a field must possess, and the verification is a finite but fiddly computation with the norm $N (a + b \frac{1 + - 19}{2}) = a^{2} + ab + 5 b^{2}$ .∎

Figure 7.40. The classes nest strictly, and each gap is witnessed by a concrete ring.

Intuition. Read the picture from the inside out as a story about what you are allowed to do. In the innermost ring you can divide with remainder, so you can compute. One ring out you can still solve $u a + v b = g cd$ , but only by knowing an ideal has a generator, not by finding it. One further out you can still factor uniquely, but gcds are no longer linear combinations. Outside everything, "factor" stops meaning anything definite: $6$ is $2 \cdot 3$ and it is $(1 + - 5) (1 - - 5)$ , and nothing adjudicates between them.

Example 7.41 (Ideals of $F [x]$ and their generators). In $Q [x]$ , describe the ideal $I = (x^{3} - 1, x^{2} + x - 2)$ by a single generator.

Solution.

By the corollary $F [x]$ is a principal ideal domain, $I = (d)$ where $d$ is the monic gcd of the two generators.
Euclid: $x^{3} - 1 = (x - 1) (x^{2} + x - 2) + (3 x - 3)$ , since $(x - 1) (x^{2} + x - 2) = x^{3} - 3 x + 2$ and $x^{3} - 1 - (x^{3} - 3 x + 2) = 3 x - 3$ .
Next: $x^{2} + x - 2 = (\frac{x}{3} + \frac{2}{3}) (3 x - 3) + 0$ , since $(x + 2) (x - 1) = x^{2} + x - 2$ .
The last nonzero remainder is $3 x - 3$ , monic normalisation $x - 1$ . So $I = (x - 1)$ .
Check: $x^{3} - 1 = (x - 1) (x^{2} + x + 1)$ and $x^{2} + x - 2 = (x - 1) (x + 2)$ , both in $(x - 1)$ ; and $x - 1 = \frac{1}{3} [(x^{3} - 1) - (x - 1) (x^{2} + x - 2)] \in I$ . ✓

□

Exercises for §7.3 →

7.4Irreducibility over $Q$

$Q [x]$ is a UFD, so every rational polynomial factors uniquely into irreducibles. Finding that factorization is another matter, and the difficulty is that $Q$ is infinite: one cannot search. The strategy of this section is to push every question down to $Z$ , where one can.

Definition 7.42 (Content and primitive polynomials). For a nonzero $f = a_{0} + a_{1} x + \dots + a_{n} x^{n} \in Z [x]$ , the content $c (f)$ is $g cd (a_{0}, \dots, a_{n})$ , taken positive. $f$ is primitive if $c (f) = 1$ , that is, no prime divides every coefficient.

Every nonzero $f \in Z [x]$ is $c (f)$ times a primitive polynomial, and every nonzero $g \in Q [x]$ is a positive rational multiple of a primitive integer polynomial: clear denominators by the lcm, then pull out the content. That primitive polynomial is unique up to sign.

Lemma 7.43 (Gauss's lemma). The product of two primitive polynomials in $Z [x]$ is primitive. Equivalently, $c (f g) = c (f) c (g)$ for all nonzero $f, g \in Z [x]$ .

Proof. Let $f, g$ be primitive and suppose $f g$ is not, so some prime $p$ divides every coefficient of $f g$ . Reduce coefficients modulo $p$ : the reduction map $Z [x] \to F_{p} [x]$ is a ring homomorphism, and it sends $f g$ to $0$ . Hence $\overset{ˉ}{f} \overset{g}{ˉ} = 0$ in $F_{p} [x]$ .

But $F_{p}$ is a field, so $F_{p} [x]$ is an integral domain by the corollary $R [x]$ is a domain exactly when $R$ is. Therefore $\overset{ˉ}{f} = 0$ or $\overset{g}{ˉ} = 0$ , that is, $p$ divides every coefficient of $f$ or every coefficient of $g$ — contradicting primitivity of both.

For the general statement write $f = c (f) f_{0}$ and $g = c (g) g_{0}$ with $f_{0}, g_{0}$ primitive. Then $f g = c (f) c (g) f_{0} g_{0}$ with $f_{0} g_{0}$ primitive, so $c (f g) = c (f) c (g)$ .∎

Theorem 7.44 (Gauss's theorem: irreducibility over $Z$ and over $Q$ ). Let $f \in Z [x]$ be primitive of degree $\geq 1$ . Then $f$ is irreducible in $Z [x]$ if and only if it is irreducible in $Q [x]$ .

Consequently, if $f$ factors over $Q$ as a product of polynomials of degrees $d_{1}, d_{2}$ , it already factors over $Z$ into integer polynomials of those same degrees.

Proof. ( $\Leftarrow$ ) If $f$ is irreducible over $Q$ then any factorization $f = g h$ in $Z [x]$ has $g$ or $h$ a rational constant, hence an integer constant dividing the content $c (f) = 1$ , hence $\pm 1$ : a unit of $Z [x]$ .

( $\Rightarrow$ ) Suppose $f = G H$ with $G, H \in Q [x]$ of degree $\geq 1$ . Write $G = αg$ and $H = β h$ with $g, h \in Z [x]$ primitive of the same degrees and $α, β \in Q_{> 0}$ . Then $f = α β g h$ . Write $α β = u / v$ in lowest terms, so $v f = u g h$ . Taking contents and using the lemma Gauss's lemma, $v c (f) = u c (g h) = u$ , and $c (f) = 1$ gives $u = v$ , so $α β = 1$ and

f = g h

is a factorization in $Z [x]$ into factors of degree $\geq 1$ , neither of which is a unit. So $f$ is reducible over $Z$ . The contrapositive is the claim, and the displayed identity is the "consequently" clause.∎

Remark. The same argument, run over an arbitrary UFD $R$ with fraction field $K$ , proves Gauss's theorem for UFDs: if $R$ is a UFD then so is $R [x]$ . Taking $R = Z$ gives that $Z [x]$ is a UFD, which is the half of the proposition $Z [x]$ is a UFD that is not a PID we did not prove there; iterating gives that $Z [x_{1}, \dots, x_{n}]$ and $F [x_{1}, \dots, x_{n}]$ are UFDs, though for $n \geq 2$ they are not PIDs, since $(x_{1}, x_{2})$ is not principal.

Proposition 7.45 (Low-degree irreducibility test). Let $F$ be a field and $f \in F [x]$ with $de g f \in {2, 3}$ . Then $f$ is irreducible over $F$ if and only if $f$ has no root in $F$ .

Proof. If $f$ has a root $a$ then $(x - a) ∣ f$ by the corollary Factor theorem, and the cofactor has degree $1$ or $2$ , so neither factor is a unit and $f$ is reducible. Conversely, if $f = g h$ nontrivially then $de g g + de g h = de g f \leq 3$ with both degrees $\geq 1$ , so one of them is $1$ , say $g = a x + b$ with $a \neq = 0$ ; then $- b / a$ is a root of $g$ and hence of $f$ .∎

Pitfall. The test is false from degree $4$ onwards. $x^{4} + 2 x^{2} + 1 = (x^{2} + 1)^{2}$ has no real root and is reducible over $R$ ; $x^{4} + 4$ has no rational root and is reducible over $Q$ , as the example A rootless quartic that still factors shows. "No roots" only rules out linear factors.

Theorem 7.46 (Rational root theorem). Let $f = a_{n} x^{n} + \dots + a_{1} x + a_{0} \in Z [x]$ with $a_{n} \neq = 0$ and $a_{0} \neq = 0$ . If $p / q \in Q$ is a root written in lowest terms, then $p ∣ a_{0}$ and $q ∣ a_{n}$ .

Proof. Substitute and clear denominators: $a_{n} p^{n} + a_{n - 1} p^{n - 1} q + \dots + a_{1} p q^{n - 1} + a_{0} q^{n} = 0$ . Every term except the last is divisible by $p$ , so $p ∣ a_{0} q^{n}$ ; since $g cd (p, q) = 1$ we have $g cd (p, q^{n}) = 1$ , so $p ∣ a_{0}$ . Symmetrically, every term except the first is divisible by $q$ , so $q ∣ a_{n} p^{n}$ and hence $q ∣ a_{n}$ .∎

Example 7.47 (Ruling out rational roots). Show that $f = 3 x^{3} - 5 x^{2} + 5 x - 2$ has exactly one rational root, and find it.

Solution.

By the theorem Rational root theorem, any rational root $p / q$ has $p ∣ 2$ and $q ∣ 3$ , so the candidates are $\pm 1, \pm 2, \pm \frac{1}{3}, \pm \frac{2}{3}$ — twelve in all, eight of them distinct from the integers listed.
$f (1) = 3 - 5 + 5 - 2 = 1 \neq = 0$ ; $f (- 1) = - 3 - 5 - 5 - 2 = - 15$ ; $f (2) = 24 - 20 + 10 - 2 = 12$ ; $f (- 2) = - 24 - 20 - 10 - 2 = - 56$ .
$f (2/3) = 3 \cdot \frac{8}{27} - 5 \cdot \frac{4}{9} + \frac{10}{3} - 2 = \frac{8}{9} - \frac{20}{9} + \frac{30}{9} - \frac{18}{9} = 0$ . ✓
So $(3 x - 2) ∣ f$ ; dividing gives $f = (3 x - 2) (x^{2} - x + 1)$ . The quadratic has discriminant $1 - 4 = - 3 < 0$ , so no real, hence no rational, root; by the proposition Low-degree irreducibility test it is irreducible over $Q$ .
The unique rational root is therefore $x = 2/3$ , and the full factorization over $Q$ is $(3 x - 2) (x^{2} - x + 1)$ .

□

Theorem 7.48 (Eisenstein's criterion). Let $f = a_{n} x^{n} + \dots + a_{1} x + a_{0} \in Z [x]$ with $n \geq 1$ , and suppose there is a prime $p$ with

p ∤ a_{n}, p ∣ a_{i} for 0 \leq i \leq n - 1, p^{2} ∤ a_{0} .

Then $f$ is irreducible over $Q$ . If in addition $f$ is primitive, it is irreducible over $Z$ .

Proof. Suppose $f$ is reducible over $Q$ . We may assume $f$ primitive (dividing by the content changes neither the hypotheses, since $p ∤ a_{n}$ means $p ∤ c (f)$ , nor irreducibility over $Q$ ), so by the theorem Gauss's theorem: irreducibility over $Z$ and over $Q$ we may write

f = g h, g = b_{r} x^{r} + \dots + b_{0}, h = c_{s} x^{s} + \dots + c_{0},

with $g, h \in Z [x]$ and $r, s \geq 1$ , $r + s = n$ .

Reduce modulo $p$ . All coefficients of $f$ except the top one are divisible by $p$ , so in $F_{p} [x]$

\overset{g}{ˉ} \overset{ˉ}{h} = \overset{ˉ}{f} = \overset{a}{ˉ}_{n} x^{n}, \overset{a}{ˉ}_{n} \neq = 0.

Now $F_{p} [x]$ is a UFD by the corollary Factorization in $F [x]$ , and $x$ is irreducible there, so the only monic irreducible dividing $\overset{a}{ˉ}_{n} x^{n}$ is $x$ . Hence $\overset{g}{ˉ}$ and $\overset{ˉ}{h}$ are constants times powers of $x$ . Their degrees multiply out correctly only if $\overset{g}{ˉ} = \overset{ˉ}{b}_{r} x^{r}$ and $\overset{ˉ}{h} = \overset{c}{ˉ}_{s} x^{s}$ — in particular, since $r, s \geq 1$ , both $\overset{g}{ˉ}$ and $\overset{ˉ}{h}$ have zero constant term:

p ∣ b_{0} and p ∣ c_{0} .

But $a_{0} = b_{0} c_{0}$ , so $p^{2} ∣ a_{0}$ , contradicting the hypothesis. Therefore $f$ is irreducible over $Q$ , and for primitive $f$ the theorem Gauss's theorem: irreducibility over $Z$ and over $Q$ transfers this to $Z [x]$ .∎

Corollary 7.49 ( $x^{n} - a$ for squarefree-witnessed $a$ ). For every $n \geq 1$ the polynomial $x^{n} - 2$ is irreducible over $Q$ . More generally $x^{n} - a$ is irreducible over $Q$ whenever some prime $p$ satisfies $p ∣ a$ and $p^{2} ∤ a$ .

Proof. Apply the theorem Eisenstein's criterion with that prime $p$ . The leading coefficient is $1$ , so $p ∤ a_{n}$ . The middle coefficients $a_{1}, \dots, a_{n - 1}$ are all $0$ , which every prime divides. The constant term is $- a$ , and $p ∣ a$ with $p^{2} ∤ a$ . All three conditions hold, so $x^{n} - a$ is irreducible. For $x^{n} - 2$ take $p = 2$ .∎

This single corollary produces, for each $n$ , a rational polynomial of degree $n$ with no rational factorization — so $Q [x]$ has irreducibles of every degree, in sharp contrast with $C [x]$ , where the Fundamental Theorem of Algebra leaves only degree $1$ , and with $R [x]$ , where only degrees $1$ and $2$ occur.

Corollary 7.50 (The cyclotomic polynomial $Φ_{p}$ is irreducible). For $p$ prime,

Φ_{p} (x) = \frac{x ^{p} - 1}{x - 1} = x^{p - 1} + x^{p - 2} + \dots + x + 1

is irreducible over $Q$ .

Proof. Eisenstein does not apply to $Φ_{p}$ directly — every coefficient is $1$ . The trick is that irreducibility is preserved by the substitution $x \mapsto x + 1$ , since $f (x) \mapsto f (x + 1)$ is a ring automorphism of $Q [x]$ (its inverse is $x \mapsto x - 1$ ), and an automorphism carries factorizations to factorizations. So it suffices to prove $Φ_{p} (x + 1)$ irreducible.

Compute, using the binomial theorem:

Φ_{p} (x + 1) = \frac{( x + 1 ) ^{p} - 1}{x} = \frac{1}{x} k = 1 \sum p (k p) x^{k} = k = 1 \sum p (k p) x^{k - 1} = x^{p - 1} + (p - 1 p) x^{p - 2} + \dots + (2 p) x + p .

Apply the theorem Eisenstein's criterion with this same prime $p$ . The leading coefficient is $1$ , not divisible by $p$ . For $1 \leq k \leq p - 1$ the binomial coefficient $(k p) = \frac{p !}{k ! ( p - k )!}$ is divisible by $p$ , because $p$ divides the numerator and, being prime and larger than every factor in $k! (p - k)!$ , divides no part of the denominator. The constant term is $(1 p) = p$ , which is divisible by $p$ but not by $p^{2}$ . Eisenstein applies, so $Φ_{p} (x + 1)$ — and therefore $Φ_{p}$ — is irreducible over $Q$ .∎

Example 7.51 (Eisenstein after a shift). Decide whether $f = x^{4} + 1$ is irreducible over $Q$ .

Solution.

Eisenstein fails for $f$ itself: the only candidate prime must divide the constant term $1$ , and no prime does.
Substitute $x \mapsto x + 1$ : $(x + 1)^{4} + 1 = x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 2$ .
Take $p = 2$ : it does not divide the leading coefficient $1$ ; it divides $4, 6, 4$ and $2$ ; and $4 = 2^{2}$ does not divide the constant term $2$ .
By the theorem Eisenstein's criterion, $(x + 1)^{4} + 1$ is irreducible over $Q$ , hence so is $x^{4} + 1$ .
Remark for contrast: $x^{4} + 1$ factors modulo every prime, so the reduction test of the proposition Reduction modulo a prime could never have settled this. ✓

□

Proposition 7.52 (Reduction modulo a prime). Let $f \in Z [x]$ have degree $n$ and let $p$ be a prime with $p ∤ lc (f)$ . If the reduction $\overset{ˉ}{f} \in F_{p} [x]$ is irreducible, then $f$ is irreducible over $Q$ .

Proof. Suppose $f = g h$ over $Q$ with both factors of degree $\geq 1$ ; by the theorem Gauss's theorem: irreducibility over $Z$ and over $Q$ we may take $g, h \in Z [x]$ of the same degrees. Reducing, $\overset{ˉ}{f} = \overset{g}{ˉ} \overset{ˉ}{h}$ . Since $p ∤ lc (f) = lc (g) lc (h)$ , neither leading coefficient dies, so $de g \overset{g}{ˉ} = de g g \geq 1$ and likewise for $\overset{ˉ}{h}$ . That exhibits $\overset{ˉ}{f}$ as a product of two non-units, contradicting its irreducibility.∎

Pitfall. The converse is false in both directions one might hope for. $\overset{ˉ}{f}$ reducible says nothing: $x^{2} + 1$ is irreducible over $Q$ but factors as $(x + 1)^{2}$ mod $2$ . And the hypothesis $p ∤ lc (f)$ cannot be dropped: $2 x^{2} + x$ has degree $2$ but reduces mod $2$ to the irreducible $x$ .

Example 7.53 (Irreducibility by reduction mod 2). Show $f = x^{4} + x + 1 \in Z [x]$ is irreducible over $Q$ .

Solution.

Work in $F_{2} [x]$ , where $\overset{ˉ}{f} = x^{4} + x + 1$ .
Roots: $\overset{ˉ}{f} (0) = 1$ and $\overset{ˉ}{f} (1) = 1 + 1 + 1 = 1$ . No roots, so no linear factor.
The only irreducible quadratic over $F_{2}$ is $x^{2} + x + 1$ (the other three monic quadratics $x^{2}, x^{2} + 1 = (x + 1)^{2}, x^{2} + x = x (x + 1)$ all factor). So the only possible factorization into two quadratics is $(x^{2} + x + 1)^{2} = x^{4} + x^{2} + 1 \neq = \overset{ˉ}{f}$ .
Hence $\overset{ˉ}{f}$ is irreducible over $F_{2}$ , and by the proposition Reduction modulo a prime — with $p = 2 ∤ 1 = lc (f)$ — $f$ is irreducible over $Q$ . ✓

□

Example 7.54 (A rootless quartic that still factors). Factor $x^{4} + 4$ into irreducibles over $Q$ .

Solution.

$x^{4} + 4 > 0$ for every real $x$ , so there is no real root and hence no rational root: no linear factor.
But degree $4$ admits a factorization into two quadratics, so the proposition Low-degree irreducibility test does not apply. Complete the square:

x^{4} + 4 = (x^{2} + 2)^{2} - 4 x^{2} = (x^{2} + 2 x + 2) (x^{2} - 2 x + 2) .

Each factor has discriminant $4 - 8 = - 4 < 0$ , so has no rational root and is irreducible by the proposition Low-degree irreducibility test.
So the factorization into irreducibles over $Q$ is $(x^{2} + 2 x + 2) (x^{2} - 2 x + 2)$ , and $x^{4} + 4$ is the standing warning that "no roots" is not "irreducible". ✓

□

Figure 7.55. Unique factorization as a tree: every route down from the root ends in the same multiset of irreducibles.

Exercises for §7.4 →

7.5Quotients, finite fields and counting irreducibles

Every result so far pays off in one construction: killing an irreducible polynomial to manufacture a field in which it has a root. This section makes that concrete and then counts how many irreducibles there are to kill.

Theorem 7.56 (Structure of $F [x] / (f)$ ). Let $F$ be a field and $f \in F [x]$ of degree $n \geq 1$ . Then every class in $F [x] / (f)$ has exactly one representative of degree $< n$ , so

F [x] / (f) = {\overline{r} : r \in F [x], r = 0 or de g r < n}

is an $F$ -vector space of dimension $n$ with basis $1, \overset{x}{ˉ}, \dots, \overset{x}{ˉ}^{n - 1}$ . If $F$ is finite with $q$ elements, $∣ F [x] / (f) ∣ = q^{n}$ .

Proof. Given $g \in F [x]$ , the corollary Division algorithm in $F [x]$ produces unique $q, r$ with $g = q f + r$ and $r = 0$ or $de g r < n$ ; then $\overset{g}{ˉ} = \overset{r}{ˉ}$ . If two such representatives $r, r^{'}$ were congruent, $f ∣ (r - r^{'})$ with $de g (r - r^{'}) < n = de g f$ , which by the theorem Degrees add over a domain forces $r - r^{'} = 0$ . So representatives of degree $< n$ exist and are unique, and they form the $F$ -span of $1, x, \dots, x^{n - 1}$ , which is therefore a basis. Counting: an element is a choice of $n$ coefficients from $F$ , giving $q^{n}$ .∎

Corollary 7.57 (Making a field by killing an irreducible). $F [x] / (f)$ is a field if and only if $f$ is irreducible over $F$ . In that case it is a field extension of $F$ of degree $de g f$ in which $\overset{x}{ˉ}$ is a root of $f$ .

Proof. By the corollary Maximality of nonzero prime ideals applied in the PID $F [x]$ , $(f)$ is maximal exactly when $f$ is irreducible, and a quotient by an ideal is a field exactly when that ideal is maximal. For the last clause, write $f = \sum a_{i} x^{i}$ ; then $f (\overset{x}{ˉ}) = \overline{\sum a_{i} x^{i}} = \overset{ˉ}{f} = 0$ in the quotient. The degree is $de g f$ by the theorem Structure of $F [x] / (f)$ .∎

Example 7.58 (A field with nine elements). Show $F_{3} [x] / (x^{2} + 1)$ is a field, list its elements, and compute $(\overset{x}{ˉ} + 1)^{2}$ .

Solution.

$x^{2} + 1$ has degree $2$ , so by the proposition Low-degree irreducibility test it is irreducible over $F_{3}$ iff it has no root there: $0^{2} + 1 = 1$ , $1^{2} + 1 = 2$ , $2^{2} + 1 = 5 = 2$ . None is zero, so it is irreducible.
By the corollary Making a field by killing an irreducible, the quotient is a field; by the theorem Structure of $F [x] / (f)$ it has $3^{2} = 9$ elements, namely $a + b \overset{x}{ˉ}$ with $a, b \in {0, 1, 2}$ .
$(\overset{x}{ˉ} + 1)^{2} = \overset{x}{ˉ}^{2} + 2 \overset{x}{ˉ} + 1$ , and $\overset{x}{ˉ}^{2} = - 1 = 2$ , so this is $2 + 2 \overset{x}{ˉ} + 1 = 3 + 2 \overset{x}{ˉ} = 2 \overset{x}{ˉ}$ .
Check the field property on an example: $\overset{x}{ˉ} \cdot 2 \overset{x}{ˉ} = 2 \overset{x}{ˉ}^{2} = 2 \cdot 2 = 4 = 1$ , so $\overset{x}{ˉ}^{- 1} = 2 \overset{x}{ˉ}$ . ✓

□

Proposition 7.59 (Counting monic irreducibles over $F_{p}$ ). Let $N_{p} (n)$ be the number of monic irreducible polynomials of degree $n$ over $F_{p}$ . Then

N_{p} (1) = p, N_{p} (2) = \frac{p ^{2} - p}{2}, N_{p} (3) = \frac{p ^{3} - p}{3},

and in general $N_{p} (n) = \frac{1}{n} d ∣ n \sum μ (d) p^{n / d}$ .

Proof. Degree $1$ : the monic linear polynomials are $x - a$ for $a \in F_{p}$ , all irreducible, and there are $p$ of them.

Degree $2$ : there are $p^{2}$ monic quadratics $x^{2} + b x + c$ . The reducible ones are exactly the products $(x - a) (x - a^{'})$ with $a, a^{'} \in F_{p}$ — by the proposition Low-degree irreducibility test a reducible quadratic has a root, hence splits into linear factors — and unordered pairs with repetition number $(2 p + 1) = \frac{p ( p + 1 )}{2}$ . So $N_{p} (2) = p^{2} - \frac{p ( p + 1 )}{2} = \frac{2 p ^{2} - p ^{2} - p}{2} = \frac{p ^{2} - p}{2}$ .

Degree $3$ : there are $p^{3}$ monic cubics. A reducible cubic has a linear factor, so it is $(x - a)$ times a monic quadratic, or a product of three linear factors. Counting by factorization type: $p \cdot N_{p} (2)$ of the form (linear)(irreducible quadratic), and $(3 p + 2)$ products of three linear factors with repetition. Then

N_{p} (3) = p^{3} - p \cdot \frac{p ^{2} - p}{2} - \frac{p ( p + 1 ) ( p + 2 )}{6} = \frac{6 p ^{3} - 3 p ^{3} + 3 p ^{2} - p ^{3} - 3 p ^{2} - 2 p}{6} = \frac{2 p ^{3} - 2 p}{6} = \frac{p ^{3} - p}{3} .

The general formula is quoted rather than proved here: it follows by Möbius inversion from the identity $p^{n} = \sum_{d ∣ n} d N_{p} (d)$ , which says that $x^{p^{n}} - x$ is the product of all monic irreducibles of degree dividing $n$ — a fact belonging to the theory of finite fields developed in Galois Theory.∎

Example 7.60 (Listing the monic irreducible quadratics over $F_{3}$ ). Find every monic irreducible quadratic in $F_{3} [x]$ and check the count against the proposition Counting monic irreducibles over $F_{p}$ .

Solution.

The formula predicts $N_{3} (2) = (9 - 3) /2 = 3$ .
A monic quadratic $x^{2} + b x + c$ over $F_{3}$ is irreducible iff it has no root in ${0, 1, 2}$ , by the proposition Low-degree irreducibility test. Note $c \neq = 0$ , else $0$ is a root.
Test the six candidates with $c \in {1, 2}$ : $x^{2} + 1$ takes values $1, 2, 2$ — irreducible. $x^{2} + x + 1$ takes $1, 0, \dots$ — reducible. $x^{2} + 2 x + 1 = (x + 1)^{2}$ — reducible. $x^{2} + 2$ takes $2, 0$ — reducible. $x^{2} + x + 2$ takes $2, 1, 2$ — irreducible. $x^{2} + 2 x + 2$ takes $2, 2, 1$ — irreducible.
So the three are $x^{2} + 1$ , $x^{2} + x + 2$ , $x^{2} + 2 x + 2$ , matching the prediction. ✓

□

Summary. The chapter in five lines. Degree turns $F [x]$ into a ring with division-with-remainder; division-with-remainder makes it Euclidean; Euclidean makes every ideal principal; principal makes irreducibles prime; and irreducibles being prime, together with the ascending chain condition, is exactly unique factorization. Everything else — Gauss, Eisenstein, the rational root theorem — is machinery for identifying the irreducibles once you know they exist.

Exercises for §7.5 →

Common Mistakes

Treating a polynomial as the function it defines. Over a finite ring these differ: $x^{2} + x$ and $0$ agree at every point of $F_{2}$ but are different elements of $F_{2} [x]$ . The identification is legitimate only over an infinite domain, by the corollary Polynomials and functions agree over an infinite domain.
Using $de g (f g) = de g f + de g g$ without a domain. Over $Z /4 Z$ , $(2 x + 1)^{2} = 1$ . Every consequence — units are constants, at most $n$ roots, cancellation — fails with it.
Believing $Z [x]$ has a division algorithm. You may divide by a monic polynomial in any $R [x]$ , and by any nonzero polynomial only when the coefficients form a field.
Claiming a degree- $n$ polynomial has at most $n$ roots in any ring. $x^{2} - 1$ has four roots in $Z /8 Z$ . The bound needs an integral domain.
Concluding "no roots, therefore irreducible". True only in degrees $2$ and $3$ . $x^{4} + 4$ and $(x^{2} + 1)^{2}$ are the standing counterexamples.
Confusing irreducible with prime. Prime always implies irreducible; the converse needs a PID (or a UFD). In $Z [- 5]$ , $2$ is irreducible and not prime, and factorization is not unique.
Assuming a gcd is always a linear combination. Bézout needs a PID. In $Z [x]$ , $g cd (2, x) = 1$ but $1 \in / (2, x)$ .
Expecting Eisenstein to be visible. It very often applies only after a substitution $x \mapsto x + a$ , as for $Φ_{p}$ and for $x^{4} + 1$ ; failing directly proves nothing.
Reading a mod- $p$ factorization as proof of reducibility. Reduction can only prove irreducibility. $x^{4} + 1$ is irreducible over $Q$ and reducible modulo every prime.
Forgetting the hypothesis $p ∤ lc (f)$ in the reduction test, which is what keeps the degrees of the factors from dropping.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter

Introduction

7.1Polynomials over a ring

Division with remainder

7.2Euclidean domains

7.3Principal ideal domains and unique factorization

7.4Irreducibility over Q

7.5Quotients, finite fields and counting irreducibles

7.4Irreducibility over $Q$