Chapter 7 · Rings

7.3 Polynomial Rings and Irreducibility

Polynomials over a field divide like integers — division algorithm, roots and factors, unique factorisation. Deciding whether a polynomial factors over $\mathbb{C}$, $\mathbb{R}$, $\mathbb{Q}$ or $\mathbb{F}_p$ calls on Gauss's lemma, the rational root test, Eisenstein's criterion with shifts and reduction mod $p$; counting irreducibles over $\mathbb{F}_p$ and the cyclotomic polynomials complete the toolkit.

Polynomials are the second great example, after the integers, of a ring in which one can divide with remainder. Over a field $F$ the ring $F[x]$ has a division algorithm, a Euclidean algorithm, Bézout's identity and unique factorisation — and its "primes" are the irreducible polynomials. Unlike the integers, though, the primes of $F[x]$ depend on $F$: $x^2+1$ is irreducible over $\mathbb{R}$ and over $\mathbb{F}_3$, but splits over $\mathbb{C}$ and over $\mathbb{F}_5$; $x^4+1$ cannot be factored over $\mathbb{Q}$, yet it factors modulo every prime. Learning to decide irreducibility quickly and correctly is the practical aim of this section.

It is also a theoretical necessity. By §7.2, $F[x]/\langle f\rangle$ is a field exactly when $f$ is irreducible, and every field extension in Chapter 8 — $\mathbb{Q}(\sqrt[3]{2})$, the cyclotomic fields, the finite fields $\mathbb{F}_{p^n}$ — is built this way. CSIR NET examines the material directly: "which of these polynomials is irreducible over $\mathbb{Q}$?", "how many monic irreducible cubics are there over $\mathbb{Z}_5$?", "for how many $a$ is $\mathbb{Z}_3[x]/\langle f_a\rangle$ a field?", "what is $\Phi_{12}$?". The tools are few — the root test for degrees $2$ and $3$, Gauss's lemma, the rational root test, Eisenstein's criterion (often after a shift $x\mapsto x+1$), reduction modulo a prime, and a counting formula over $\mathbb{F}_p$ — and the traps are always the same: a quartic without roots that still factors, an Eisenstein test that fails although the polynomial is irreducible, and a reduction mod $p$ read in the wrong direction. Throughout, rings are commutative with $1\ne0$, and we write $\mathbb{F}_p$ for the field $\mathbb{Z}_p$ ($p$ prime).

Polynomial Rings and the Division Algorithm

📘 Definition 7.15 — Polynomials over a ring

Let $R$ be a commutative ring. A polynomial over $R$ is a formal expression $f=a_0+a_1x+\dots+a_nx^n$ with $a_i\in R$, two polynomials being equal when all their coefficients agree. With the usual addition and the product $$\Big(\sum_i a_ix^i\Big)\Big(\sum_j b_jx^j\Big)=\sum_k\Big(\sum_{i+j=k}a_ib_j\Big)x^k$$ they form the polynomial ring $R[x]$, which contains $R$ as the constant polynomials.

If $f\ne0$ and $a_n\ne0$ is its last nonzero coefficient, $n=\deg f$ is the degree, $a_n$ the leading coefficient, and $f$ is monic if $a_n=1$. The zero polynomial has no degree (or degree $-\infty$). For $c\in R$ the value $f(c)=\sum a_ic^i$ is obtained by evaluation, and $f\mapsto f(c)$ is a ring homomorphism $R[x]\to R$; $c$ is a root (zero) of $f$ if $f(c)=0$.

