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
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).
Let $R$ be a commutative ring and $f,g\in R[x]$ nonzero.
- $\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.
- 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.)
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$.
Let $R$ be a commutative ring, $f\in R[x]$ and $c\in R$.
- Remainder theorem: the remainder of $f$ on division by $x-c$ is the constant $f(c)$.
- Factor theorem: $f(c)=0$ if and only if $(x-c)$ divides $f$ in $R[x]$.
- 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$.
- 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.
- 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$;
- 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$;
- 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$. ∎
Let $F$ be a field and $f\in F[x]$ nonconstant.
- $c\in F$ is a multiple root of $f$ iff $f(c)=f'(c)=0$.
- 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')$.
- 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.
Irreducible Polynomials over $\mathbb{C}$, $\mathbb{R}$ and in Low Degree
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$.
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$. ∎
- 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)$.
- 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. ∎
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.
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)$. ∎
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]$. ∎
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.
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.
Eisenstein's Criterion, Shifts and Reduction mod $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.
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.
- 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$.
- Consequently, if $\bar f$ is irreducible over $\mathbb{F}_p$, then $f$ is irreducible over $\mathbb{Q}$.
- 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.
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.
- 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$).
- 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.
- 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)$.
- 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$.
- 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).
- 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.
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.
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$ | 1 | 2 | 3 | 4 | 5 | 6 | general |
|---|---|---|---|---|---|---|---|
| $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$ | 2 | 1 | 2 | 3 | 6 | 9 | |
| $p=3$ | 3 | 3 | 8 | 18 | 48 | 116 |
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.
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.
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. ∎
- 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}$.
- (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]$. ∎
- $\Phi_n(0)=1$ for $n\ge2$.
- $\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.
- $\Phi_{2n}(x)=\Phi_n(-x)$ for odd $n\ge3$.
- 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$.
- (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. ∎
- 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$.
- 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$).
- 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]$).
- 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$.
- 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$.
- 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}$.
- 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$.
- 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.
- $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).
- 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.
- 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)).
- $\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
- 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 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 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 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$.
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$.
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$.
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$.
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$.
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$.
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.
Suggested plan — 3 lectures × 60 min.
- $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$.
- 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.
- 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 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.
- 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$).
- 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.
- 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. - 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).
🧪 Self-check quiz
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