7.2 Rings, Ideals, ED, PID, UFD and Polynomial Rings
Rings and their elements — units, zero divisors, nilpotents and idempotents — ideals and quotient rings, prime and maximal ideals, the chain ED ⇒ PID ⇒ UFD with its standard counterexamples, and polynomial rings with the irreducibility tests (Gauss, Eisenstein, reduction mod p) that GATE MA asks about.
Section 7.1 studied structures with one operation. The number systems we compute in every day have two — we add and multiply integers, residues, polynomials, matrices and functions — and a ring keeps both, tied together by the distributive law. Once two operations are present, phenomena appear that $\mathbb{Z}$ hides: nonzero elements whose product is $0$ ($2\cdot3=0$ in $\mathbb{Z}_6$), nonzero elements with a vanishing power ($6^2=0$ in $\mathbb{Z}_{36}$), and "prime numbers" that stop behaving like primes ($2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ in $\mathbb{Z}[\sqrt{-5}]$, two genuinely different factorisations of $6$). The ideas of this section — ideals and quotients, prime and maximal ideals, unique factorisation, irreducible polynomials — are the tools that sort these phenomena out, and they are exactly what is needed to build the finite fields of §7.3 as quotients $F[x]/\langle f\rangle$, the fields behind error-correcting codes and modern cryptography.
GATE MA examines rings through counts and classifications: the number of units, nilpotents or idempotents of $\mathbb{Z}_n$ or of a quotient ring; which of several ideals of $\mathbb{Z}[x]$ are prime or maximal; which rings are integral domains, PIDs or UFDs; which polynomials are irreducible over $\mathbb{Q}$ or over $\mathbb{Z}_p$; and the size and structure of rings like $\mathbb{Z}_3[x]/\langle x^2+1\rangle$. The MSQs rely on a short list of counterexamples ($\mathbb{Z}[x]$, $\mathbb{Z}[\sqrt{-5}]$, $\mathbb{Z}_4[x]$, $x^4+1$) collected in the ⚠️ box. Notation follows §7.1 and the CSIR course: ideals are written $\langle a_1,\dots,a_k\rangle$, and $N$ is the norm on quadratic rings.
Rings, Units, Zero Divisors, Domains and Fields
A ring $(R,+,\cdot)$ is a set with two operations such that $(R,+)$ is an abelian group (identity $0$), multiplication is associative, and $a(b+c)=ab+ac$, $(a+b)c=ac+bc$. It is commutative if $ab=ba$, and has an identity if some $1$ satisfies $1a=a1=a$. A subring is a subset that is a ring under the same operations (test: nonempty, closed under $a-b$ and $ab$).
Convention. From the definition of ideals on, "ring" means commutative ring with $1\ne0$ unless matrix rings or rings without identity (like $2\mathbb{Z}$) are mentioned explicitly. The standard examples: $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$, $\mathbb{Z}_n$; the quadratic rings $\mathbb{Z}[\sqrt d]=\{a+b\sqrt d:a,b\in\mathbb{Z}\}$ ($d$ squarefree), in particular the Gaussian integers $\mathbb{Z}[i]$; polynomial rings $R[x]$; products $R\times S$; the function ring $C[0,1]$; and the non-commutative $M_n(R)$.
- $a\in\mathbb{Z}_n$ is a unit iff $\gcd(a,n)=1$; every nonzero non-unit is a zero divisor. So $\mathbb{Z}_n$ has $\varphi(n)$ units and $n-\varphi(n)-1$ zero divisors, and it is an integral domain iff it is a field iff $n$ is prime.
- $a$ is nilpotent iff $\operatorname{rad}(n)\mid a$: there are $n/\operatorname{rad}(n)$ nilpotents.
- There are exactly $2^r$ idempotents: by the Chinese remainder theorem $\mathbb{Z}_n\cong\mathbb{Z}_{p_1^{a_1}}\times\cdots\times\mathbb{Z}_{p_r^{a_r}}$ as rings, and $e$ is idempotent iff each component is $0$ or $1$.
- In any finite commutative ring, every element is either a unit or a zero divisor (or $0$).
Proof. (1) If $\gcd(a,n)=1$, Bézout gives $ax+ny=1$, so $ax\equiv1$. If $d=\gcd(a,n)\gt1$ and $a\ne0$, then $a\cdot\frac nd=\frac adn\equiv0$ with $\frac nd\not\equiv0$. (2) $a^k\equiv0\pmod n$ for some $k$ iff every $p_i$ divides $a$; the multiples of $\operatorname{rad}(n)$ in $\{0,\dots,n-1\}$ number $n/\operatorname{rad}(n)$. (3) The ring isomorphism $a\mapsto(a\bmod p_i^{a_i})_i$ comes from the CRT. In $\mathbb{Z}_{p^a}$, $e^2=e$ means $p^a\mid e(e-1)$, and since $e$ and $e-1$ are coprime, $p^a$ divides one of them: $e\in\{0,1\}$. (4) If $a$ is not a zero divisor, $x\mapsto ax$ is injective on the finite ring, hence onto, so $ax=1$ for some $x$. ∎
- In an integral domain, $ab=ac$ and $a\ne0$ imply $b=c$ (cancellation). A finite integral domain is a field.
- The characteristic of an integral domain is $0$ or a prime $p$; in characteristic $p$, $(a+b)^p=a^p+b^p$.
- $\operatorname{char}(R\times S)=\operatorname{lcm}(\operatorname{char}R,\operatorname{char}S)$ (when both are positive). A product $R\times S$ of nonzero rings is never a domain: $(1,0)(0,1)=0$.
- If $a$ is nilpotent, $1+a$ is a unit; the nilpotents form an ideal (the nilradical).
Proof. (1) $a(b-c)=0$ forces $b-c=0$. For finiteness, apply Theorem 7.25(4). (2) If $\operatorname{char}R=mn$ with $1\lt m,n$, then $(m\cdot1)(n\cdot1)=0$ with both factors nonzero. In characteristic $p$, the binomial coefficients $\binom pk$, $0\lt k\lt p$, are divisible by $p$. (3) $k\cdot(1,1)=0$ iff both $\operatorname{char}$'s divide $k$. (4) If $a^k=0$, $(1+a)(1-a+a^2-\cdots\pm a^{k-1})=1\pm a^k=1$. If $a^k=0=b^l$, every term of $(a+b)^{k+l}$ contains $a^i$ with $i\ge k$ or $b^j$ with $j\ge l$; and $(ra)^k=r^ka^k=0$. ∎
Ideals, Quotient Rings and Ring Homomorphisms
- An ideal containing a unit is the whole ring. A commutative ring with $1$ is a field iff its only ideals are $\{0\}$ and $R$.
- The ideals of $\mathbb{Z}$ are the $n\mathbb{Z}$, $n\ge0$; the ideals of $\mathbb{Z}_n$ are the $\langle d\rangle$ for $d\mid n$ (so there are $\tau(n)$ of them), with $\mathbb{Z}_n/\langle d\rangle\cong\mathbb{Z}_d$.
- The ideals of $R\times S$ are exactly the products $I\times J$ of ideals.
- Sums $I+J$, intersections $I\cap J$ and products $IJ$ of ideals are ideals; in $\mathbb{Z}$, $\langle m\rangle+\langle n\rangle=\langle\gcd(m,n)\rangle$ and $\langle m\rangle\cap\langle n\rangle=\langle\operatorname{lcm}(m,n)\rangle$.
Proof. (1) If $u\in I$ is a unit, $r=(ru^{-1})u\in I$ for every $r$. If $R$ is a field, a nonzero ideal contains a unit. Conversely, if the only ideals are $0$ and $R$, then for $a\ne0$, $\langle a\rangle=R\ni1$, so $a$ is a unit. (2) An ideal of $\mathbb{Z}$ is a subgroup, hence $n\mathbb{Z}$, and these are ideals. Ideals of $\mathbb{Z}_n$ are subgroups of the cyclic group $\mathbb{Z}_n$ — one for each divisor (Theorem 7.3) — and each subgroup $\langle d\rangle$ is an ideal. (3) If $K$ is an ideal of $R\times S$ and $(a,b)\in K$, then $(a,0)=(1,0)(a,b)\in K$ and $(0,b)\in K$; so $K=I\times J$ with $I,J$ the projections. (4) Direct checks; in $\mathbb{Z}$ both sides of each identity are subgroups with the same generator. ∎
- If $\phi:R\to S$ is a ring homomorphism, $R/\ker\phi\cong\phi(R)$.
- (Correspondence) The ideals of $R/I$ are the $J/I$ with $J\supseteq I$ an ideal of $R$, and $(R/I)/(J/I)\cong R/J$.
- (CRT) If $I+J=R$ (coprime ideals), then $R/(I\cap J)\cong R/I\times R/J$, and $I\cap J=IJ$. In particular $\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ when $\gcd(m,n)=1$, and $F[x]/\langle fg\rangle\cong F[x]/\langle f\rangle\times F[x]/\langle g\rangle$ when $\gcd(f,g)=1$.
Proof. (1) As for groups (Theorem 7.10), $a+\ker\phi\mapsto\phi(a)$ is well defined, bijective onto the image and additive; it is multiplicative because $\phi$ is. (2) Apply (1) to $R/I\to R/J$, $a+I\mapsto a+J$. (3) The map $R\to R/I\times R/J$, $a\mapsto(a+I,a+J)$, has kernel $I\cap J$. It is onto: write $1=i+j$ with $i\in I$, $j\in J$; then $aj+bi\mapsto(a+I,\,b+J)$, because $j\equiv1\pmod I$ and $i\equiv1\pmod J$. Finally $I\cap J=(I\cap J)(i+j)\subseteq IJ\subseteq I\cap J$. ∎
- Look for a surjective homomorphism out of $R$ whose kernel is $I$ — usually evaluation ($f\mapsto f(a)$ on a polynomial ring) or reduction mod $n$ — and apply Theorem 7.28(1).
- For $F[x]/\langle f\rangle$: the elements are the remainders of degree $\lt\deg f$, so there are $|F|^{\deg f}$ of them; factor $f$ and use the CRT. It is a field iff $f$ is irreducible (Theorem 7.38), and it has nilpotents iff $f$ has a repeated factor.
- For $\mathbb{Z}[x]/\langle n,f\rangle$: first kill $n$ to get $\mathbb{Z}_n[x]/\langle\bar f\rangle$, then use step 2.
- For $\mathbb{Z}[i]/\langle\alpha\rangle$ with $\alpha\ne0$: it has $N(\alpha)$ elements; if $N(\alpha)=p$ is prime, it is $\mathbb{Z}_p$.
Prime and Maximal Ideals
Proof. $(a+I)(b+I)=0$ in $R/I$ means $ab\in I$, so "$R/I$ has no zero divisors" is exactly the definition of primeness (and $I\ne R$ iff $R/I\ne0$). By the correspondence theorem the ideals of $R/I$ are the $J/I$ with $I\subseteq J$; so $R/I$ has only the two ideals $0$ and itself iff there is nothing strictly between $I$ and $R$; by Theorem 7.27(1) this says $R/I$ is a field. Fields are domains. If $R$ is finite, $R/P$ is a finite domain, hence a field (Theorem 7.26). ∎
- $\mathbb{Z}$: the prime ideals are $\{0\}$ and $p\mathbb{Z}$; the maximal ones are the $p\mathbb{Z}$.
- $\mathbb{Z}_n$: the prime ideals and the maximal ideals are the same, namely $\langle p\rangle$ for the primes $p\mid n$: there are $\omega(n)$ of them (the number of distinct prime factors).
- $R\times S$: the prime (maximal) ideals are $P\times S$ and $R\times Q$ with $P$, $Q$ prime (maximal).
- $F[x]$, $F$ a field: every ideal is $\langle f\rangle$; for $f\ne0$, $\langle f\rangle$ is prime $\iff$ maximal $\iff$ $f$ is irreducible.
- $\mathbb{Z}[x]$: $\langle x\rangle$ and $\langle p\rangle$ are prime but not maximal ($\mathbb{Z}[x]/\langle x\rangle\cong\mathbb{Z}$, $\mathbb{Z}[x]/\langle p\rangle\cong\mathbb{Z}_p[x]$); $\langle p,f\rangle$ is maximal when $p$ is prime and $f$ is irreducible mod $p$ — and every maximal ideal has this form.
- $C[0,1]$: the maximal ideals are exactly $M_c=\{f:f(c)=0\}$, $c\in[0,1]$, with $C[0,1]/M_c\cong\mathbb{R}$.
Proof (of 1–5; 6 and the last clause of 5 are in the 📚 box). (1), (2) $\mathbb{Z}/n\mathbb{Z}=\mathbb{Z}_n$ is a domain iff $n=0$ or $n$ is prime, and a field iff $n$ is prime; for $\mathbb{Z}_n$ use the correspondence $\langle d\rangle\leftrightarrow d\mathbb{Z}\supseteq n\mathbb{Z}$. (3) Ideals are $I\times J$ (Theorem 7.27) and $(R\times S)/(I\times J)\cong R/I\times S/J$, a domain only if one factor is $0$. (4) $F[x]$ is a PID (Theorem 7.35); $F[x]/\langle f\rangle$ is a field iff $f$ is irreducible (Theorem 7.38), and by Theorem 7.33 nonzero prime ideals of a PID are maximal. (5) The quotients named are $\mathbb{Z}$ and $\mathbb{Z}_p[x]$, domains but not fields; $\mathbb{Z}[x]/\langle p,f\rangle\cong\mathbb{Z}_p[x]/\langle\bar f\rangle$ is a field when $\bar f$ is irreducible. ∎
| ideal $I$ | $\mathbb{Z}[x]/I$ | prime? | maximal? |
|---|---|---|---|
| $\langle x\rangle$ | $\mathbb{Z}$ | yes | no |
| $\langle2,x\rangle$ | $\mathbb{Z}_2$ | yes | yes |
| $\langle4,x\rangle$ | $\mathbb{Z}_4$ | no | no |
| $\langle x^2+1\rangle$ | $\mathbb{Z}[i]$ | yes | no |
| $\langle3,x^2+1\rangle$ | field of $9$ elements | yes | yes |
| $\langle5,x^2+1\rangle$ | $\mathbb{Z}_5\times\mathbb{Z}_5$ | no | no |
Divisibility: Euclidean Domains, PIDs and UFDs
- In an integral domain every prime element is irreducible. In a UFD (in particular in a PID) every irreducible element is prime.
- In $\mathbb{Z}[\sqrt d]$ ($d\ne1$ squarefree) the norm $N(a+b\sqrt d)=a^2-db^2$ is multiplicative. Consequently $\alpha$ is a unit iff $N(\alpha)=\pm1$, and if $N(\alpha)=\pm p$ with $p$ prime, then $\alpha$ is irreducible.
- The units of $\mathbb{Z}[i]$ are $\pm1,\pm i$; for $d\le-2$ the units of $\mathbb{Z}[\sqrt d]$ are $\pm1$; for $d\ge2$ there are infinitely many (e.g. $(1+\sqrt2)^k$).
Proof. (1) If $p$ is prime and $p=ab$, then $p\mid ab$, say $p\mid a$, $a=pc$; so $p=pcb$, and cancelling, $cb=1$: $b$ is a unit. In a UFD, let $p$ be irreducible with $p\mid ab$, $ab=pc$. Factor $a$, $b$, $c$ into irreducibles; by uniqueness $p$ is associate to an irreducible factor of $a$ or of $b$, so $p$ divides $a$ or $b$. (2) $N(\alpha)=\alpha\bar\alpha$ with $\overline{a+b\sqrt d}=a-b\sqrt d$, and conjugation is multiplicative. If $\alpha\beta=1$ then $N(\alpha)N(\beta)=1$ in $\mathbb{Z}$; conversely if $N(\alpha)=\pm1$ then $\alpha\cdot(\pm\bar\alpha)=1$. If $N(\alpha)=\pm p$ and $\alpha=\beta\gamma$, then $N(\beta)N(\gamma)=\pm p$, so one of them has norm $\pm1$ and is a unit. (3) For $d\lt0$, $a^2+|d|b^2=1$ has only the solutions listed; $N(1+\sqrt2)=-1$, and the powers of $1+\sqrt2\gt1$ are distinct. ∎
Proof. (a) Let $b\in I$ be nonzero with $\delta(b)$ least. For $a\in I$ write $a=qb+r$; then $r=a-qb\in I$, and $\delta(r)\lt\delta(b)$ is impossible, so $r=0$: $I=\langle b\rangle$. (b) Given $a$ and $b\ne0$, write $a/b=u+vi\in\mathbb{Q}(i)$ and choose integers $m,n$ with $|u-m|\le\tfrac12$, $|v-n|\le\tfrac12$. Put $q=m+ni$ and $r=a-qb\in\mathbb{Z}[i]$. Then $$N(r)=N(b)\,N\!\left(\tfrac ab-q\right)\le\tfrac12N(b)\lt N(b).$$ Geometrically: the multiples of $b$ form a square lattice of side $|b|$, and every point is within half a diagonal of a lattice point (Interactive 2). The other rings are handled similarly (📚 box). ∎
- any $a,b$ have a gcd $d$ with $\langle a,b\rangle=\langle d\rangle$, so $d=ax+by$ (Bézout);
- for $p\ne0$: $\langle p\rangle$ is maximal $\iff$ $p$ is irreducible $\iff$ $p$ is prime; every nonzero prime ideal is maximal;
- $R$ is a UFD.
Proof. (1) $\langle a,b\rangle=\langle d\rangle$ gives $d\mid a$, $d\mid b$ and $d=ax+by$, so every common divisor divides $d$. (2) Let $p$ be irreducible and $\langle p\rangle\subseteq\langle a\rangle\subseteq R$. Then $p=ab$, so $a$ is a unit ($\langle a\rangle=R$) or $b$ is a unit ($\langle a\rangle=\langle p\rangle$): $\langle p\rangle$ is maximal, hence prime, so $p$ is prime; and prime elements are irreducible (Theorem 7.31). (3) Existence: if some $a_0$ had no factorisation into irreducibles, it would be reducible, $a_0=a_1b_1$ with at least one factor, say $a_1$, without a factorisation; repeating gives a strictly increasing chain $\langle a_0\rangle\subsetneq\langle a_1\rangle\subsetneq\cdots$. Its union is an ideal, $=\langle c\rangle$, and $c$ lies in some $\langle a_k\rangle$, so the chain stops — contradiction. Uniqueness: irreducibles are prime by (2); if $p_1\cdots p_r=q_1\cdots q_s$, $p_1$ divides some $q_j$, hence is associate to it; cancel and induct. ∎
- $\mathbb{Z}$, $F[x]$, $\mathbb{Z}[i]$ are Euclidean but not fields.
- $\mathbb{Z}\big[\tfrac{1+\sqrt{-19}}2\big]$ is a PID but not Euclidean (statement only).
- $\mathbb{Z}[x]$ and $F[x,y]$ are UFDs (Theorem 7.36) but not PIDs: $\langle2,x\rangle$ and $\langle x,y\rangle$ are not principal.
- $\mathbb{Z}[\sqrt{-5}]$ and $\mathbb{Z}[\sqrt{-3}]$ are integral domains but not UFDs: $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ and $4=2\cdot2=(1+\sqrt{-3})(1-\sqrt{-3})$.
- Every PID has "nonzero prime $\Rightarrow$ maximal", so a domain with a nonzero prime ideal that is not maximal is not a PID.
Proof (of the claims GATE uses). $\langle2,x\rangle\ne\mathbb{Z}[x]$ since its elements have even constant term. If $\langle2,x\rangle=\langle f\rangle$, then $f\mid2$ forces $f=\pm1$ or $\pm2$; $\pm1$ is excluded, and $\pm2\nmid x$. Likewise $\langle x,y\rangle=\langle f\rangle$ would force $f$ to be a constant (it divides $x$ and $y$), but $\langle x,y\rangle$ contains no nonzero constant. Also $\langle x\rangle\subsetneq\langle2,x\rangle\subsetneq\mathbb{Z}[x]$ shows directly that the prime ideal $\langle x\rangle$ is not maximal. The examples in $\mathbb{Z}[\sqrt{-5}]$ are worked out in Example 4; the $\mathbb{Z}[\sqrt{-3}]$ case is Exercise III.2. ∎
Polynomial Rings and Irreducibility
- If $R$ is an integral domain, so is $R[x]$; then $\deg(fg)=\deg f+\deg g$ and $R[x]^\times=R^\times$.
- For any commutative $R$: $f=a_0+\cdots+a_nx^n$ is a unit of $R[x]$ iff $a_0$ is a unit and $a_1,\dots,a_n$ are nilpotent. (In $\mathbb{Z}_4[x]$, $(1+2x)^2=1$.)
- Division by a monic polynomial works over any commutative ring; over a field $F$, $F[x]$ is a Euclidean domain (by degree), hence a PID and a UFD. $R[x]$ is a PID if and only if $R$ is a field.
- (Factor theorem) $f(a)=0\iff(x-a)\mid f$. Over an integral domain a nonzero polynomial of degree $n$ has at most $n$ roots.
Proof. (1) The leading coefficient of $fg$ is $a_nb_m\ne0$. If $fg=1$ then $\deg f+\deg g=0$. (2) "If": $a_0+(\text{nilpotent})$ is a unit, since the nilpotents form an ideal (Theorem 7.26(4)) and $a_0^{-1}(a_0+n)=1+a_0^{-1}n$. "Only if" is in the 📚 box. (3) The usual long division needs only that the leading coefficient of the divisor is invertible. If $R[x]$ is a PID, $R\cong R[x]/\langle x\rangle$ is a domain, so $\langle x\rangle$ is a nonzero prime, hence maximal (Theorem 7.33), and $R=R[x]/\langle x\rangle$ is a field. (4) Divide $f$ by $x-a$: $f=(x-a)q+f(a)$. If $a_1,\dots,a_{n+1}$ were distinct roots, then $f=(x-a_1)q$ and, $R$ being a domain, $q(a_j)=0$ for $j\ge2$; induct on the degree. ∎
- (Gauss's lemma) The product of two primitive polynomials in $\mathbb{Z}[x]$ is primitive; $c(fg)=c(f)c(g)$.
- If $f\in\mathbb{Z}[x]$ factors in $\mathbb{Q}[x]$ into polynomials of degrees $r$ and $s$, it factors in $\mathbb{Z}[x]$ into polynomials of the same degrees. So a primitive $f\in\mathbb{Z}[x]$ is irreducible in $\mathbb{Z}[x]$ iff it is irreducible in $\mathbb{Q}[x]$.
- If $R$ is a UFD, so is $R[x]$. Hence $\mathbb{Z}[x]$, $\mathbb{Z}[x,y]$, $F[x_1,\dots,x_n]$ and $\mathbb{Z}[i][x]$ are UFDs.
- (Rational root test) If $p/q$ in lowest terms is a root of $a_nx^n+\cdots+a_0\in\mathbb{Z}[x]$, then $p\mid a_0$ and $q\mid a_n$.
Proof. (1) If a prime $p$ divided every coefficient of $fg$, then in $\mathbb{Z}_p[x]$, $\bar f\,\bar g=0$; since $\mathbb{Z}_p[x]$ is a domain, $\bar f=0$ or $\bar g=0$, i.e. $p$ divides all coefficients of $f$ or of $g$ — impossible for primitive $f,g$. Writing $f=c(f)f_0$, $g=c(g)g_0$ with $f_0,g_0$ primitive gives $c(fg)=c(f)c(g)$. (2) If $f=gh$ in $\mathbb{Q}[x]$, clear denominators: $mf=g_1h_1$ with $g_1,h_1\in\mathbb{Z}[x]$, and write $g_1=c(g_1)g_0$, $h_1=c(h_1)h_0$. By (1), $m\,c(f)=c(g_1)c(h_1)$, so $f=\pm c(f)\,g_0h_0$ in $\mathbb{Z}[x]$, with $\deg g_0=\deg g$, $\deg h_0=\deg h$. (3) The same argument over the fraction field of $R$, combined with unique factorisation in $R$ and in $\operatorname{Frac}(R)[x]$ (📚 box). (4) $a_np^n+a_{n-1}p^{n-1}q+\cdots+a_0q^n=0$; every term except the last is divisible by $p$, so $p\mid a_0q^n$, hence $p\mid a_0$; similarly $q\mid a_np^n$. ∎
Proof. By Theorem 7.36(2) it suffices to rule out $f=gh$ with $g=b_rx^r+\cdots+b_0$, $h=c_sx^s+\cdots+c_0$ in $\mathbb{Z}[x]$, $r,s\ge1$. Reduce mod $p$: $\bar f=\bar a_nx^n$, so $\bar g\,\bar h=\bar a_nx^n$ in $\mathbb{Z}_p[x]$, a UFD; hence $\bar g=\bar b_rx^r$ and $\bar h=\bar c_sx^s$ (both have degree $\ge1$ since $p\nmid a_n=b_rc_s$). Their constant terms vanish: $p\mid b_0$ and $p\mid c_0$, so $p^2\mid b_0c_0=a_0$ — contradiction. For $\Phi_p$: $\Phi_p(x+1)=\dfrac{(x+1)^p-1}{x}$, which equals
$$x^{p-1}+\tbinom p{p-1}x^{p-2}+\cdots+\tbinom p2x+p,$$and this is Eisenstein at $p$. ∎
- Over a field, a polynomial of degree $2$ or $3$ is irreducible iff it has no root. (For degree $\ge4$, "no root" is not enough.)
- Over $\mathbb{C}$ only linear polynomials are irreducible; over $\mathbb{R}$ the irreducibles are the linear ones and the quadratics with negative discriminant.
- (Reduction mod $p$) If $f\in\mathbb{Z}[x]$, $p\nmid$ the leading coefficient and $\bar f\in\mathbb{Z}_p[x]$ is irreducible, then $f$ is irreducible over $\mathbb{Q}$. The converse fails.
- $F[x]/\langle f\rangle$ is a field iff $f$ is irreducible. If $|F|=q$ and $\deg f=n$, then $|F[x]/\langle f\rangle|=q^n$.
- Over $\mathbb{Z}_p$ there are $\tfrac{p^2-p}2$ monic irreducible quadratics and $\tfrac{p^3-p}3$ monic irreducible cubics.
Proof. (1) A factorisation of a polynomial of degree $2$ or $3$ into lower-degree factors contains a linear factor, i.e. a root. (2) The fundamental theorem of algebra; a real polynomial's nonreal roots pair up as $z,\bar z$ with $(x-z)(x-\bar z)\in\mathbb{R}[x]$. (3) A factorisation $f=gh$ over $\mathbb{Z}$ (Theorem 7.36) with $\deg g,\deg h\ge1$ reduces to $\bar f=\bar g\bar h$ with the same degrees, because $p$ does not divide the leading coefficients. (4) $\langle f\rangle$ is maximal iff $f$ is irreducible, by Theorem 7.33(2) in the PID $F[x]$; then Theorem 7.29. The remainders mod $f$ are the $q^n$ polynomials of degree $\lt n$. (5) Monic quadratics: $p^2$; reducible ones $(x-a)(x-b)$: $p$ with $a=b$ and $\binom p2$ with $a\ne b$. So $p^2-p-\tfrac{p(p-1)}2=\tfrac{p^2-p}2$. Cubics: the reducible monic cubics have a root, and split as three distinct roots ($\binom p3$), a double and a simple root ($p(p-1)$), a triple root ($p$), or a root times an irreducible quadratic ($p\cdot\tfrac{p^2-p}2$); subtracting from $p^3$ leaves $\tfrac{p^3-p}3$. ∎
- Make $f$ primitive (divide by the content) — this does not change irreducibility over $\mathbb{Q}$.
- Degree $2$ or $3$: run the rational root test; no rational root means irreducible.
- Try Eisenstein at each prime dividing $a_0$; if none works, try $f(x+1)$ or $f(x-1)$.
- Try reduction mod $2$ or $3$; an irreducible reduction of the same degree settles it.
- Degree $4$ with no rational root: check for a quadratic factorisation $(x^2+ax+b)(x^2+cx+d)$ with $bd=a_0$ — this is how $x^4+4=(x^2+2x+2)(x^2-2x+2)$ is found.
- A subring need not be an ideal: $\mathbb{Z}\subset\mathbb{Q}$ is a subring but $\tfrac12\cdot1\notin\mathbb{Z}$. An ideal containing $1$ (or any unit) is the whole ring.
- Prime ideals of a ring with zero divisors still exist: $\langle2\rangle$ is a prime, even maximal, ideal of $\mathbb{Z}_6$ ($\mathbb{Z}_6/\langle2\rangle\cong\mathbb{Z}_2$), although $\mathbb{Z}_6$ is not a domain. $\{0\}$ is prime only in a domain.
- Prime does not imply maximal outside PIDs: $\langle x\rangle\subsetneq\langle2,x\rangle$ in $\mathbb{Z}[x]$; $\langle x\rangle\subsetneq\langle x,y\rangle$ in $F[x,y]$; and $\{0\}$ in $\mathbb{Z}$.
- Irreducible does not imply prime: $2$ in $\mathbb{Z}[\sqrt{-5}]$ (Example 4). UFD does not imply PID: $\mathbb{Z}[x]$, $\mathbb{Q}[x,y]$. PID does not imply ED: $\mathbb{Z}[\tfrac{1+\sqrt{-19}}2]$.
- Subrings of UFDs need not be UFDs: $\mathbb{Z}[\sqrt{-3}]$ is not a UFD, although it sits inside the Euclidean ring $\mathbb{Z}[\omega]$, $\omega=\tfrac{-1+\sqrt{-3}}2$.
- Too many roots in a non-domain: $x^2-1$ has the four roots $1,3,5,7$ in $\mathbb{Z}_8$; $x^2+1$ has infinitely many roots among the quaternions (a non-commutative ring).
- $R[x]$ can have more units than $R$, and degrees can drop when $R$ has nilpotents: $(1+2x)^2=1$ and $(2x)(2x)=0$ in $\mathbb{Z}_4[x]$.
- Irreducible over $\mathbb{Q}$ is not irreducible over $\mathbb{Z}$: $2x+2=2(x+1)$ is a product of two non-units in $\mathbb{Z}[x]$ (the content matters), though irreducible in $\mathbb{Q}[x]$.
- No root does not mean irreducible in degree $\ge4$: $x^4+4$, $(x^2+1)^2$, $(x^2+x+1)^2$ over $\mathbb{Z}_2$.
- Reduction mod $p$ and Eisenstein are one-way tests: $x^4+1$ is irreducible over $\mathbb{Q}$ but reducible mod every prime; $x^2+1$ is irreducible but Eisenstein applies only after the shift $x\mapsto x+1$.
- Products are never domains, and the characteristic of a ring can be composite: $\mathbb{R}\times\mathbb{R}$, $\operatorname{char}\mathbb{Z}_6=6$; only domains have characteristic $0$ or prime.
- CSIR Unit 2 · §7.1 Rings, Ideals and Quotient Rings — rings without identity, quadratic rings and their units, units of matrix rings, the characteristic, all isomorphism theorems for rings, quotients of the Gaussian integers, and ring homomorphisms $\mathbb{Z}_m\to\mathbb{Z}_n$.
- CSIR Unit 2 · §7.2 Prime and Maximal Ideals; ED, PID and UFD — Krull's theorem (maximal ideals exist), the maximal ideals of $C[0,1]$, norm criteria, the primes of $\mathbb{Z}[i]$ and Fermat's two-squares theorem, and the full proofs that ED $\Rightarrow$ PID $\Rightarrow$ UFD and that $R[x]$ is a UFD when $R$ is.
- CSIR Unit 2 · §7.3 Polynomial Rings and Irreducibility — units and zero divisors of $R[x]$, repeated roots and the derivative, Gauss's lemma in full, Eisenstein and reduction mod $p$, Gauss's count of irreducible polynomials over $\mathbb{F}_p$, and cyclotomic polynomials.
Two Labs
Exercises
- 1 List the units, zero divisors, nilpotent elements and idempotents of $\mathbb{Z}_{12}$.
- 2 How many units does $\mathbb{Z}_8\times\mathbb{Z}_{10}$ have? Is it isomorphic to $\mathbb{Z}_{80}$?
- 3 Find the characteristic of $\mathbb{Z}_4\times\mathbb{Z}_6\times\mathbb{Z}_{10}$.
- 4 Find the inverse of $7=1+6$ in $\mathbb{Z}_{36}$ using Theorem 7.26(4), and check it.
- 5 A ring is Boolean if $a^2=a$ for all $a$. Prove that a Boolean ring has characteristic $2$ and is commutative.
- 6 Show that $\mathbb{Z}[\sqrt2]$ has infinitely many units.
- 7 Which of the following are integral domains: $\mathbb{Z}\times\mathbb{Z}$, $\mathbb{Z}[x]$, $C[0,1]$, $\mathbb{Z}_7[x]$, $\mathbb{Z}_9$, $\mathbb{Z}_2[x]/\langle x^2\rangle$?
- 8 Find all units of $\mathbb{Z}[i]$, and show that $3$ is irreducible in $\mathbb{Z}[i]$.
- 1 How many ideals does $\mathbb{Z}_{36}$ have? How many of them are prime?
- 2 Show that $M=\{f\in C[0,1]:f(\tfrac12)=0\}$ is a maximal ideal of $C[0,1]$.
- 3 Identify $\mathbb{Z}[x]/\langle x-3\rangle$.
- 4 Identify $\mathbb{Q}[x]/\langle x^2-5x+6\rangle$.
- 5 How many ring homomorphisms $\mathbb{Z}_{12}\to\mathbb{Z}_6$ are there (not required to preserve $1$)? How many preserve $1$?
- 6 Show that $\langle2,x\rangle$ is not a principal ideal of $\mathbb{Z}[x]$.
- 7 How many ideals does $\mathbb{Z}_6\times\mathbb{Z}_{10}$ have? How many maximal ideals?
- 8 Show that $\mathbb{Z}[x]/\langle x^2+x+1\rangle$ is an integral domain, and identify it with a subring of $\mathbb{C}$.
- 1 Decide which are maximal ideals of $\mathbb{Z}[x]$: $\langle7,x\rangle$, $\langle7,x^2+1\rangle$, $\langle13,x^2+1\rangle$, $\langle x^2+1\rangle$.
- 2 Show that $\mathbb{Z}[\sqrt{-3}]$ is not a UFD.
- 3 Factor $5$, $2$ and $10$ into irreducibles in $\mathbb{Z}[i]$.
- 4 Divide $7+5i$ by $2-i$ in $\mathbb{Z}[i]$ with remainder of smaller norm.
- 5 Find $\gcd(16+7i,\ 10-5i)$ in $\mathbb{Z}[i]$.
- 6 Prove that in a PID every nonzero prime ideal is maximal, and deduce that $\mathbb{Z}[x]$ is not a PID.
- 7 Show that $1+\sqrt{-5}$ is irreducible but not prime in $\mathbb{Z}[\sqrt{-5}]$.
- 8 Show that $\langle x,y\rangle$ is a maximal, non-principal ideal of $\mathbb{Q}[x,y]$.
- 1 Show that $x^5-6x+3$ is irreducible over $\mathbb{Q}$.
- 2 Show that $x^3+2x+1$ is irreducible over $\mathbb{Z}_3$. How many elements does $\mathbb{Z}_3[x]/\langle x^3+2x+1\rangle$ have, and is it a field?
- 3 Is $x^4+x+1$ irreducible over $\mathbb{Z}_2$?
- 4 How many monic irreducible quadratics are there over $\mathbb{Z}_7$?
- 5 Is $\mathbb{Z}_5[x]/\langle x^2+2\rangle$ a field?
- 6 Show that $x^3+x+1$ is irreducible over $\mathbb{Q}$ by reducing mod $2$, and also by the rational root test.
- 7 Give a polynomial of degree $4$ over $\mathbb{Q}$ with no rational root that is reducible, and one that is irreducible but not Eisenstein at any prime.
- 8 Prove that $x^2-2$ is irreducible over $\mathbb{Q}$ but reducible over $\mathbb{Z}_7$, and explain why this does not contradict Theorem 7.38(3).
- 9 (Modelling) A checksum scheme works in the ring $\mathbb{Z}_2[x]/\langle x^3+x+1\rangle$. How many elements does it have, is every nonzero element invertible, and what is the inverse of $\bar x$?
E1. GATE MA · MCQ Which of the following ideals of $\mathbb{Z}[x]$ is maximal? (A) $\langle x\rangle$; (B) $\langle x^2+1\rangle$; (C) $\langle3,x^2+1\rangle$; (D) $\langle5,x^2+1\rangle$.
E2. GATE MA · MCQ The number of nilpotent elements in the ring $\mathbb{Z}_{360}$ is (A) $6$; (B) $12$; (C) $30$; (D) $96$.
E3. GATE MA · MSQ CSIR Part C Which of the following rings is/are principal ideal domains? (One or more options may be correct.) (A) $\mathbb{Z}[x]$. (B) $\mathbb{Q}[x]$. (C) $\mathbb{Z}[i]$. (D) $\mathbb{R}[x,y]$.
E4. GATE MA · MSQ Which of the following polynomials is/are irreducible over $\mathbb{Q}$? (One or more options may be correct.) (A) $x^4+1$. (B) $x^4+4$. (C) $x^3+x+1$. (D) $x^4+2x^2+1$.
E5. GATE MA · NAT The number of units in the ring $\mathbb{Z}_2[x]/\langle x^3+1\rangle$ is ______.
E6. GATE MA · NAT The number of monic irreducible polynomials of degree $3$ over the field $\mathbb{Z}_3$ is ______.
Suggested plan — 3 lectures × 60 min.
- Rings and ideals. Definitions 7.15–7.17, Theorems 7.25–7.26 with Example 1 done as a class race on $\mathbb{Z}_{72}$; project Interactive 1 and move $n$ through $12$, $13$, $16$, $30$. Ideals and quotients (Definitions 7.18–7.20, Theorems 7.27–7.28), the strategy box and Example 2.
- Prime and maximal ideals; factorisation. Theorem 7.29 with proof, Theorem 7.30 and Example 3 (let students fill in the table). Definitions 7.22–7.25, Theorems 7.31–7.33 with proofs; Example 4 on the board. Project Interactive 2 for the Gaussian division and run Example 5.
- Polynomials. Theorem 7.35 (stress $\mathbb{Z}_4[x]$), Gauss's lemma with the mod-$p$ proof, Eisenstein with proof, Theorem 7.38 and the strategy box. Examples 6 and 7; finish with GATE corner E1, E4 and E6.
Discussion questions. (1) Why is every prime ideal of $\mathbb{Z}_n$ maximal, but not every prime ideal of $\mathbb{Z}$? (2) In Interactive 2, why does the remainder always land inside a square of side $|b|$ — and what goes wrong for $\mathbb{Z}[\sqrt{-5}]$, whose lattice of multiples is a rectangle? (3) $x^4+1$ is irreducible over $\mathbb{Q}$ but reducible modulo every prime. What does that say about proving irreducibility by reduction?
Misconceptions to watch for. "Prime ideal" taken to mean "generated by a prime number"; prime ⇒ maximal in every ring; irreducible ⇒ prime in every domain; "no root" ⇒ irreducible in degree $4$; forgetting the content when passing between $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$; assuming $R[x]^\times=R^\times$ for rings with nilpotents; treating $\mathbb{R}\times\mathbb{R}$ as a field.
Suggested homework. I(1, 2, 5, 7), II(1, 4, 5, 7), III(1, 2, 5, 7), IV(2, 3, 5, 8, 9); GATE corner E2, E3, E5.
Research question. How does a cyclic redundancy check (CRC) — the error-detecting code in Ethernet frames, USB packets, ZIP files and QR codes — use the ring $\mathbb{Z}_2[x]$, and which polynomial properties decide which transmission errors it is guaranteed to catch?
Why it matters. Every time data is sent or stored, a few bits may flip. A CRC treats the message as a polynomial $m(x)$ over $\mathbb{Z}_2$, appends the remainder of $x^km(x)$ on division by a fixed generator $g(x)$ of degree $k$, so that the transmitted word is divisible by $g$, and the receiver re-divides. An error pattern $e(x)$ goes undetected exactly when $g\mid e$ — a question about ideals of $\mathbb{Z}_2[x]$.
What to do.
- Take $g(x)=x^3+x+1$ (irreducible over $\mathbb{Z}_2$, Exercise IV.9). Encode the $4$-bit message $1101$, i.e. $m=x^3+x^2+1$: compute the remainder of $x^3m(x)$ modulo $g$ and write out the $7$-bit codeword.
- Show that every single-bit error $e=x^j$ is detected (an irreducible $g$ of degree $3$ cannot divide $x^j$) and that every two-bit error $x^i+x^j$ with $0\lt j-i\lt7$ is detected. Hint: $g$ divides $x^n-1$ first for $n=7$, because $\bar x$ has order $7$ in the field $\mathbb{Z}_2[x]/\langle g\rangle$ of $8$ elements.
- Show that if $(x+1)\mid g$, every error with an odd number of flipped bits is detected (evaluate at $x=1$). Is that true for $g=x^3+x+1$?
- Write a short program that encodes random $4$-bit messages, flips $1$, $2$ or $3$ random bits among the $7$, and records the detection rate. Compare with $g=x^3+1$, which is reducible.
Tools: pencil and paper for steps 1–3; Python (integers as bit strings, XOR for addition) for step 4.
Hand in: the codeword of step 1, the proofs of steps 2–3, a table of detection rates for the two generators, and one paragraph explaining the difference using the ideal $\langle g\rangle$ and the factorisation of $g$.
Going further. Read about the CRC-32 generator used in Ethernet (degree $32$) and why designers choose generators that are a product of $x+1$ and a primitive polynomial; and about BCH and Reed–Solomon codes, which use the finite fields of §7.3.
🧪 Self-check quiz
Q1. Which of the following rings is an integral domain?
Q2. In $\mathbb{Z}[x]$, the ideal $\langle x\rangle$ is
Q3. Which of these integral domains is not a UFD?
Q4. Eisenstein's criterion applies directly (without a substitution) to which polynomial?
Q5. The number of nilpotent elements of $\mathbb{Z}_{72}$ is