A polynomial is not a function: it is its list of coefficients. Over $\mathbb{F}_p$ the nonzero polynomial $x^p-x$ vanishes at every element (Fermat's little theorem, §5.2), so it defines the same function as $0$. Over an infinite domain this cannot happen (Theorem 7.38).

📐 Theorem 7.36 — Degrees, units and zero divisors in $R[x]$

Let $R$ be a commutative ring and $f,g\in R[x]$ nonzero.

  1. $\deg(f+g)\le\max(\deg f,\deg g)$ (when $f+g\ne0$) and $\deg(fg)\le\deg f+\deg g$, with equality in the second whenever the leading coefficient of $f$ or of $g$ is not a zero divisor — in particular whenever one of them is a unit, or $R$ is an integral domain.
  2. If $R$ is an integral domain, so is $R[x]$, and $R[x]^\times=R^\times$: the units of $R[x]$ are the unit constants. Consequently $x$ is never a unit and $R[x]$ is never a field.

Proof. (1) Write $f=\sum_{i\le m}a_ix^i$, $g=\sum_{j\le n}b_jx^j$ with $a_m,b_n\ne0$. No coefficient of $f+g$ beyond degree $\max(m,n)$ can be nonzero. In $fg$ the coefficient of $x^k$ is $\sum_{i+j=k}a_ib_j$, which is $0$ for $k\gt m+n$ (one index would exceed its range), and for $k=m+n$ equals $a_mb_n$. If $a_m$ is not a zero divisor then $a_mb_n\ne0$, so $\deg(fg)=m+n$; similarly if $b_n$ is not a zero divisor.

(2) In a domain no nonzero element is a zero divisor, so $\deg(fg)=\deg f+\deg g\ge0$ and in particular $fg\ne0$: $R[x]$ is a domain. If $fg=1$ then $\deg f+\deg g=\deg1=0$, so $f=a_0$ and $g=b_0$ are constants with $a_0b_0=1$, i.e. $a_0\in R^\times$. Conversely a unit constant is a unit of $R[x]$. Since $\deg x=1$, $x$ is not a unit, so the nonzero element $x$ has no inverse and $R[x]$ is not a field. ∎

Both conclusions fail as soon as $R$ has zero divisors: in $\mathbb{Z}_4[x]$, $(2x)(2x)=4x^2=0$ and $(1+2x)^2=1+4x+4x^2=1$, so $1+2x$ is a non-constant unit. (In general, $a_0+a_1x+\dots+a_nx^n$ is a unit of $R[x]$ iff $a_0$ is a unit and $a_1,\dots,a_n$ are nilpotent.)

📐 Theorem 7.37 — Division algorithm
Let $R$ be a commutative ring and let $g\in R[x]$ be a nonzero polynomial whose leading coefficient is a unit of $R$ (for instance $g$ monic). For every $f\in R[x]$ there are unique $q,r\in R[x]$ with $$f=qg+r,\qquad r=0\ \text{ or }\ \deg r\lt\deg g.$$ In particular this holds for every nonzero $g$ when $R=F$ is a field. If $f,g$ have coefficients in a subring $S\subseteq R$ (and the leading coefficient of $g$ is a unit of $S$), then $q,r$ have coefficients in $S$.

Proof. Existence, by strong induction on $\deg f$. Let $\deg g=m$ with leading coefficient $u\in R^\times$. If $f=0$ or $\deg f\lt m$, take $q=0$, $r=f$. If $\deg f=n\ge m$ with leading coefficient $a$, then $$f_1=f-au^{-1}x^{n-m}g$$ has its $x^n$-terms cancelled, so $f_1=0$ or $\deg f_1\lt n$. By induction $f_1=q_1g+r$ with $r=0$ or $\deg r\lt m$, and then $f=(q_1+au^{-1}x^{n-m})g+r$. Every step uses only ring operations on the coefficients of $f$ and $g$ and the inverse $u^{-1}$, which proves the last sentence.

Uniqueness. If $qg+r=q'g+r'$ then $(q-q')g=r'-r$. If $q\ne q'$, the leading coefficient $u$ of $g$ is a unit, hence not a zero divisor, so by Theorem 7.36 $\deg\big((q-q')g\big)=\deg(q-q')+m\ge m$; but $r'-r$ is $0$ or has degree $\lt m$. Hence $q=q'$ and then $r=r'$. ∎

The hypothesis on the leading coefficient matters: in $\mathbb{Z}[x]$ we cannot divide $x$ by $2x+1$, since $x=q(2x+1)+r$ with $r\in\mathbb{Z}$ forces $q$ to be a constant with $2q=1$. Over $\mathbb{Q}$ the division is $x=\tfrac12(2x+1)-\tfrac12$.

📐 Theorem 7.38 — Remainder theorem, factor theorem, number of roots

Let $R$ be a commutative ring, $f\in R[x]$ and $c\in R$.

  1. Remainder theorem: the remainder of $f$ on division by $x-c$ is the constant $f(c)$.
  2. Factor theorem: $f(c)=0$ if and only if $(x-c)$ divides $f$ in $R[x]$.
  3. If $R=D$ is an integral domain, a nonzero $f\in D[x]$ of degree $n$ has at most $n$ roots in $D$; more precisely, if $c_1,\dots,c_k$ are distinct roots then $(x-c_1)\cdots(x-c_k)$ divides $f$.
  4. If $D$ is an infinite integral domain and $f(c)=g(c)$ for infinitely many $c\in D$, then $f=g$.

Proof. (1) $x-c$ is monic, so $f=q\cdot(x-c)+r$ with $r$ constant (Theorem 7.37). Evaluation is a ring homomorphism, so $f(c)=q(c)\cdot0+r=r$. (2) follows: $f(c)=0$ iff the remainder is $0$.

(3) Induction on $k$. For $k=1$ this is (2). If $f=(x-c_1)\cdots(x-c_{k-1})\,h$ and $c_k$ is another root, then $0=f(c_k)=(c_k-c_1)\cdots(c_k-c_{k-1})\,h(c_k)$. The factors $c_k-c_i$ are nonzero and $D$ has no zero divisors, so $h(c_k)=0$ and $(x-c_k)\mid h$. Comparing degrees (Theorem 7.36), $k\le n$.

(4) $f-g$ has infinitely many roots, so by (3) it cannot be a nonzero polynomial. ∎

Part (3) is exactly what is used in §6.1 to show that every finite subgroup of $F^\times$ is cyclic: the equation $x^d=1$ has at most $d$ solutions in a field. It fails in rings with zero divisors (Example 2), and also in non-commutative rings, where evaluation is not a homomorphism.

📐 Theorem 7.39 — $F[x]$ is a Euclidean domain
Let $F$ be a field. Then $F[x]$ is a Euclidean domain with $\delta(f)=\deg f$, hence a PID and a UFD (§7.2). Concretely:
  1. every ideal $I\ne0$ of $F[x]$ is $I=\langle g\rangle$ for a unique monic $g$ — the monic polynomial of least degree in $I$;
  2. any $f,g$, not both $0$, have a unique monic $\gcd(f,g)=d$, and $d=uf+vg$ for some $u,v\in F[x]$ (Bézout); $d$ is computed by the Euclidean algorithm, and it is the same whether computed in $F[x]$ or in $K[x]$ for any field $K\supseteq F$;
  3. every nonconstant $f\in F[x]$ is $f=c\,p_1^{e_1}\cdots p_k^{e_k}$ with $c\in F^\times$ and distinct monic irreducible $p_i$ (Definition 7.17 below), uniquely up to the order of the factors.

Proof. The division algorithm (Theorem 7.37) is precisely the Euclidean property for $\delta=\deg$. (1) Let $g\in I$ be nonzero of least degree, scaled to be monic. For $f\in I$, $f=qg+r$ with $r=f-qg\in I$ of degree $\lt\deg g$, so $r=0$: $I=\langle g\rangle$. Two monic generators divide each other, so they have equal degrees and differ by a unit constant, which must be $1$. (2) Apply (1) to $I=\langle f,g\rangle=\{uf+vg\}$: its monic generator $d$ divides $f$ and $g$, and every common divisor of $f,g$ divides $uf+vg=d$. Euclid's algorithm replaces $(f,g)$ by $(g,r)$, which generate the same ideal, until the remainder is $0$; every division happens in $F[x]$, and by uniqueness in Theorem 7.37 it is the same division in $K[x]$, so the output does not depend on the larger field. (3) is ED $\Rightarrow$ PID $\Rightarrow$ UFD (§7.2); the key step, Euclid's lemma, is immediate here: if $p$ is irreducible and $p\mid ab$ but $p\nmid a$, then $\gcd(p,a)=1$, so $1=up+va$ and $b=upb+vab$ is divisible by $p$. ∎

📘 Definition 7.16 — Multiplicity and the formal derivative
A root $c$ of $f\ne0$ has multiplicity $m$ if $(x-c)^m\mid f$ but $(x-c)^{m+1}\nmid f$; it is a simple root if $m=1$ and a multiple (repeated) root if $m\ge2$. The formal derivative of $f=\sum a_kx^k$ is $f'=\sum_{k\ge1}k\,a_kx^{k-1}$. It satisfies $(f+g)'=f'+g'$ and $(fg)'=f'g+fg'$ (check on monomials $x^ix^j$ and extend bilinearly), with no limits involved.
📐 Theorem 7.40 — Repeated roots and the derivative

Let $F$ be a field and $f\in F[x]$ nonconstant.

  1. $c\in F$ is a multiple root of $f$ iff $f(c)=f'(c)=0$.
  2. If $\gcd(f,f')=1$, then $f$ has no multiple root in any field $K\supseteq F$. If $f$ has a repeated irreducible factor $p^2\mid f$ in $F[x]$, then $p\mid\gcd(f,f')$.
  3. An irreducible $f$ has a multiple root in some $K\supseteq F$ only if $f'=0$. In characteristic $0$ this never happens; in characteristic $p$ it happens only if $f(x)=g(x^p)$ for some $g$.

Proof. (1) Write $f=(x-c)^mg$ with $m\ge1$ and $g(c)\ne0$. Then $f'=m(x-c)^{m-1}g+(x-c)^mg'$. If $m\ge2$ both terms vanish at $c$. If $m=1$, $f'(c)=g(c)\ne0$.

(2) If $(x-c)^2\mid f$ in $K[x]$, then $f(c)=f'(c)=0$ by (1) (the derivative does not depend on the field), so $x-c$ divides $\gcd(f,f')$ computed in $K[x]$, which by Theorem 7.39(2) equals $\gcd(f,f')$ computed in $F[x]$; hence that gcd is not $1$. If $f=p^2h$ then $f'=2pp'h+p^2h'$ is divisible by $p$.

(3) If $f$ is irreducible, $\gcd(f,f')$ divides $f$, so it is $1$ or (the monic multiple of) $f$. In the second case $f\mid f'$ with $\deg f'\lt\deg f$, forcing $f'=0$. In characteristic $0$, $f'$ has leading coefficient $na_n\ne0$. In characteristic $p$, $f'=\sum ka_kx^{k-1}=0$ means $ka_k=0$ for all $k$, i.e. $a_k=0$ unless $p\mid k$. ∎

Two uses to remember: $x^{p^n}-x$ over $\mathbb{F}_p$ has derivative $p^nx^{p^n-1}-1=-1$, so it has $p^n$ distinct roots wherever it splits; and $x^n-1$ over $\mathbb{F}_p$ with $p\nmid n$ has $\gcd(x^n-1,nx^{n-1})=1$, so it has no repeated factors.

✏️ Example 1 — Division and the Euclidean algorithm over $\mathbb{Q}$ and $\mathbb{F}_p$
(a) Divide $f=2x^4-3x^3+x-5$ by $g=2x^2+1$ in $\mathbb{Q}[x]$. (b) Divide $3x^4+x^3+2x+1$ by $2x^2+x+3$ in $\mathbb{F}_5[x]$. (c) Find $\gcd(x^4-1,\;x^3+2x^2+2x+1)$ in $\mathbb{Q}[x]$, write it in Bézout form, and then find the gcd of the same two polynomials in $\mathbb{F}_3[x]$.
(a) Leading terms: $2x^4\div2x^2=x^2$; $f-x^2g=-3x^3-x^2+x-5$. Next $-\tfrac32x$: subtracting $-\tfrac32xg$ leaves $-x^2+\tfrac52x-5$. Next $-\tfrac12$: leaves $\tfrac52x-\tfrac92$. So $$q=x^2-\tfrac32x-\tfrac12,\qquad r=\tfrac52x-\tfrac92.$$ Check: $(2x^2+1)(x^2-\tfrac32x-\tfrac12)=2x^4-3x^3-\tfrac32x-\tfrac12$, and adding $r$ gives $f$.
(b) The leading coefficient $2$ is a unit of $\mathbb{F}_5$ with $2^{-1}=3$. Dividing, $q=4x^2+x+1$ and $r=3x+3$. Check: $(2x^2+x+3)(4x^2+x+1)=8x^4+6x^3+15x^2+4x+3\equiv3x^4+x^3+4x+3$, and adding $3x+3$ gives $3x^4+x^3+7x+6\equiv3x^4+x^3+2x+1\pmod5$.
(c) over $\mathbb{Q}$ $x^4-1=(x-2)(x^3+2x^2+2x+1)+(2x^2+3x+1)$; then $x^3+2x^2+2x+1=(\tfrac12x+\tfrac14)(2x^2+3x+1)+\tfrac34(x+1)$; and $2x^2+3x+1=(2x+1)(x+1)$ leaves remainder $0$. The last nonzero remainder, made monic, is $\gcd=x+1$. Back-substituting (or by the extended algorithm), $$\left(-\tfrac23x-\tfrac13\right)(x^4-1)+\left(\tfrac23x^2-x+\tfrac23\right)(x^3+2x^2+2x+1)=x+1.$$ Factorisations confirm it: $x^4-1=(x-1)(x+1)(x^2+1)$ and $x^3+2x^2+2x+1=(x+1)(x^2+x+1)$.
(c) over $\mathbb{F}_3$ The first remainder is $2x^2+3x+1\equiv2x^2+1=2(x^2-1)$. Then $x^3+2x^2+2x+1=(x+2)(x^2-1)+3x+3\equiv(x+2)(x^2-1)$, so the gcd is $x^2-1$. The reason: modulo $3$, $x^2+x+1=(x-1)^2$, so the cubic becomes $(x+1)(x-1)^2$ and shares the factor $x-1$ with $x^4-1$.
Lesson The gcd does not change when the field is enlarged (Theorem 7.39(2)), but reducing the coefficients modulo $p$ is a different operation and may enlarge the gcd.
✏️ Example 2 — Prove or disprove: polynomials over rings that are not domains
Decide each statement. (a) A nonzero polynomial of degree $n$ over a commutative ring has at most $n$ roots. (b) Over every commutative ring, $\deg(fg)=\deg f+\deg g$ for nonzero $f,g$ with $fg\ne0$. (c) If two polynomials over a field $F$ take the same value at every point of $F$, they are equal. (d) Over any ring with $1$, $x^2+1$ has at most two roots.
(a) False In $\mathbb{Z}_8$, $x^2-1$ has the four roots $1,3,5,7$ (each odd square is $\equiv1\pmod8$). In $\mathbb{Z}_6$, $x^3-x$ vanishes at all six elements, since $n^3-n=(n-1)n(n+1)$ is divisible by $6$. The proof of Theorem 7.38(3) breaks where we cancelled $c_k-c_i$: in $\mathbb{Z}_8$, $(3-1)(3+1)=8=0$.
(b) False In $\mathbb{Z}_4[x]$, $(2x+1)(2x+1)=4x^2+4x+1=1$ has degree $0$, not $2$. The leading coefficient $2$ is a zero divisor, exactly the case excluded in Theorem 7.36(1).
(c) False for finite fields In $\mathbb{F}_p$, $x^p$ and $x$ agree at every point (Fermat), but they are different polynomials. For an infinite field the statement is true by Theorem 7.38(4).
(d) False In the quaternions $\mathbb{H}$ (§7.1), $(bi+cj+dk)^2=-(b^2+c^2+d^2)$ because $ij=-ji$ etc., so every $bi+cj+dk$ with $b^2+c^2+d^2=1$ is a root of $x^2+1$ — infinitely many. Here $R$ is a division ring, so there are no zero divisors; what fails is commutativity, which the factor theorem needs (evaluation $f\mapsto f(c)$ is a homomorphism only if $c$ commutes with the coefficients and with $x$).

Irreducible Polynomials over $\mathbb{C}$, $\mathbb{R}$ and in Low Degree

📘 Definition 7.17 — Irreducible polynomial

Let $F$ be a field. A polynomial $f\in F[x]$ is irreducible over $F$ if $\deg f\ge1$ and $f$ cannot be written as $f=gh$ with $g,h\in F[x]$ both of degree $\ge1$ (equivalently, of degrees $\lt\deg f$). Otherwise a nonconstant $f$ is reducible. Constants are neither.

This is the general notion of an irreducible element (§7.2) in the domain $F[x]$: since the units are the nonzero constants, "$f=gh$ forces $g$ or $h$ to be a unit" means "forces $g$ or $h$ to be constant". Over a domain $D$ that is not a field — such as $\mathbb{Z}$ — the general notion is different, because non-unit constants count: in $\mathbb{Z}[x]$, $2x+4=2(x+2)$ is reducible although it has degree $1$.

📐 Theorem 7.41 — The root test in degrees $2$ and $3$
Let $F$ be a field. Every polynomial of degree $1$ is irreducible. A polynomial $f\in F[x]$ of degree $2$ or $3$ is irreducible over $F$ if and only if it has no root in $F$. For degree $\ge4$, "no root" is necessary for irreducibility but not sufficient.

Proof. A factorisation of a degree-$1$ polynomial into two factors of degree $\ge1$ would have degree $\ge2$. If $\deg f\in\{2,3\}$ and $f=gh$ with $\deg g,\deg h\ge1$, then $\deg g+\deg h\le3$ forces one factor, say $g=ax+b$ with $a\ne0$, to be linear, and $f(-b/a)=0$. Conversely, a root $c$ gives the factor $x-c$ (Theorem 7.38), and if $\deg f\ge2$ the cofactor has degree $\ge1$. For degree $4$: $(x^2+1)^2$ has no real root but is reducible over $\mathbb{R}$; $x^4+4=(x^2+2x+2)(x^2-2x+2)$ has no rational root but is reducible over $\mathbb{Q}$; and $x^4+x^2+1=(x^2+x+1)^2$ over $\mathbb{F}_2$. ∎

📐 Theorem 7.42 — Irreducible polynomials over $\mathbb{C}$ and over $\mathbb{R}$
  1. The irreducible polynomials in $\mathbb{C}[x]$ are exactly those of degree $1$; every nonconstant $f\in\mathbb{C}[x]$ is $c\prod(x-\alpha_i)$.
  2. The irreducible polynomials in $\mathbb{R}[x]$ are exactly those of degree $1$ and the quadratics $ax^2+bx+c$ with $b^2-4ac\lt0$. Every nonconstant real polynomial is a product of real linear factors and real quadratics with negative discriminant; its non-real roots come in conjugate pairs. In particular every real polynomial of odd degree has a real root.

Proof. (1) By the fundamental theorem of algebra (stated in §1.1, proved via Liouville's theorem in §2.3), a polynomial of degree $\ge2$ over $\mathbb{C}$ has a root, hence a linear factor and a cofactor of degree $\ge1$. Induct on the degree for the factorisation.

(2) A real quadratic is irreducible over $\mathbb{R}$ iff it has no real root (Theorem 7.41) iff $b^2-4ac\lt0$. Now let $f\in\mathbb{R}[x]$ be irreducible of degree $n\ge2$. It has a complex root $\alpha$, which is not real (else $x-\alpha$ would be a real factor). Since the coefficients are real, $f(\bar\alpha)=\overline{f(\alpha)}=0$, and $\bar\alpha\ne\alpha$. So in $\mathbb{C}[x]$ the polynomial $$q(x)=(x-\alpha)(x-\bar\alpha),$$ which equals $x^2-2(\operatorname{Re}\alpha)x+|\alpha|^2$ and so lies in $\mathbb{R}[x]$, divides $f$. Divide $f$ by $q$ in $\mathbb{R}[x]$: $f=sq+r$; by uniqueness of division in $\mathbb{C}[x]$ (Theorem 7.37) the remainder is the one found there, $r=0$. So $q\mid f$ in $\mathbb{R}[x]$, and irreducibility forces $f=cq$ with $c\in\mathbb{R}^\times$: $n=2$. The factorisation statement follows by Theorem 7.39(3), and an odd-degree polynomial cannot be a product of quadratics only. ∎

📐 Theorem 7.43 — $F[x]/\langle f\rangle$ is a field iff $f$ is irreducible
Let $F$ be a field and $f\in F[x]$ of degree $n\ge1$. Every coset in $F[x]/\langle f\rangle$ contains exactly one polynomial of degree $\lt n$ (its remainder mod $f$), so as an $F$-vector space $F[x]/\langle f\rangle$ has basis $1,\bar x,\dots,\bar x^{\,n-1}$; for $F=\mathbb{F}_p$ it has $p^n$ elements. Moreover the following are equivalent: (i) $f$ is irreducible; (ii) $\langle f\rangle$ is a maximal ideal; (iii) $\langle f\rangle$ is a prime ideal; (iv) $F[x]/\langle f\rangle$ is a field; (v) $F[x]/\langle f\rangle$ is an integral domain.

Proof. By the division algorithm $g=qf+r$ with $\deg r\lt n$ (or $r=0$), so $g+\langle f\rangle=r+\langle f\rangle$; and two such remainders in the same coset differ by a multiple of $f$ of degree $\lt n$, which must be $0$. (i)$\Rightarrow$(iv): let $g\notin\langle f\rangle$. Any common divisor of $f$ and $g$ divides the irreducible $f$, so is a constant or a constant times $f$; the latter is impossible as $f\nmid g$. Hence $\gcd(f,g)=1=uf+vg$ (Theorem 7.39), and $\bar v\bar g=\bar1$ in the quotient. (iv)$\Rightarrow$(v) is clear. (v)$\Rightarrow$(i): if $f=gh$ with $1\le\deg g,\deg h\lt n$, then $\bar g\bar h=\bar0$ while $\bar g,\bar h\ne\bar0$ (they are their own remainders and nonzero). The equivalences with (ii), (iii) are "maximal $\iff$ quotient is a field" and "prime $\iff$ quotient is a domain" (§7.2). ∎

So $\mathbb{R}[x]/\langle x^2+1\rangle\cong\mathbb{C}$, $\mathbb{F}_2[x]/\langle x^2+x+1\rangle$ is a field with $4$ elements, and $\mathbb{F}_5[x]/\langle x^2+1\rangle$ is not a field: $x^2+1=(x-2)(x+2)$ over $\mathbb{F}_5$, and by the Chinese remainder theorem for rings it is $\cong\mathbb{F}_5\times\mathbb{F}_5$. Finite fields of every prime-power order are built in exactly this way in §8.2 — once we know that irreducible polynomials of every degree exist over $\mathbb{F}_p$ (Theorem 7.52).

Content, Gauss's Lemma and the Rational Root Test

Over $\mathbb{Q}$ there are irreducible polynomials of every degree ($x^n-2$, Example 4), so the root test is not enough. The first step is to move the problem from $\mathbb{Q}[x]$ to $\mathbb{Z}[x]$, where divisibility of coefficients by primes becomes available. Gauss's lemma guarantees that nothing is lost.

📘 Definition 7.18 — Content and primitive polynomials
The content $c(f)$ of a nonzero $f=\sum a_ix^i\in\mathbb{Z}[x]$ is $\gcd(a_0,a_1,\dots,a_n)\ge1$. The polynomial $f$ is primitive if $c(f)=1$. Every nonzero $f\in\mathbb{Z}[x]$ is $f=c(f)f_0$ with $f_0$ primitive, and every nonzero $F\in\mathbb{Q}[x]$ can be written $F=\lambda f_0$ with $\lambda\in\mathbb{Q}^\times$ and $f_0\in\mathbb{Z}[x]$ primitive (clear denominators, then remove the content); $f_0$ is unique up to sign.
📐 Theorem 7.44 — Gauss's lemma
The product of two primitive polynomials in $\mathbb{Z}[x]$ is primitive. Consequently $c(fg)=c(f)\,c(g)$ for all nonzero $f,g\in\mathbb{Z}[x]$.

Proof. Suppose $f,g$ are primitive but a prime $p$ divides every coefficient of $fg$. Reduce coefficients modulo $p$: the map $\mathbb{Z}[x]\to\mathbb{F}_p[x]$, $h\mapsto\bar h$, is a ring homomorphism, so $\bar f\,\bar g=\overline{fg}=0$. Since $\mathbb{F}_p[x]$ is an integral domain (Theorem 7.36), $\bar f=0$ or $\bar g=0$ — that is, $p$ divides every coefficient of $f$ or of $g$, contradicting primitivity. For the second statement write $f=c(f)f_0$, $g=c(g)g_0$; then $fg=c(f)c(g)\,f_0g_0$ with $f_0g_0$ primitive, so $c(fg)=c(f)c(g)$. ∎

📐 Theorem 7.45 — Factoring over $\mathbb{Q}$ is factoring over $\mathbb{Z}$
Let $f\in\mathbb{Z}[x]$ be nonconstant. If $f=GH$ with $G,H\in\mathbb{Q}[x]$ of degrees $r,s$, then $f=gh$ with $g,h\in\mathbb{Z}[x]$ of the same degrees $r,s$ (and $g,h$ rational multiples of $G,H$). Hence: a primitive nonconstant $f\in\mathbb{Z}[x]$ is irreducible in $\mathbb{Z}[x]$ iff it is irreducible in $\mathbb{Q}[x]$.

Proof. Write $G=\lambda g_0$, $H=\mu h_0$ with $\lambda,\mu\in\mathbb{Q}^\times$ and $g_0,h_0$ primitive in $\mathbb{Z}[x]$. Then $f=\lambda\mu\,g_0h_0$, and $g_0h_0$ is primitive by Gauss's lemma. Write $\lambda\mu=a/b$ in lowest terms with $b\gt0$: $bf=a\,g_0h_0$. Taking contents, $b\,c(f)=|a|$; so $b$ divides $a$, forcing $b=1$ and $\lambda\mu=a\in\mathbb{Z}$. Then $g=a g_0$ and $h=h_0$ work. For the equivalence: if primitive $f$ is reducible in $\mathbb{Q}[x]$ we get $f=gh$ in $\mathbb{Z}[x]$ with both degrees $\ge1$, so neither factor is a unit of $\mathbb{Z}[x]$. Conversely, if $f=gh$ in $\mathbb{Z}[x]$ with neither $g$ nor $h$ a unit ($\pm1$), then neither is a constant — a constant factor would divide $c(f)=1$ — so both have degree $\ge1$ and $f$ is reducible in $\mathbb{Q}[x]$. ∎

📐 Theorem 7.46 — Rational root test
Let $f=a_nx^n+\dots+a_1x+a_0\in\mathbb{Z}[x]$ with $a_n\ne0$. If $u/v$ is a root of $f$ with $u,v\in\mathbb{Z}$, $v\gt0$ and $\gcd(u,v)=1$, then $u\mid a_0$ and $v\mid a_n$. In particular a monic integer polynomial has every rational root an integer dividing $a_0$.

Proof. Multiply $f(u/v)=0$ by $v^n$: $$a_nu^n+a_{n-1}u^{n-1}v+\dots+a_1uv^{n-1}+a_0v^n=0.$$ Every term except $a_0v^n$ is divisible by $u$, so $u\mid a_0v^n$; as $\gcd(u,v)=1$, $u\mid a_0$. Every term except $a_nu^n$ is divisible by $v$, so $v\mid a_nu^n$ and $v\mid a_n$. ∎

The monic case is a quick irrationality machine: $\sqrt[k]{m}$ is either an integer or irrational (it is a root of $x^k-m$), and $\sqrt2+\sqrt3$, a root of $x^4-10x^2+1$ whose only candidate rational roots $\pm1$ fail, is irrational.

📐 Theorem 7.47 — $\mathbb{Z}[x]$ is a UFD; its irreducible elements
$\mathbb{Z}[x]$ is a unique factorisation domain. Its irreducible elements are (a) the primes $\pm p$ of $\mathbb{Z}$, and (b) the primitive polynomials of degree $\ge1$ that are irreducible in $\mathbb{Q}[x]$. More generally, if $D$ is a UFD then so is $D[x]$, and hence so is $D[x_1,\dots,x_n]$.

Proof sketch. (This is Gauss's theorem on polynomial rings over a UFD from §7.2, whose proof there quoted Gauss's lemma; now that the lemma is proved, here are the steps for $\mathbb{Z}[x]$.) Existence: write $f=c(f)f_0$; factor $c(f)$ into primes of $\mathbb{Z}$, and factor $f_0$ by repeatedly splitting it into two factors of lower degree — by Theorem 7.45 this can be done inside $\mathbb{Z}[x]$, with primitive factors (their contents multiply to $1$), and degrees decrease, so it stops. Irreducibles: a constant $p$ is irreducible in $\mathbb{Z}[x]$ iff it is a prime of $\mathbb{Z}$ (a factorisation of a constant has constant factors); a nonconstant irreducible must be primitive (else $f=c(f)f_0$) and is then irreducible in $\mathbb{Q}[x]$ by Theorem 7.45. Uniqueness: it suffices that irreducibles are prime. A prime $p\in\mathbb{Z}$ is prime in $\mathbb{Z}[x]$ because $\mathbb{Z}[x]/\langle p\rangle\cong\mathbb{F}_p[x]$ is a domain — this is Gauss's lemma again. A primitive $f$ irreducible in $\mathbb{Q}[x]$ is prime in $\mathbb{Q}[x]$ (Theorem 7.39); if $f\mid gh$ in $\mathbb{Z}[x]$, then $f$ divides $g$, say, in $\mathbb{Q}[x]$, $g=fk$ with $k\in\mathbb{Q}[x]$, and comparing contents as in Theorem 7.45 shows $k\in\mathbb{Z}[x]$. The same argument works with $\mathbb{Z},\mathbb{Q}$ replaced by a UFD $D$ and its field of fractions. ∎

Recall from §7.2 that $\mathbb{Z}[x]$ is not a PID — the ideal $\langle2,x\rangle$ is not principal — so $\mathbb{Z}[x]$ is the standard example of a UFD that is not a PID. Likewise $F[x,y]$ is a UFD but $\langle x,y\rangle$ is not principal.

✏️ Example 3 — The rational root test at work
(a) Factor $f=2x^4-x^3-3x^2-5x-2$ into irreducibles over $\mathbb{Q}$. (b) Show that $x^3-3x-1$ is irreducible over $\mathbb{Q}$, and explain why this matters for the number $2\cos20^\circ$. (c) Show that $x^4-10x^2+1$ is irreducible over $\mathbb{Q}$.
(a) Candidates By Theorem 7.46 a rational root $u/v$ has $u\mid2$ and $v\mid2$: the candidates are $\pm1,\pm2,\pm\tfrac12$. Evaluating, $f(1)=-9$, $f(-1)=3$, $f(-2)=36$, $f(\tfrac12)=-\tfrac{21}{4}$, while $f(2)=32-8-12-10-2=0$ and $f(-\tfrac12)=\tfrac18+\tfrac18-\tfrac34+\tfrac52-2=0$.
(a) Factor So $(x-2)(2x+1)=2x^2-3x-2$ divides $f$, and long division gives $f=(x-2)(2x+1)(x^2+x+1)$. The quadratic has discriminant $-3\lt0$, so no rational (even real) root, and it is irreducible over $\mathbb{Q}$ by Theorem 7.41. This is the complete factorisation.
(b) The only candidates are $\pm1$, and $1-3-1=-3$, $-1+3-1=1$. A cubic without rational roots is irreducible over $\mathbb{Q}$. From $\cos3\theta=4\cos^3\theta-3\cos\theta$ with $\theta=20^\circ$ and $y=2\cos20^\circ$: $\tfrac12=\tfrac{y^3}{2}-\tfrac{3y}{2}$, i.e. $y^3-3y-1=0$. So $2\cos20^\circ$ is a root of an irreducible cubic; in Chapter 8 this shows $[\mathbb{Q}(\cos20^\circ):\mathbb{Q}]=3$, which is not a power of $2$, so the angle $60^\circ$ cannot be trisected with straightedge and compass.
(c) Candidates $\pm1$: $1-10+1=-8\ne0$, so no linear factor. By Theorem 7.45 a factorisation into two quadratics may be taken in $\mathbb{Z}[x]$ and, comparing leading coefficients, with monic factors: $(x^2+ax+b)(x^2+cx+d)$. Comparing coefficients: $x^3$: $a+c=0$; $x^1$: $ad+bc=a(d-b)=0$; $x^0$: $bd=1$, so $b=d=\pm1$; $x^2$: $b+d+ac=\pm2-a^2=-10$, so $a^2=12$ or $a^2=8$. Neither is a square, so there is no factorisation: $x^4-10x^2+1$ is irreducible. (It is the minimal polynomial of $\sqrt2+\sqrt3$, and it will reappear as a polynomial that no Eisenstein test can handle.)

Eisenstein's Criterion, Shifts and Reduction mod $p$

📐 Theorem 7.48 — Eisenstein's criterion
Let $f=a_nx^n+a_{n-1}x^{n-1}+\dots+a_0\in\mathbb{Z}[x]$, $n\ge1$, and let $p$ be a prime such that (i) $p\nmid a_n$; (ii) $p\mid a_i$ for $0\le i\le n-1$; (iii) $p^2\nmid a_0$. Then $f$ is irreducible in $\mathbb{Q}[x]$. If moreover $f$ is primitive, it is irreducible in $\mathbb{Z}[x]$. (The same holds over any UFD with a prime element $p$.)

Proof. Suppose $f$ is reducible in $\mathbb{Q}[x]$. By Theorem 7.45, $f=gh$ with $g=b_rx^r+\dots+b_0$ and $h=c_sx^s+\dots+c_0$ in $\mathbb{Z}[x]$, $r,s\ge1$, $r+s=n$. Reduce modulo $p$. The hypotheses say $\bar f=\bar a_nx^n$ with $\bar a_n\ne0$. Since $b_rc_s=a_n$ is not divisible by $p$, neither is $b_r$ nor $c_s$, so $\deg\bar g=r$ and $\deg\bar h=s$. In the UFD $\mathbb{F}_p[x]$ the only divisors of $\bar a_nx^n$ are constants times powers of $x$, so $\bar g=\bar b_rx^r$ and $\bar h=\bar c_sx^s$. As $r,s\ge1$, the constant terms vanish: $p\mid b_0$ and $p\mid c_0$. Then $p^2\mid b_0c_0=a_0$, a contradiction. If $f$ is primitive, irreducibility in $\mathbb{Z}[x]$ follows from Theorem 7.45. ∎

Eisenstein needs $p\mid$ all lower coefficients, and only those. Note what the proof really used: $\bar f$ is a constant times $x^n$. That tells us when a substitution might help.

📐 Theorem 7.49 — Substitutions preserve irreducibility
Let $F$ be a field, $a\in F$ and $c\in F^\times$. The map $f(x)\mapsto f(cx+a)$ is a ring automorphism of $F[x]$ that preserves degrees. Hence $f(x)$ is irreducible over $F$ iff $f(x+a)$ is, iff $f(cx+a)$ is. Also, for $f$ with $f(0)\ne0$, $f$ is irreducible iff its reversal $x^nf(1/x)$ is.

Proof. $\theta(f)(x)=f(cx+a)$ is evaluation at $cx+a$, hence a ring homomorphism $F[x]\to F[x]$ fixing constants; it has the inverse $f(x)\mapsto f\!\left(c^{-1}(x-a)\right)$, and $\deg f(cx+a)=\deg f$ because the leading coefficient gets multiplied by $c^n\ne0$. An automorphism preserving degrees carries factorisations $f=gh$ with $\deg g,\deg h\ge1$ to such factorisations and back. For the reversal: if $f=gh$ with degrees $r,s\ge1$ then $x^nf(1/x)=\big(x^rg(1/x)\big)\big(x^sh(1/x)\big)$, and $g(0)h(0)=f(0)\ne0$ ensures both reversed factors still have degrees $r,s$; reversing twice gives back $f$. ∎

When will a shift work? If $f(x+a)$ is Eisenstein at $p$ then $f(x+a)\equiv a_nx^n$, i.e. $f(x)\equiv a_n(x-a)^n\pmod p$. So look at $f$ modulo small primes: a shift can only help at a prime $p$ for which $f$ is congruent to a constant times an $n$-th power of a linear polynomial. For $x^4+1\equiv(x+1)^4\pmod2$ the shift $x\mapsto x+1$ is the natural try; for $x^4-10x^2+1$, which modulo every odd prime has distinct roots or (at $p=3$) is $(x^2+1)^2$, the only candidate is $p=2$, $a$ odd — and $f(a)=a^4-10a^2+1\equiv0\pmod 8$ for odd $a$, so $p^2\mid$ the constant term: no shift works. Interactive 1 lets you scan shifts and primes.

✏️ Example 4 — Eisenstein, directly and after a shift
Show that the following are irreducible over $\mathbb{Q}$: (a) $x^n-2$ for every $n\ge1$; (b) $x^4+1$; (c) $x^3-3x-1$ (a second proof); (d) for a prime $p$, the cyclotomic polynomial $\Phi_p(x)=x^{p-1}+x^{p-2}+\dots+x+1$; (e) $x^5+5x^4+20x^3+60x^2+120x+120$, i.e. $5!\sum_{k=0}^{5}\tfrac{x^k}{k!}$.
(a) Eisenstein at $p=2$: the leading coefficient $1$ is odd, the other coefficients are $0,\dots,0,-2$, and $4\nmid2$. So $\mathbb{Q}[x]$ has irreducible polynomials of every degree — unlike $\mathbb{R}[x]$ and $\mathbb{C}[x]$ (Theorem 7.42) — and $\sqrt[n]2$ is irrational for $n\ge2$.
(b) $x^4+1$ itself fails at every prime (the middle coefficients are $0$ but the constant $1$ is divisible by no prime). Modulo $2$, $x^4+1=(x+1)^4$, which suggests $x\mapsto x+1$: $$(x+1)^4+1=x^4+4x^3+6x^2+4x+2,$$ Eisenstein at $p=2$. By Theorem 7.49, $x^4+1$ is irreducible.
(c) Modulo $3$, $x^3-3x-1\equiv x^3-1=(x-1)^3$, suggesting $x\mapsto x+1$: $(x+1)^3-3(x+1)-1=x^3+3x^2-3$, Eisenstein at $p=3$ ($3\mid3,\ 3\mid0,\ 3\mid-3,\ 9\nmid3$). This agrees with Example 3(b).
(d) $\Phi_p(x)=\dfrac{x^p-1}{x-1}$, so $$\Phi_p(x+1)=\frac{(x+1)^p-1}{x}=\sum_{k=1}^{p}\binom pk x^{k-1}=x^{p-1}+\binom p{p-1}x^{p-2}+\dots+\binom p2x+p.$$ For $0\lt k\lt p$, $\binom pk=\tfrac{p!}{k!(p-k)!}$ is divisible by $p$ (the $p$ in the numerator is not cancelled), and the constant term $p$ is not divisible by $p^2$. Eisenstein at $p$, so $\Phi_p$ is irreducible.
(e) The coefficients are $\tfrac{5!}{k!}$: $1,5,20,60,120,120$ from $x^5$ down. All but the leading one are divisible by $5$, and $25\nmid120$. Eisenstein at $p=5$. (The same works for $p!\sum_{k\le p}x^k/k!$ for every prime $p$; Schur proved that the truncated exponential series is irreducible for every degree.)
Interactive 1 — Eisenstein Scanner: Shifts, Primes and Reduction mod $p$

Choose $f$ and a shift $a$. The top row shows the coefficients of $g(x)=f(x+a)$. Each prime row tests Eisenstein at $p$: the leading cell must be not divisible by $p$, every lower cell divisible by $p$, and the constant not divisible by $p^2$ (green = condition met, red = violated). The last column factors $f$ modulo $p$ — it never changes with the shift, because $x\mapsto x+a$ is an automorphism. Press Play to scan $a=-3,\dots,3$.

shift a—
g(x) = f(x + a)—
Eisenstein primes—
f irreducible mod—
📐 Theorem 7.50 — Reduction modulo $p$
Let $f=a_nx^n+\dots+a_0\in\mathbb{Z}[x]$, $n\ge1$, and let $p$ be a prime with $p\nmid a_n$. Write $\bar f\in\mathbb{F}_p[x]$ for its reduction.
  1. If $f=gh$ in $\mathbb{Z}[x]$ with $\deg g=r$, $\deg h=s$, then $\bar f=\bar g\bar h$ with $\deg\bar g=r$, $\deg\bar h=s$.
  2. Consequently, if $\bar f$ is irreducible over $\mathbb{F}_p$, then $f$ is irreducible over $\mathbb{Q}$.
  3. More generally, the degrees of the factors of any factorisation of $f$ over $\mathbb{Q}$ are sums of degrees of irreducible factors of $\bar f$ — for every such $p$ simultaneously.
The converse of (2) is false: $x^4+1$ is irreducible over $\mathbb{Q}$ but reducible modulo every prime (Example 5).

Proof. (1) $b_rc_s=a_n$ with $p\nmid a_n$, so $p\nmid b_r$ and $p\nmid c_s$, and the reductions keep their degrees; reduction is a ring homomorphism, so $\bar f=\bar g\bar h$. (2) If $f$ were reducible over $\mathbb{Q}$, Theorem 7.45 would give $f=gh$ in $\mathbb{Z}[x]$ with $r,s\ge1$, and (1) a factorisation of $\bar f$ into factors of degrees $r,s\ge1$. (3) In (1), factor $\bar g$ and $\bar h$ into irreducibles in $\mathbb{F}_p[x]$; by unique factorisation these together are the irreducible factors of $\bar f$, and $r$ is the sum of the degrees of those belonging to $\bar g$. ∎

The hypothesis $p\nmid a_n$ cannot be dropped: $2x^2+x=x(2x+1)$ is reducible, yet modulo $2$ it becomes $x$, which is irreducible — the factor $2x+1$ dropped in degree.

✏️ Example 5 — Reduction mod $p$: a certificate, and its limits
(a) Show that $f=x^4+8x+12$ is irreducible over $\mathbb{Q}$, using $f\bmod5$ and $f\bmod17$. (b) Prove that $x^4+1$ is reducible modulo every prime $p$. (c) What do (a) and (b) say about the converse of Theorem 7.50(2)?
(a) mod 5 $\bar f=x^4+3x+2$ has the root $-1$ ($1-3+2=0$), and dividing, $\bar f=(x+1)(x^3+4x^2+x+2)$. The cubic has no root in $\mathbb{F}_5$ (its values at $0,1,2,3,4$ are $2,3,3,3,4$), so it is irreducible (Theorem 7.41). The pattern modulo $5$ is $1+3$.
(a) mod 17 One checks $\bar f=(x^2+4x+7)(x^2+13x+9)$ over $\mathbb{F}_{17}$ (multiply out: $x^3$: $13+4=17$; $x^2$: $9+52+7=68$; $x$: $36+91=127=8+7\cdot17$; constant $63=12+3\cdot17$), and $f$ has no root modulo $17$, so both quadratics are irreducible. The pattern modulo $17$ is $2+2$.
(a) conclude By Theorem 7.50(3), a factorisation of $f$ over $\mathbb{Q}$ into degrees $1+3$ is impossible (modulo $17$ there is no factor of degree $1$), and one into degrees $2+2$ is impossible (modulo $5$ no sum of the degrees $1,3$ equals $2$). So $f$ is irreducible — although, as Interactive 1 shows for small primes, it is reducible modulo every prime (its Galois group is $A_4$, which has no $4$-cycle; see §8.3).
(b) For $p=2$, $x^4+1=(x+1)^4$. Let $p$ be odd. The Legendre symbol is multiplicative (§5.3), so $\left(\tfrac{-1}p\right)\left(\tfrac2p\right)=\left(\tfrac{-2}p\right)$; hence at least one of $-1,\,2,\,-2$ is a square modulo $p$. In each case: $$-1=a^2:\ \ x^4+1=(x^2-a)(x^2+a);$$ $$2=b^2:\ \ x^4+1=(x^2+bx+1)(x^2-bx+1);$$ $$-2=c^2:\ \ x^4+1=(x^2+cx-1)(x^2-cx-1).$$ Each identity is checked by multiplying out: the products are $x^4-a^2$, $x^4+(2-b^2)x^2+1$ and $x^4-(2+c^2)x^2+1$.
(c) Reduction modulo $p$ is a one-way test. It proves irreducibility when some $\bar f$ is irreducible, or — as in (a) — when the patterns at several primes are incompatible with every splitting of the degree. But there are irreducible polynomials, such as $x^4+1$ and $x^4+8x+12$, that are reducible modulo every prime, so failing the test proves nothing.
🧭 Problem-solving strategy — is $f\in\mathbb{Q}[x]$ irreducible?
  1. Normalise. Clear denominators and remove the content: work with a primitive $f\in\mathbb{Z}[x]$ (Theorem 7.45). Remove obvious factors ($x$ if $a_0=0$).
  2. Degree $2$ or $3$: list the candidates $u/v$ with $u\mid a_0$, $v\mid a_n$ and test them. No rational root $\iff$ irreducible.
  3. Eisenstein at each prime dividing all of $a_0,\dots,a_{n-1}$. If none works, reduce $f$ modulo small primes; where $\bar f$ is a constant times $(x-a)^n$, try the shift $x\mapsto x+a$. Also try the reversal $x^nf(1/x)$.
  4. Reduce modulo small primes $p\nmid a_n$. If some $\bar f$ is irreducible, stop: $f$ is irreducible. Otherwise record the degree patterns and intersect the possible splittings of $n$.
  5. Degree $4$ with no rational root: only $2+2$ is left; solve $(x^2+ax+b)(x^2+cx+d)$ over $\mathbb{Z}$ with $bd=a_0$ (finitely many cases).
  6. Recognise shapes: cyclotomic polynomials, $x^n-a$, $x^4+4a^4$ (always reducible), polynomials in $x^2$ or $x^k$, palindromic polynomials ($x^4+ax^3+bx^2+ax+1$: substitute $y=x+1/x$).

Irreducibles over $\mathbb{F}_p$ and Cyclotomic Polynomials

Over a finite field everything can be counted. In degrees $2$ and $3$ the root test (Theorem 7.41) turns counting irreducibles into counting reducible polynomials, which is elementary combinatorics.

📐 Theorem 7.51 — Irreducible quadratics and cubics over $\mathbb{F}_p$
Let $N_p(n)$ denote the number of monic irreducible polynomials of degree $n$ in $\mathbb{F}_p[x]$. Then $N_p(1)=p$, $$N_p(2)=\frac{p^2-p}{2},$$ $$N_p(3)=\frac{p^3-p}{3}.$$ The number of all (not necessarily monic) irreducible polynomials of degree $n$ is $(p-1)N_p(n)$.

Proof. There are $p^n$ monic polynomials of degree $n$. Degree $1$: all $p$ of them, $x-c$, are irreducible. Degree $2$: a reducible monic quadratic is $(x-c)(x-d)$ for an unordered pair $\{c,d\}$ with repetition allowed, and by unique factorisation different pairs give different polynomials; there are $\binom p2+p=\tfrac{p(p+1)}2$ of them, leaving $p^2-\tfrac{p(p+1)}2=\tfrac{p^2-p}2$ irreducible. Degree $3$: a reducible monic cubic has a linear factor, and is either a product of three monic linear factors — a multiset of size $3$ from $p$ roots, $\binom{p+2}{3}$ choices — or (monic linear)(monic irreducible quadratic), $p\cdot\tfrac{p^2-p}2$ choices. Hence $$N_p(3)=p^3-\binom{p+2}{3}-\frac{p^3-p^2}{2}.$$ Since $6\binom{p+2}{3}=p^3+3p^2+2p$, we get $6N_p(3)=6p^3-(p^3+3p^2+2p)-(3p^3-3p^2)$, which is $2p^3-2p$, so $N_p(3)=\tfrac{p^3-p}{3}$. Finally every irreducible of degree $n$ is a unique nonzero constant times a monic irreducible. ∎

For $p=2$: $N_2(2)=1$ ($x^2+x+1$) and $N_2(3)=2$ ($x^3+x+1$, $x^3+x^2+1$). For $p=5$: $N_5(2)=10$, $N_5(3)=40$. In degree $4$ the root test fails — rootless reducible quartics such as $(x^2+x+1)^2$ exist — and a better idea is needed.

📐 Theorem 7.52 — Gauss's formula: $x^{p^n}-x$ and the number of irreducibles
For every prime $p$ and $n\ge1$, $$x^{p^n}-x=\prod_{d\mid n}\ \prod_{\substack{f\text{ monic irreducible}\\ \deg f=d}}f\qquad\text{in }\mathbb{F}_p[x].$$ Comparing degrees, $p^n=\sum_{d\mid n}d\,N_p(d)$, and by Möbius inversion (§5.3) $$N_p(n)=\frac1n\sum_{d\mid n}\mu(d)\,p^{n/d}.$$ In particular $N_p(n)\ge1$: irreducible polynomials of every degree exist over $\mathbb{F}_p$, and $N_p(n)\approx p^n/n$.

Proof. Let $f$ be monic irreducible of degree $d$, and let $K=\mathbb{F}_p[x]/\langle f\rangle$, a field with $p^d$ elements (Theorem 7.43). Let $\alpha=\bar x\in K$. For $g\in\mathbb{F}_p[x]$, $g(\alpha)$ is the coset $\bar g$, so $$g(\alpha)=0\iff f\mid g.\qquad(\ast)$$ The group $K^\times$ has order $p^d-1$, so $b^{p^d-1}=1$ for $b\ne0$ (Lagrange, §6.1) and therefore $b^{p^d}=b$ for every $b\in K$.

If $d\mid n$, iterating $\alpha^{p^d}=\alpha$ gives $\alpha^{p^n}=\alpha$, so $f\mid x^{p^n}-x$ by $(\ast)$.

If $f\mid x^{p^n}-x$, then $\alpha^{p^n}=\alpha$. The Frobenius map $\sigma(b)=b^p$ is a ring homomorphism of $K$ (since $\binom pk\equiv0\pmod p$ for $0\lt k\lt p$, $(b+c)^p=b^p+c^p$), it fixes $\mathbb{F}_p$ (Fermat), and it is injective, hence bijective on the finite set $K$. Every $b\in K$ is $g(\alpha)$ for some $g\in\mathbb{F}_p[x]$, so $\sigma^n(b)=g(\sigma^n(\alpha))=g(\alpha)=b$: $\sigma^n=\mathrm{id}$. Also $\sigma^d=\mathrm{id}$. With $e=\gcd(n,d)=un+vd$ ($u,v\in\mathbb{Z}$) we get $\sigma^e=\mathrm{id}$, i.e. all $p^d$ elements of $K$ are roots of $x^{p^e}-x$. By Theorem 7.38 this needs $p^d\le p^e$, so $d\le e$, hence $d=e\mid n$.

No repeated factors: the derivative of $x^{p^n}-x$ is $-1$, so $\gcd(x^{p^n}-x,\,(x^{p^n}-x)')=1$ (Theorem 7.40). By unique factorisation, $x^{p^n}-x$ is the product of its distinct monic irreducible factors, which are exactly the monic irreducibles of degree dividing $n$. Comparing degrees gives $p^n=\sum_{d\mid n}dN_p(d)$, and Möbius inversion of $F(n)=\sum_{d\mid n}G(d)$ with $G(d)=dN_p(d)$ gives the formula. Finally $nN_p(n)\ge p^n-\sum_{k=1}^{\lfloor n/2\rfloor}p^k\gt p^n-p^{\lfloor n/2\rfloor+1}\ge0$ for $n\ge2$, since every divisor $d\gt1$ of $n$ has $n/d\le n/2$. ∎

$n$123456general
$N_p(n)$$p$$\tfrac{p^2-p}2$$\tfrac{p^3-p}3$$\tfrac{p^4-p^2}4$$\tfrac{p^5-p}5$$\tfrac{p^6-p^3-p^2+p}6$$\tfrac1n\sum_{d\mid n}\mu(d)p^{n/d}$
$p=2$212369
$p=3$3381848116

Over $\mathbb{F}_2$, for instance, $x^8-x=x(x+1)(x^3+x+1)(x^3+x^2+1)$ — degrees $1+1+3+3=8$ — and $x^{16}-x$ is the product of $x$, $x+1$, $x^2+x+1$ and the three irreducible quartics $x^4+x+1$, $x^4+x^3+1$, $x^4+x^3+x^2+x+1$. Interactive 2 sieves all monic polynomials of a given degree and checks the count.

Interactive 2 — Sieving the Monic Polynomials over $\mathbb{F}_p$

Every cell is one monic polynomial of degree $n$ over $\mathbb{F}_p$ (rows: leading coefficients, columns: trailing ones; long labels are written as coefficient strings $1\,a_{n-1}\dots a_0$). Each is factored in turn: red = has a root, amber = no root but reducible, green = irreducible. Amber cells appear only from degree $4$ on — that is why the root test stops at degree $3$. Compare the final green count with Gauss's formula.

monic, degree n—
checked—
with a root—
rootless reducible—
irreducible—
Gauss's formula—
✏️ Example 6 — Irreducibles over $\mathbb{F}_2$ and $\mathbb{F}_3$
(a) List the monic irreducible polynomials of degree $\le4$ over $\mathbb{F}_2$ and check Gauss's formula for $n=4$. (b) Find $N_3(2)$, $N_3(3)$, $N_3(4)$ and check $3^4=\sum_{d\mid4}dN_3(d)$. (c) For which $a\in\mathbb{F}_3$ is $x^2+x+a$ irreducible, and what is the resulting quotient field?
(a) Degrees 1–3 Degree $1$: $x$, $x+1$. Degree $2$: of $x^2,\,x^2+1=(x+1)^2,\,x^2+x=x(x+1),\,x^2+x+1$ only the last has no root. Degree $3$: no root means constant term $1$ (so $0$ is not a root) and an odd number of terms (so $1$ is not a root): $x^3+x+1$ and $x^3+x^2+1$.
(a) Degree 4 The rootless quartics are $x^4+x^3+x^2+x+1$, $x^4+x^3+1$, $x^4+x+1$, $x^4+x^2+1$. The only reducible rootless quartic is a product of two irreducible quadratics, and there is only one such product, $(x^2+x+1)^2=x^4+x^2+1$. So the irreducible quartics are $x^4+x+1$, $x^4+x^3+1$, $x^4+x^3+x^2+x+1$: $N_2(4)=3=\tfrac{16-4}{4}$, and $16=1\cdot2+2\cdot1+4\cdot3$.
(b) $N_3(2)=\tfrac{9-3}2=3$, $N_3(3)=\tfrac{27-3}3=8$, $N_3(4)=\tfrac{81-9}4=18$. Check: $1\cdot3+2\cdot3+4\cdot18=3+6+72=81$.
(c) Values of $x^2+x+a$ at $0,1,2$: $a,\ a+2,\ a+6\equiv a$. It has no root iff $a\ne0$ and $a\ne1$, i.e. $a=2$: $x^2+x+2$ is irreducible, and $\mathbb{F}_3[x]/\langle x^2+x+2\rangle$ is a field with $9$ elements. (For $a=0$: $x(x+1)$; for $a=1$: $x^2+x+1=(x-1)^2$.)

Now we turn to the most important family of polynomials over $\mathbb{Q}$. Recall (§1.1, §6.1) that $\mu_n=\{z\in\mathbb{C}:z^n=1\}=\{e^{2\pi ik/n}:0\le k\lt n\}$ is a cyclic group of order $n$, and that $\zeta\in\mu_n$ is a primitive $n$-th root of unity if it has order exactly $n$, i.e. $\zeta=e^{2\pi ik/n}$ with $\gcd(k,n)=1$; there are $\varphi(n)$ of them.

📘 Definition 7.19 — Cyclotomic polynomial
The $n$-th cyclotomic polynomial is $$\Phi_n(x)=\prod_{\substack{1\le k\le n\\ \gcd(k,n)=1}}\left(x-e^{2\pi ik/n}\right),$$ the monic polynomial whose roots are the primitive $n$-th roots of unity, each once. Thus $\Phi_1=x-1$, $\Phi_2=x+1$, $\Phi_4=(x-i)(x+i)=x^2+1$.
📐 Theorem 7.53 — $x^n-1=\prod_{d\mid n}\Phi_d(x)$
For every $n\ge1$: (1) $x^n-1=\prod_{d\mid n}\Phi_d(x)$; (2) $\deg\Phi_n=\varphi(n)$; (3) $\Phi_n$ is monic with integer coefficients. Consequently $\Phi_n$ can be computed recursively as $\Phi_n=(x^n-1)\big/\prod_{d\mid n,\,d\lt n}\Phi_d$.

Proof. (1) $x^n-1$ has the $n$ distinct roots $\mu_n$, so $x^n-1=\prod_{\zeta\in\mu_n}(x-\zeta)$. Each $\zeta\in\mu_n$ has some order $d$, which divides $n$ (Lagrange in $\mu_n$), and then $\zeta$ is a primitive $d$-th root of unity; conversely every primitive $d$-th root with $d\mid n$ lies in $\mu_n$. Grouping the factors $x-\zeta$ by the order of $\zeta$ gives $\prod_{d\mid n}\Phi_d$. (2) By definition there are $\varphi(n)$ factors. (Comparing degrees in (1) recovers $\sum_{d\mid n}\varphi(d)=n$ from §5.3.)

(3) Strong induction on $n$; $\Phi_1=x-1$. Suppose $\Phi_d\in\mathbb{Z}[x]$ is monic for all $d\lt n$. Then $G=\prod_{d\mid n,\,d\lt n}\Phi_d$ is monic in $\mathbb{Z}[x]$, so the division algorithm in $\mathbb{Z}[x]$ (Theorem 7.37 — the divisor is monic) gives $x^n-1=QG+R$ with $Q,R\in\mathbb{Z}[x]$, $\deg R\lt\deg G$. In $\mathbb{C}[x]$ we also have $x^n-1=\Phi_n\cdot G+0$, and division in $\mathbb{C}[x]$ is unique, so $\Phi_n=Q\in\mathbb{Z}[x]$; it is monic as a product of monic factors. ∎

📐 Theorem 7.54 — Irreducibility of cyclotomic polynomials
  1. For a prime $p$ and $k\ge1$, $\Phi_{p^k}(x)=\Phi_p\!\left(x^{p^{k-1}}\right)$, that is, $1+y+\dots+y^{p-1}$ with $y=x^{p^{k-1}}$; and $\Phi_{p^k}$ is irreducible over $\mathbb{Q}$.
  2. (Gauss for $n$ prime; Kronecker and Dedekind in general.) $\Phi_n$ is irreducible over $\mathbb{Q}$ for every $n\ge1$. Hence $\Phi_n$ is the minimal polynomial over $\mathbb{Q}$ of every primitive $n$-th root of unity, and the factorisation $x^n-1=\prod_{d\mid n}\Phi_d$ is the factorisation into irreducibles over $\mathbb{Q}$ — it has exactly $\tau(n)$ factors.

Proof. (1) The roots of $x^{p^k}-1$ that are not primitive $p^k$-th roots are exactly those of order dividing $p^{k-1}$, i.e. the roots of $x^{p^{k-1}}-1$. So $\Phi_{p^k}=\dfrac{x^{p^k}-1}{x^{p^{k-1}}-1}=\dfrac{y^p-1}{y-1}$ with $y=x^{p^{k-1}}$, which is $\Phi_p(y)$. Now shift: let $g(x)=\Phi_{p^k}(x+1)$, so $g(x)\big((x+1)^{p^{k-1}}-1\big)=(x+1)^{p^k}-1$. Modulo $p$, $(x+1)^{p^j}\equiv x^{p^j}+1$ (apply $(u+v)^p\equiv u^p+v^p$ $j$ times), so $\bar g\cdot x^{p^{k-1}}=x^{p^k}$ in $\mathbb{F}_p[x]$, and cancelling in the domain $\mathbb{F}_p[x]$, $\bar g=x^{p^k-p^{k-1}}$. So every non-leading coefficient of the monic $g$ is divisible by $p$, and its constant term is $g(0)=\Phi_{p^k}(1)=1+1+\dots+1=p$, not divisible by $p^2$. Eisenstein at $p$ and Theorem 7.49 finish the proof.

(2) Proof sketch with all key steps. Let $\zeta$ be a primitive $n$-th root of unity and $f$ the monic polynomial of least degree in $\mathbb{Q}[x]$ with $f(\zeta)=0$. The polynomials vanishing at $\zeta$ form an ideal of $\mathbb{Q}[x]$, generated by $f$ (Theorem 7.39(1)); $f$ is irreducible (a factorisation would give a factor of smaller degree vanishing at $\zeta$), and $f\mid\Phi_n$. By Gauss's lemma $f\in\mathbb{Z}[x]$ and $\Phi_n=fh$ with $h\in\mathbb{Z}[x]$ monic. Claim: if $p\nmid n$ is prime then $f(\zeta^p)=0$. If not, $\zeta^p$ (also a primitive $n$-th root) is a root of $h$, so $\zeta$ is a root of $h(x^p)$ and $f(x)\mid h(x^p)$ in $\mathbb{Z}[x]$. Reduce modulo $p$: $\bar h(x^p)=\bar h(x)^p$ (Frobenius, using $\bar c^{\,p}=\bar c$ for coefficients), so $\bar f\mid\bar h^p$, and some irreducible factor of $\bar f$ also divides $\bar h$. Then it divides $\bar f\bar h=\bar\Phi_n$ twice, so $x^n-1$ has a repeated factor in $\mathbb{F}_p[x]$ — impossible since $p\nmid n$ (Theorem 7.40, as noted after it). Applying the claim repeatedly, $f(\zeta^k)=0$ for every $k$ coprime to $n$ (factor $k$ into primes not dividing $n$). So all $\varphi(n)$ roots of $\Phi_n$ are roots of $f$, and $f=\Phi_n$. The last sentence follows from Theorem 7.53(1) and the uniqueness of factorisation in $\mathbb{Q}[x]$. ∎

📐 Theorem 7.55 — Rules for computing $\Phi_n$
  1. $\Phi_n(0)=1$ for $n\ge2$.
  2. $\Phi_n(1)=p$ if $n=p^k$ ($p$ prime, $k\ge1$), and $\Phi_n(1)=1$ if $n$ has at least two distinct prime factors.
  3. $\Phi_{2n}(x)=\Phi_n(-x)$ for odd $n\ge3$.
  4. For a prime $p$: $\Phi_{pn}(x)=\Phi_n(x^p)$ if $p\mid n$, and $\Phi_{pn}(x)=\Phi_n(x^p)/\Phi_n(x)$ if $p\nmid n$.
  5. (Proved in §8.2.) If $p\nmid n$, then modulo $p$, $\Phi_n$ is a product of $\varphi(n)/m$ distinct irreducibles, each of degree $m=\operatorname{ord}_n(p)$, the order of $p$ in $U(n)$.

Proof of (2) and (3). (2) Dividing $x^n-1=\prod_{d\mid n}\Phi_d$ by $\Phi_1=x-1$ gives $$1+x+\dots+x^{n-1}=\prod_{d\mid n,\ d\gt1}\Phi_d(x),$$ and at $x=1$: $$n=\prod_{d\mid n,\ d\gt1}\Phi_d(1).$$ We saw $\Phi_{p^j}(1)=p$ in Theorem 7.54(1). Now induct on $n$. If $n=p_1^{a_1}\cdots p_r^{a_r}$ with $r\ge2$, the prime-power divisors $d=p_i^j$ ($1\le j\le a_i$) already contribute $\prod_ip_i^{a_i}=n$, and every other divisor $d$ with $1\lt d\lt n$ has at least two distinct prime factors and contributes $\Phi_d(1)=1$ by induction; what is left is $n=n\cdot\Phi_n(1)$, so $\Phi_n(1)=1$. (3) For odd $n\ge3$, $\zeta\mapsto-\zeta$ maps the primitive $n$-th roots bijectively onto the primitive $2n$-th roots: $-1$ has order $2$, $\zeta$ has order $n$, they commute and $\gcd(2,n)=1$, so $-\zeta$ has order $2n$, and both sets have $\varphi(n)=\varphi(2n)$ elements. Since $\varphi(n)$ is even, $$\Phi_n(-x)=\prod(-x-\zeta)=\prod\big(x-(-\zeta)\big),$$ which is $\Phi_{2n}(x)$. Parts (1) and (4) are Exercises IV.3 and IV.5. ∎

Small cases$\Phi_3=x^2+x+1$, $\Phi_6=x^2-x+1$, $\Phi_8=x^4+1$, $\Phi_9=x^6+x^3+1$, $\Phi_{10}=x^4-x^3+x^2-x+1$, $\Phi_{12}=x^4-x^2+1$.
CoefficientsFor $n\lt105$ all coefficients lie in $\{-1,0,1\}$, but $\Phi_{105}$ (degree $48$) has the coefficient $-2$, at $x^7$ and at $x^{41}$.
Second coefficientThe sum of the primitive $n$-th roots of unity is $\mu(n)$, so $\Phi_n=x^{\varphi(n)}-\mu(n)x^{\varphi(n)-1}+\cdots$ (Exercise IV.7).
✏️ Example 7 — Computing and factoring with cyclotomic polynomials
(a) Compute $\Phi_{12}$ and factor $x^{12}-1$ into irreducibles over $\mathbb{Q}$. (b) Compute $\Phi_{18}$ and $\Phi_{30}$ using Theorem 7.55, given $\Phi_{15}=x^8-x^7+x^5-x^4+x^3-x+1$. (c) Factor $\Phi_7$ over $\mathbb{F}_2$ and $\Phi_8=x^4+1$ over $\mathbb{F}_3$, and compare the degrees with Theorem 7.55(5).
(a) The divisors of $12$ are $1,2,3,4,6,12$. Since $\Phi_1\Phi_2\Phi_3\Phi_6=x^6-1$ and $\Phi_4=x^2+1$, $$\Phi_{12}=\frac{x^{12}-1}{(x^6-1)(x^2+1)}=\frac{x^6+1}{x^2+1}=x^4-x^2+1.$$ So $x^{12}-1=(x-1)(x+1)(x^2+x+1)(x^2+1)(x^2-x+1)(x^4-x^2+1)$, and by Theorem 7.54 these $\tau(12)=6$ factors are irreducible over $\mathbb{Q}$. Check: degrees $1+1+2+2+2+4=12$.
(b) $18=3\cdot6$ with $3\mid6$, so $\Phi_{18}(x)=\Phi_6(x^3)=x^6-x^3+1$ (Theorem 7.55(4)); equivalently $\Phi_{18}(x)=\Phi_9(-x)$ by (3). And $\Phi_{30}(x)=\Phi_{15}(-x)=x^8+x^7-x^5-x^4-x^3+x+1$ (odd powers change sign).
(c) $\operatorname{ord}_7(2)=3$ ($2^3=8\equiv1$), so $\Phi_7$ (degree $6$) should split over $\mathbb{F}_2$ into $6/3=2$ cubics: indeed $\Phi_7=(x^3+x+1)(x^3+x^2+1)$ — the two irreducible cubics of Example 6. For $\Phi_8$ and $p=3$: $3^2=9\equiv1\pmod8$, so two quadratics: $x^4+1=(x^2+x+2)(x^2+2x+2)$ over $\mathbb{F}_3$ (multiply out: $x^3$: $2+1=3$; $x^2$: $2+2+2=6$; $x$: $4+2=6$; constant $4$; all $\equiv$ the coefficients $0,0,0,1$).
Moral Every odd $p$ has $p^2\equiv1\pmod 8$, so $\operatorname{ord}_8(p)\le2$ and $x^4+1$ splits into quadratics or linear factors modulo every odd prime — a second explanation of Example 5(b).
⚠️ Counterexamples and pitfalls
  1. No root does not mean irreducible (degree $\ge4$). $(x^2+1)^2$ over $\mathbb{R}$, $x^4+4=(x^2+2x+2)(x^2-2x+2)$ and $x^4+x^2+1=(x^2+x+1)(x^2-x+1)$ over $\mathbb{Q}$, $(x^2+x+1)^2$ over $\mathbb{F}_2$.
  2. Irreducibility depends on the field. $x^2+1$: irreducible over $\mathbb{R}$, $\mathbb{Q}$, $\mathbb{F}_3$; reducible over $\mathbb{C}$, $\mathbb{F}_2$, $\mathbb{F}_5$. $x^2-2$: irreducible over $\mathbb{Q}$, reducible over $\mathbb{R}$ and over $\mathbb{F}_7$ ($3^2=2$).
  3. Over $\mathbb{Z}$ constants count. $2x+4=2(x+2)$ is reducible in $\mathbb{Z}[x]$ but irreducible in $\mathbb{Q}[x]$; Eisenstein proves irreducibility in $\mathbb{Z}[x]$ only for primitive polynomials ($3x+6$ is Eisenstein at $2$ yet $3(x+2)$ in $\mathbb{Z}[x]$).
  4. Eisenstein is sufficient, not necessary. $x^2+1$ is not Eisenstein at any prime; $x^4-10x^2+1$ is irreducible but $f(x+a)$ is Eisenstein for no $a$ and no $p$.
  5. Reduction mod $p$ works one way only. $x^4+1$ and $x^4+8x+12$ are irreducible over $\mathbb{Q}$ but reducible modulo every prime. And $p\nmid a_n$ is essential: $2x^2+x$ is reducible, yet $\equiv x\pmod 2$.
  6. Root counts fail without a domain. $x^2-1$ has $4$ roots in $\mathbb{Z}_8$; $x^3-x$ vanishes on all of $\mathbb{Z}_6$; $x^2+1$ has infinitely many roots in $\mathbb{H}$.
  7. Polynomials are not functions over finite fields. $x^p-x\ne0$ in $\mathbb{F}_p[x]$, but it is the zero function on $\mathbb{F}_p$.
  8. Degree and units in $R[x]$ for non-domains. In $\mathbb{Z}_4[x]$, $(2x)^2=0$ and $(1+2x)^2=1$: $\deg(fg)\lt\deg f+\deg g$ and non-constant units exist.
  9. $x^p-a$ over $\mathbb{F}_p$ is never irreducible. $x^p-a=(x-a)^p$ (Frobenius and Fermat). Over $\mathbb{F}_p(t)$, however, $x^p-t$ is irreducible with a single repeated root — the standard inseparable polynomial (§8.1).
  10. Monic or not? The number of monic irreducible cubics over $\mathbb{F}_5$ is $40$; counting all irreducible cubics gives $4\cdot40=160$. Read the question.
  11. Cyclotomic myths. Coefficients are not always in $\{-1,0,1\}$ ($\Phi_{105}$); $\Phi_n(1)$ is $p$ for prime powers, not always $1$; and $\Phi_n$, irreducible over $\mathbb{Q}$, usually factors modulo $p$ (Theorem 7.55(5)).
  12. $\mathbb{Z}[x]/\langle f\rangle$ is never a field. $\mathbb{Q}[x]/\langle f\rangle$ is a field for irreducible $f$, but $\mathbb{Z}[x]/\langle f\rangle$ is not (e.g. $\mathbb{Z}[x]/\langle x\rangle\cong\mathbb{Z}$); one needs a second generator, as in $\mathbb{Z}[x]/\langle3,x^2+1\rangle\cong\mathbb{F}_9$.

Exercises

I
Arithmetic in $R[x]$: division, gcd, roots.
  • 1 Divide $x^5+2x^3-x+4$ by $x^2-x+2$ in $\mathbb{Q}[x]$.
  • 2 Divide $3x^4+5x^2+x+6$ by $2x^2+3$ in $\mathbb{F}_7[x]$.
  • 3 Find $d=\gcd(x^4+x^3+2x^2+x+1,\ x^3-1)$ in $\mathbb{Q}[x]$ and write $d$ in Bézout form.
  • 4 Find all roots of $x^3-x$ in $\mathbb{Z}_6$ and of $x^2+1$ in $\mathbb{Z}_{65}$. Why does this not contradict Theorem 7.38?
  • 5 Show that $1+3x$ is a unit of $\mathbb{Z}_9[x]$, find its inverse, and show that $3x$ is nilpotent.
  • 6 Let $D$ be an integral domain. Prove that $D[x]$ is not a field, and that $\langle x\rangle$ is a maximal ideal of $D[x]$ if and only if $D$ is a field.
  • 7 Prove that $\gcd(x^m-1,\,x^n-1)=x^{\gcd(m,n)}-1$ in $F[x]$ for every field $F$ and $m,n\ge1$.
  • 8 Find all $c\in\mathbb{C}$ for which $x^3-3x+c$ has a repeated root, and factor the polynomial in each case.
1 $q=x^3+x^2+x-1$, $r=-4x+6$. Check: $(x^2-x+2)(x^3+x^2+x-1)=x^5+2x^3+3x-2$, and adding $-4x+6$ gives $x^5+2x^3-x+4$.
2 $2^{-1}=4$ in $\mathbb{F}_7$. $q=5x^2+2$, $r=x$. Check: $(2x^2+3)(5x^2+2)=10x^4+19x^2+6\equiv3x^4+5x^2+6$, plus $x$.
3 $x^4+x^3+2x^2+x+1=(x+1)(x^3-1)+(2x^2+2x+2)$, and $x^3-1=(x-1)(x^2+x+1)$ is divisible by $x^2+x+1$. So $d=x^2+x+1=\tfrac12\left(x^4+x^3+2x^2+x+1\right)-\tfrac{x+1}{2}\left(x^3-1\right)$. (Indeed the quartic is $(x^2+1)(x^2+x+1)$.)
4 $n^3-n=(n-1)n(n+1)$ is divisible by $6$, so all six elements of $\mathbb{Z}_6$ are roots. $x^2\equiv-1\pmod{65}$ means $x\equiv\pm2\pmod5$ and $x\equiv\pm5\pmod{13}$; the CRT gives four roots $8,18,47,57$. Theorem 7.38(3) needs an integral domain, and $\mathbb{Z}_6$, $\mathbb{Z}_{65}$ are not.
5 $(1+3x)(1+6x)=1+9x+18x^2=1$ in $\mathbb{Z}_9[x]$, so $(1+3x)^{-1}=1+6x$. $(3x)^2=9x^2=0$. (This is the general rule: $1+$nilpotent is a unit, with inverse $1-N+N^2-\cdots$.)
6 $x$ is not a unit by Theorem 7.36(2), so $D[x]$ is not a field. The evaluation $f\mapsto f(0)$ is a surjective homomorphism $D[x]\to D$ with kernel $\langle x\rangle$ (factor theorem), so $D[x]/\langle x\rangle\cong D$, and $\langle x\rangle$ is maximal iff this quotient is a field (§7.2) iff $D$ is a field. For $D=\mathbb{Z}$: $\langle x\rangle$ is prime but not maximal ($\langle x\rangle\subsetneq\langle2,x\rangle$).
7 Write $m=qn+r$, $0\le r\lt n$. Then $x^m-1=x^r(x^{qn}-1)+(x^r-1)$ and $x^n-1\mid x^{qn}-1$, so the remainder of $x^m-1$ modulo $x^n-1$ is $x^r-1$. Thus Euclid's algorithm on $(x^m-1,x^n-1)$ runs exactly parallel to Euclid's algorithm on $(m,n)$ and ends with $x^{\gcd(m,n)}-1$ (when $r=0$, $x^0-1=0$ signals termination).
8 A repeated root satisfies $f'=3x^2-3=0$, so $x=\pm1$. $f(1)=c-2=0$ gives $c=2$: $x^3-3x+2=(x-1)^2(x+2)$. $f(-1)=c+2=0$ gives $c=-2$: $x^3-3x-2=(x+1)^2(x-2)$.
II
Irreducibility over $\mathbb{Q}$ and in $\mathbb{Z}[x]$.
  • 1 Factor $3x^3-5x^2+5x-2$ into irreducibles over $\mathbb{Q}$.
  • 2 Decide irreducibility over $\mathbb{Q}$: (a) $x^3+x^2+x+2$; (b) $2x^5-6x^3+9x^2-15$; (c) $x^4+x^2+1$.
  • 3 Show that $x^4-4x^3+6x^2-4x+3$ is irreducible over $\mathbb{Q}$ by substituting $x\mapsto x+1$.
  • 4 Show that $3x^4+6x^3+9x+1$ is not Eisenstein at any prime, but its reversal is; deduce that it is irreducible over $\mathbb{Q}$.
  • 5 Prove that $x^n-p$ is irreducible over $\mathbb{Q}$ for every prime $p$ and $n\ge1$, and that $\sqrt[n]{p}\notin\mathbb{Q}$ for $n\ge2$.
  • 6 Verify that $x^4+4a^4$ equals $$(x^2+2ax+2a^2)(x^2-2ax+2a^2);$$ factor $x^4+64$ over $\mathbb{Q}$; and show that $n^4+4$ is prime only for $n=1$ ($n\in\mathbb{N}$).
  • 7 Prove that $x^4+3x^3+7x^2-5x+1$ is irreducible over $\mathbb{Q}$ by reducing modulo $2$.
  • 8 Give an example showing that the reduction test fails if $p$ divides the leading coefficient, and explain where the proof breaks.
  • 9 Which of $2x+4$, $3x^2+6$, $5$, $2x+3$ are irreducible in $\mathbb{Z}[x]$? Which are irreducible in $\mathbb{Q}[x]$?
1 Candidates $\pm1,\pm2,\pm\tfrac13,\pm\tfrac23$. At $\tfrac23$: $\tfrac89-\tfrac{20}9+\tfrac{30}9-\tfrac{18}9=0$. Dividing: $(3x-2)(x^2-x+1)$, and $x^2-x+1$ has discriminant $-3$, so it is irreducible.
2 (a) Irreducible: a cubic whose candidate roots $\pm1,\pm2$ give $5,1,16,-4$, all nonzero. (b) Irreducible: Eisenstein at $3$ ($3\nmid2$; $3\mid0,-6,9,0,-15$; $9\nmid15$). (c) Reducible: $x^4+x^2+1=(x^2+1)^2-x^2=(x^2+x+1)(x^2-x+1)$, although it has no real root.
3 The polynomial is $(x-1)^4+2$, so substituting $x\mapsto x+1$ gives $x^4+2$, Eisenstein at $2$. By Theorem 7.49 the original is irreducible.
4 The constant term $1$ is divisible by no prime, so $f=3x^4+6x^3+9x+1$ is not Eisenstein. Its reversal is $x^4f(1/x)=x^4+9x^3+0x^2+6x+3$: Eisenstein at $3$ ($3\nmid1$; $3\mid9,0,6,3$; $9\nmid3$). Since $f(0)=1\ne0$, Theorem 7.49 says $f$ is irreducible iff its reversal is.
5 Eisenstein at $p$: coefficients $1,0,\dots,0,-p$ with $p^2\nmid p$. If $\sqrt[n]p=u/v$ were rational with $n\ge2$, then $x-u/v$ would be a factor of degree $1\lt n$ of $x^n-p$.
6 $(x^2+2a^2)^2-(2ax)^2=x^4+4a^2x^2+4a^4-4a^2x^2$. With $a=2$: $x^4+64=(x^2+4x+8)(x^2-4x+8)$, both with negative discriminant, so irreducible. $n^4+4=(n^2+2n+2)(n^2-2n+2)$ and $n^2-2n+2=(n-1)^2+1$ equals $1$ only for $n=1$ (giving the prime $5$); for $n\ge2$ both factors exceed $1$.
7 Modulo $2$: $x^4+x^3+x^2+x+1$. It has no root ($f(0)=1$, $f(1)=5\equiv1$), and it is not the only rootless reducible quartic $(x^2+x+1)^2=x^4+x^2+1$; so it is irreducible over $\mathbb{F}_2$, and the leading coefficient $1$ is odd. By Theorem 7.50, the original is irreducible over $\mathbb{Q}$.
8 $f=2x^2+x=x(2x+1)$ is reducible, but $\bar f=x$ modulo $2$ is irreducible. In the proof, $\bar g=x$, $\bar h=\overline{2x+1}=1$: the factor $h$ lost its degree because its leading coefficient vanished modulo $2$.
9 In $\mathbb{Z}[x]$: $2x+4=2(x+2)$ and $3x^2+6=3(x^2+2)$ are reducible (non-unit constants); $5$ is irreducible (a prime of $\mathbb{Z}$); $2x+3$ is irreducible (primitive of degree $1$). In $\mathbb{Q}[x]$: $2x+4$, $3x^2+6$ (no rational root of $x^2+2$) and $2x+3$ are irreducible; $5$ is a unit, hence not irreducible.
III
Over $\mathbb{R}$, $\mathbb{C}$ and finite fields.
  • 1 Factor $x^4+1$ into monic irreducibles over $\mathbb{C}$, $\mathbb{R}$, $\mathbb{Q}$, $\mathbb{F}_2$ and $\mathbb{F}_3$.
  • 2 List the monic irreducible quadratics over $\mathbb{F}_3$, and the monic irreducible quartics over $\mathbb{F}_2$.
  • 3 Compute $N_3(4)$ and $N_2(6)$ from Gauss's formula, and check $2^6=\sum_{d\mid6}dN_2(d)$.
  • 4 For which primes $p$ is $x^2+1$ irreducible over $\mathbb{F}_p$?
  • 5 Show that $\mathbb{F}_2[x]/\langle x^3+x+1\rangle$ is a field with $8$ elements, and find the inverse of $\overline{x^2+1}$ in it.
  • 6 Show that $\mathbb{Z}_5[x]/\langle x^2+2\rangle$ is a field with $25$ elements, while $\mathbb{Z}_5[x]/\langle x^2+1\rangle\cong\mathbb{Z}_5\times\mathbb{Z}_5$.
  • 7 Show that $x^p-x+1$ has no root in $\mathbb{F}_p$ and is irreducible for $p=2,3$. Challenge: prove it is irreducible over $\mathbb{F}_p$ for every prime $p$, using that if $\alpha$ is a root in some field containing $\mathbb{F}_p$ then so is $\alpha+1$.
  • 8 Prove that $x^p-a=(x-a)^p$ in $\mathbb{F}_p[x]$ for every $a\in\mathbb{F}_p$. How many monic irreducible binomials $x^p-a$ are there over $\mathbb{F}_p$?
1 $\mathbb{C}$: $\prod_{k=0}^{3}\left(x-e^{i\pi(2k+1)/4}\right)$. $\mathbb{R}$: pair conjugates, $(x^2+\sqrt2x+1)(x^2-\sqrt2x+1)$. $\mathbb{Q}$: irreducible (Example 4(b)). $\mathbb{F}_2$: $(x+1)^4$. $\mathbb{F}_3$: $(x^2+x+2)(x^2+2x+2)$ (Example 7(c)).
2 Over $\mathbb{F}_3$: $x^2+1$, $x^2+x+2$, $x^2+2x+2$ (three, as $N_3(2)=3$; each has no root among $0,1,2$). Over $\mathbb{F}_2$: $x^4+x+1$, $x^4+x^3+1$, $x^4+x^3+x^2+x+1$ (Example 6).
3 $N_3(4)=\tfrac14(3^4-3^2)=18$. $N_2(6)=\tfrac16\left(2^6-2^3-2^2+2^1\right)=\tfrac{54}{6}=9$ (divisors $1,2,3,6$ with $\mu=1,-1,-1,1$). Check: $1\cdot2+2\cdot1+3\cdot2+6\cdot9=2+2+6+54=64$.
4 A quadratic is irreducible iff it has no root, i.e. iff $-1$ is not a square modulo $p$. For $p=2$, $x^2+1=(x+1)^2$. For odd $p$, $-1$ is a square iff $p\equiv1\pmod4$ (Euler's criterion, §5.3). So $x^2+1$ is irreducible exactly for $p\equiv3\pmod4$.
5 $x^3+x+1$ has no root in $\mathbb{F}_2$ ($1$ at both points), so it is irreducible and the quotient is a field with $2^3=8$ elements (Theorem 7.43). Since $\bar x^3=\bar x+1$: $(\bar x^2+1)\bar x=\bar x^3+\bar x=\bar x+1+\bar x=1$. So $(\overline{x^2+1})^{-1}=\bar x$.
6 The squares in $\mathbb{F}_5$ are $0,1,4$, and $-2=3$ is not one, so $x^2+2$ has no root: irreducible, field with $25$ elements. But $-1=4=2^2$, so $x^2+1=(x-2)(x+2)$ with coprime factors, and the Chinese remainder theorem gives $\mathbb{Z}_5[x]/\langle x^2+1\rangle\cong\mathbb{Z}_5[x]/\langle x-2\rangle\times\mathbb{Z}_5[x]/\langle x+2\rangle\cong\mathbb{Z}_5\times\mathbb{Z}_5$, which has zero divisors such as $\overline{x-2}$.
7 For $c\in\mathbb{F}_p$, $c^p-c+1=1\ne0$ (Fermat). For $p=2,3$ the degree is $2,3$, so no root means irreducible. General $p$: if $\alpha^p-\alpha+1=0$ then $(\alpha+1)^p-(\alpha+1)+1=\alpha^p+1-\alpha-1+1=0$, so the roots are $\alpha,\alpha+1,\dots,\alpha+p-1$, all distinct. A monic factor $g$ of degree $d$, $0\lt d\lt p$, is $\prod_{k\in S}(x-\alpha-k)$ for some $S\subseteq\mathbb{F}_p$ of size $d$; its $x^{d-1}$-coefficient $-\left(d\alpha+\sum_{k\in S}k\right)$ lies in $\mathbb{F}_p$, and $d$ is invertible in $\mathbb{F}_p$, so $\alpha\in\mathbb{F}_p$ — but there is no root in $\mathbb{F}_p$. Hence $x^p-x+1$ is irreducible. (So $x^5-x-1$, which is $\equiv x^5-x+4$, needs the version with constant $a\ne0$, proved the same way: it is irreducible mod $5$, as Interactive 1 shows.)
8 $(x-a)^p=x^p+\sum_{0\lt k\lt p}\binom pk x^k(-a)^{p-k}+(-a)^p=x^p+(-a)^p$, and $(-a)^p=-a^p=-a$ for odd $p$ (Fermat); for $p=2$, $(-a)^2=a^2=a=-a$. So $x^p-a=(x-a)^p$, which is reducible since $p\ge2$. There are no irreducible ones.
IV
Cyclotomic polynomials.
  • 1 Compute $\Phi_{10}$, $\Phi_{12}$ and $\Phi_{18}$.
  • 2 Factor $x^{12}-1$ and $x^{8}-1$ into irreducibles over $\mathbb{Q}$. How many irreducible factors does $x^n-1$ have over $\mathbb{Q}$ in general?
  • 3 Prove that $\Phi_n(0)=1$ for $n\ge2$.
  • 4 Using $\Phi_{2n}(x)=\Phi_n(-x)$ ($n$ odd, $n\ge3$), compute $\Phi_{30}$ from $\Phi_{15}=x^8-x^7+x^5-x^4+x^3-x+1$, and $\Phi_{14}$ from $\Phi_7$.
  • 5 Prove Theorem 7.55(4), and check it on $\Phi_3(x^2)=\Phi_6(x)\Phi_3(x)$.
  • 6 Factor $\Phi_7$ over $\mathbb{F}_2$ and predict the degrees of the irreducible factors of $\Phi_{13}$ over $\mathbb{F}_3$.
  • 7 Show that the sum of the primitive $n$-th roots of unity is $\mu(n)$, so the coefficient of $x^{\varphi(n)-1}$ in $\Phi_n$ is $-\mu(n)$. Check for $n=5,12,15$.
  • 8 Let $p$ be a prime with $p\nmid n$, and $a\in\mathbb{Z}$ with $p\mid\Phi_n(a)$. Prove that $a$ has order exactly $n$ modulo $p$, so $p\equiv1\pmod n$. Deduce that there are infinitely many primes $\equiv1\pmod n$.
1 $\Phi_{10}(x)=\Phi_5(-x)=x^4-x^3+x^2-x+1$. $\Phi_{12}=x^4-x^2+1$ (Example 7). $\Phi_{18}(x)=\Phi_6(x^3)=x^6-x^3+1$.
2 $x^{12}-1$: Example 7(a), six factors. $x^8-1=\Phi_1\Phi_2\Phi_4\Phi_8=(x-1)(x+1)(x^2+1)(x^4+1)$. In general $x^n-1$ has exactly $\tau(n)$ irreducible factors over $\mathbb{Q}$, one $\Phi_d$ for each divisor $d$ (Theorem 7.54).
3 $\Phi_n(0)=\prod(-\zeta)=(-1)^{\varphi(n)}\prod\zeta$. For $n\ge3$, $\varphi(n)$ is even and the primitive roots pair off as $\zeta,\zeta^{-1}=\bar\zeta$ with $\zeta\ne\zeta^{-1}$, so the product is $1$. For $n=2$, $\Phi_2(0)=1$. (Alternatively evaluate $x^n-1=\prod_{d\mid n}\Phi_d$ at $0$ and induct.)
4 Replace $x$ by $-x$ (flip the signs of odd powers): $\Phi_{30}=x^8+x^7-x^5-x^4-x^3+x+1$ and $\Phi_{14}=x^6-x^5+x^4-x^3+x^2-x+1$.
5 The roots of $\Phi_n(x^p)$ are the $\beta$ with $\beta^p$ a primitive $n$-th root; there are $p\varphi(n)$ of them, all distinct (each $\zeta$ has $p$ distinct $p$-th roots). If $\beta$ has order $m$, then $\beta^p$ has order $m/\gcd(m,p)$, which must be $n$: so $m=n$ (possible only if $p\nmid n$) or $m=pn$. If $p\mid n$, every root has order $pn$; since $\varphi(pn)=p\varphi(n)$, the roots are exactly the primitive $pn$-th roots, and $\Phi_n(x^p)=\Phi_{pn}(x)$ (both monic). If $p\nmid n$, the roots are the primitive $n$-th roots ($\beta=\zeta^{p'}$ with $pp'\equiv1$) and the primitive $pn$-th roots: $\varphi(n)+(p-1)\varphi(n)=p\varphi(n)$ ✓, so $\Phi_n(x^p)=\Phi_n(x)\Phi_{pn}(x)$. Check: $x^4+x^2+1=(x^2-x+1)(x^2+x+1)$.
6 $\Phi_7=(x^3+x+1)(x^3+x^2+1)$ over $\mathbb{F}_2$ (Example 7(c)). $\operatorname{ord}_{13}(3)=3$ ($3^3=27\equiv1$), so $\Phi_{13}$ (degree $12$) splits over $\mathbb{F}_3$ into four irreducible cubics.
7 Let $s(d)$ be the sum of the primitive $d$-th roots. Grouping $\mu_n$ by order, $\sum_{d\mid n}s(d)=\sum_{\zeta\in\mu_n}\zeta$, which is $0$ for $n\gt1$ (the coefficient of $x^{n-1}$ in $x^n-1$) and $1$ for $n=1$. Möbius inversion (§5.3) gives $s(n)=\sum_{d\mid n}\mu(d)\cdot[n/d=1]=\mu(n)$. The coefficient of $x^{\varphi(n)-1}$ in $\prod(x-\zeta)$ is $-s(n)$. Checks: $\Phi_5=x^4+x^3+\cdots$, $-\mu(5)=1$ ✓; $\Phi_{12}=x^4+0x^3-\cdots$, $\mu(12)=0$ ✓; $\Phi_{15}=x^8-x^7+\cdots$, $-\mu(15)=-1$ ✓.
8 $\Phi_n(a)\equiv0$ and $\Phi_n\mid x^n-1$ give $a^n\equiv1\pmod p$. Let $m=\operatorname{ord}_p(a)$; then $m\mid n$. If $m\lt n$, then $a$ is a root mod $p$ of $x^m-1=\prod_{d\mid m}\Phi_d$, so $\bar\Phi_d(\bar a)=0$ for some $d\mid m$, $d\lt n$. Both $\Phi_n$ and $\Phi_d$ are distinct factors of $x^n-1$, so $(x-\bar a)^2\mid x^n-1$ in $\mathbb{F}_p[x]$ — impossible, since $x^n-1$ has no repeated factors modulo $p\nmid n$. So $m=n$, and $n\mid p-1$ by Fermat. For infinitude (take $n\ge2$; for $n=1$ there is nothing to prove): given primes $p_1,\dots,p_k\equiv1\pmod n$, let $N=n\,p_1\cdots p_k\,t$ with $t$ a large integer. Then $\Phi_n(N)\equiv\Phi_n(0)=1\pmod N$ (Exercise 3), and $|\Phi_n(N)|\ge(N-1)^{\varphi(n)}\gt1$, so $\Phi_n(N)$ has a prime factor $p$, which divides neither $N$ nor hence $n$ or any $p_i$. By the first part $p\equiv1\pmod n$ — a new one.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

E1. CSIR Part B GATE MA The number of monic irreducible polynomials of degree $3$ over the field $\mathbb{Z}_5$ is (A) $20$; (B) $40$; (C) $60$; (D) $120$.

Idea $N_p(3)=\tfrac{p^3-p}{3}$ (Theorem 7.51): subtract the monic cubics with a root from the $125$ monic cubics.
Count Reducible monic cubics: $\binom{7}{3}=35$ products of three linear factors, plus $5\cdot10=50$ (linear)$\times$(irreducible quadratic): $125-85=40$. (D) $120=5^3-5$ forgets to divide by $3$; (A) halves the right answer; (C) is $\tfrac{5^3-5}{2}$.
Answer (B) $40$.

E2. CSIR Part B Which of the following polynomials is irreducible over $\mathbb{Q}$? (A) $x^4+4$; (B) $x^4+x^2+1$; (C) $x^4+3x^3+3x^2+3x+6$; (D) $x^4-16$.

Options (A) $(x^2+2x+2)(x^2-2x+2)$, the Sophie Germain identity. (B) $(x^2+x+1)(x^2-x+1)$. (D) $(x-2)(x+2)(x^2+4)$. (C) Eisenstein at $3$: $3\nmid1$, $3\mid3,3,3,6$, $9\nmid6$.
Answer (C). Note (A) and (B) have no rational roots — the degree-$4$ trap.

E3. CSIR Part B For how many $a\in\mathbb{Z}_3$ is the quotient ring $\mathbb{Z}_3[x]/\langle x^3+x^2+a\rangle$ a field? (A) $0$; (B) $1$; (C) $2$; (D) $3$.

Idea Field $\iff$ irreducible (Theorem 7.43) $\iff$ no root, for a cubic (Theorem 7.41).
Check $f_a(0)=a$, $f_a(1)=a+2$, $f_a(2)=8+4+a\equiv a$. $a=0$: root $0$. $a=1$: $f_1(1)=3\equiv0$, root $1$. $a=2$: values $2,1,2$, no root.
Answer (B): only $a=2$, giving a field with $27$ elements.

E4. CSIR Part C Let $f(x)=x^4+1$. Which of the following statements are true? (One or more options may be correct.) (A) $f$ is irreducible over $\mathbb{Q}$. (B) $f$ has a root in $\mathbb{R}$. (C) $f$ is irreducible over $\mathbb{F}_p$ for infinitely many primes $p$. (D) $f(x+1)$ satisfies Eisenstein's criterion at $p=2$.

(A) True By (D) and Theorem 7.49.
(B) False $x^4+1\ge1$ on $\mathbb{R}$; over $\mathbb{R}$ it factors into two quadratics without real roots.
(C) False It is reducible modulo every prime (Example 5(b)).
(D) True $f(x+1)=x^4+4x^3+6x^2+4x+2$.
Answer (A) and (D).

E5. CSIR Part C Let $\Phi_n$ denote the $n$-th cyclotomic polynomial. Which of the following are true? (A) $\deg\Phi_{12}=4$. (B) $\Phi_n(1)=1$ for every $n\ge2$. (C) Every coefficient of every $\Phi_n$ lies in $\{-1,0,1\}$. (D) $\Phi_{2n}(x)=\Phi_n(-x)$ for every odd $n\ge3$.

(A) True $\deg\Phi_{12}=\varphi(12)=4$; indeed $\Phi_{12}=x^4-x^2+1$.
(B) False $\Phi_p(1)=p$, e.g. $\Phi_2(1)=2$, $\Phi_3(1)=3$; the value is $1$ only when $n$ has two or more distinct prime factors (Theorem 7.55(2)).
(C) False $\Phi_{105}$ has the coefficient $-2$ (at $x^7$ and $x^{41}$).
(D) True Theorem 7.55(3). (It fails for $n=1$: $\Phi_2(x)=x+1=-\Phi_1(-x)$.)
Answer (A) and (D).

E6. CSIR Part C Which of the following statements are true? (A) A primitive polynomial in $\mathbb{Z}[x]$ that is irreducible in $\mathbb{Q}[x]$ is irreducible in $\mathbb{Z}[x]$. (B) $2x+4$ is irreducible in $\mathbb{Z}[x]$. (C) $\mathbb{Z}[x]/\langle3,\,x^2+1\rangle$ is a field. (D) $\mathbb{Z}[x]/\langle5,\,x^2+1\rangle$ is a field.

(A) True Theorem 7.45: a factorisation in $\mathbb{Z}[x]$ into non-units would have both factors nonconstant (a constant factor would divide the content $1$).
(B) False $2x+4=2(x+2)$, and $2$ is not a unit of $\mathbb{Z}[x]$.
(C) True $\mathbb{Z}[x]/\langle3,x^2+1\rangle\cong\mathbb{F}_3[x]/\langle x^2+1\rangle$ (third isomorphism theorem), and $x^2+1$ has no root in $\mathbb{F}_3$ ($0,1,2\mapsto1,2,2$): a field with $9$ elements.
(D) False $\cong\mathbb{F}_5[x]/\langle x^2+1\rangle$ and $x^2+1=(x-2)(x+2)$ over $\mathbb{F}_5$, so $\overline{x-2}\cdot\overline{x+2}=0$: zero divisors.
Answer (A) and (C).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. $F[x]$ as a Euclidean domain. Theorems 7.36–7.39 with Example 1 on the board (do (c) over $\mathbb{Q}$ and then over $\mathbb{F}_3$ and ask why the answers differ). Example 2 as a class discussion of what fails without a domain. Close with Theorem 7.40 and the remark on $x^{p^n}-x$.
  2. Deciding irreducibility over $\mathbb{Q}$. Theorems 7.41–7.42 quickly; Theorem 7.43 linking to §7.2; Gauss's lemma (the reduction-mod-$p$ proof), Theorem 7.45, the rational root test with Example 3. Eisenstein with proof; project Interactive 1 — start with $x^4+1$ at $a=0$, let students predict a good shift, then show $x^4-10x^2+1$ (nothing works) and $x^4+8x+12$ (reducible modulo every listed prime). Example 5 and the strategy box.
  3. Finite fields and cyclotomic polynomials. Theorem 7.51 by counting; Interactive 2 for $p=2$, $n=4$ (watch the single amber cell appear) and $p=3$, $n=4$; Theorem 7.52 (state, then prove if time allows — it previews §8.2). Definition 7.19 and Theorems 7.53–7.55 with Example 7. Finish with E1, E3 and E5 done live.

Discussion questions. (1) Why does Eisenstein's criterion need $p^2\nmid a_0$, but nothing about $p^2$ for the other coefficients? (2) A polynomial is irreducible modulo $2$. Does it follow that it is irreducible modulo $3$? Over $\mathbb{Q}$? Over $\mathbb{R}$? (3) Over $\mathbb{F}_p$, about what fraction of monic polynomials of degree $n$ are irreducible? Compare with the density of primes near $p^n$.

Misconceptions to watch for. "No rational roots, so irreducible" for quartics; "Eisenstein fails, so reducible"; reading reduction mod $p$ backwards ("reducible mod $2$, so reducible over $\mathbb{Q}$"); ignoring constant factors in $\mathbb{Z}[x]$; forgetting $p\nmid a_n$; counting all irreducibles when the question says monic; believing $\Phi_n(1)=1$ always.

Suggested homework. I(1, 3, 4, 7), II(1, 2, 4, 6, 7, 9), III(1, 3, 5, 6), IV(1, 2, 4, 6); Exam corner E2, E4, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60 minutes

Research question. How likely is a "random" polynomial to be irreducible — over $\mathbb{F}_p$, and over $\mathbb{Z}$ — and when it does factor, how does it factor?

Why it matters. Irreducible polynomials over $\mathbb{F}_2$ are the working parts of modern communication: the CRC checksums in Ethernet frames and ZIP files, the Reed–Solomon codes on QR codes and deep-space probes, and the AES encryption standard all compute in $\mathbb{F}_2[x]/\langle f\rangle$ for a chosen irreducible $f$. Engineers need to know how many there are and how quickly one can be found by random search. Over $\mathbb{Z}$ the same question underlies computer-algebra factoring algorithms, which first factor modulo primes and then lift.

What to do.

  1. Using Gauss's formula, tabulate $nN_p(n)/p^n$ for $p=2,3,5$ and $n\le12$. Conjecture its limit and prove the bound $|nN_p(n)-p^n|\le 2p^{n/2}$ from the proof of Theorem 7.52 (look at the divisors $d\ge2$).
  2. Confirm the small cases with Interactive 2 and estimate how many random monic polynomials of degree $8$ over $\mathbb{F}_2$ one must try, on average, before finding an irreducible one.
  3. With a computer algebra system (Python's sympy), count the reducible monic quartics $x^4+ax^3+bx^2+cx+d$ with $|a|,|b|,|c|,|d|\le H$ for $H=1,2,3$. How many of the reducible ones have a rational root? Predict what happens as $H$ grows.
  4. Factor $x^4+8x+12$ modulo every prime $5\le p\lt 20000$ and record how often each pattern $1+3$, $2+2$, $1+1+1+1$ occurs. Compare the frequencies with $\tfrac23,\tfrac14,\tfrac1{12}$.

Tools: Python with sympy (Poly(f, x, modulus=p).factor_list(), factor_list), or any computer algebra system; a spreadsheet for the tables.

Hand in: A two-page note with your tables, the conjectured limit in step 1, your prediction in step 3, and a sentence explaining what the frequencies in step 4 might be counting.

Going further. Read about the "prime polynomial theorem" (the analogue of the prime number theorem for $\mathbb{F}_p[x]$), Hilbert's irreducibility theorem and van der Waerden's result that almost all integer polynomials are irreducible with full symmetric Galois group, and the Chebotarev density theorem, which explains step 4 through the Galois group $A_4$ (§8.3).

Instructor note: $nN_2(n)/2^n$ for $n=1,\dots,10$ is 1, 0.5, 0.75, 0.75, 0.9375, 0.8438, 0.9844, 0.9375, 0.9844, 0.9668 (e.g. $N_2(10)=99$), and $nN_3(n)/3^n$ reaches $0.9958$ at $n=10$; the limit is $1$, so about $1$ in $n$ monic polynomials of degree $n$ is irreducible ($N_2(8)=30$ of $256$, about one in $8.5$). For monic quartics with coefficients in $[-H,H]$: $H=1$: $47$ of $81$ reducible ($44$ with a rational root); $H=2$: $271$ of $625$ ($242$); $H=3$: $810$ of $2401$ ($726$). The reducible fraction ($58\%,43\%,34\%$) falls slowly towards $0$, and most reducible ones have a root (often $0$ or $\pm1$). For $x^4+8x+12$ and the $2260$ primes $5\le p\lt20000$ the observed frequencies are $0.670$ ($1+3$), $0.250$ ($2+2$) and $0.081$ (four linear factors), matching the proportions of $3$-cycles ($8$), double transpositions ($3$) and the identity ($1$) in $A_4$.

🧪 Self-check quiz

0/5 correct

Q1. Which polynomial is irreducible over $\mathbb{R}$?

Q2. How many monic irreducible quadratics are there over $\mathbb{F}_7$?

Q3. To which polynomial does Eisenstein's criterion apply directly (without a shift)?

Q4. How many roots does $x^2-x$ have in $\mathbb{Z}_6$?

Q5. $\Phi_6(x)$ equals