Chapter 7 · Algebra

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

📘 Definition 7.15 — Ring, subring

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)$.

📘 Definition 7.16 — Units, zero divisors, nilpotents, idempotents; domains and fields
In a commutative ring $R$ with $1$: $a$ is a unit if $ab=1$ for some $b$ (the units form a group $R^\times$); $a\ne0$ is a zero divisor if $ab=0$ for some $b\ne0$; $a$ is nilpotent if $a^k=0$ for some $k\ge1$; $a$ is idempotent if $a^2=a$. $R$ is an integral domain if it has no zero divisors, and a field if every nonzero element is a unit.
📘 Definition 7.17 — Characteristic
The characteristic $\operatorname{char}R$ is the least $n\ge1$ with $n\cdot1=1+1+\cdots+1=0$, or $0$ if there is none. Then $n\cdot a=0$ for every $a\in R$.
📐 Theorem 7.25 — The anatomy of $\mathbb{Z}_n$
Let $n=p_1^{a_1}\cdots p_r^{a_r}$ and $\operatorname{rad}(n)=p_1\cdots p_r$.
  1. $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.
  2. $a$ is nilpotent iff $\operatorname{rad}(n)\mid a$: there are $n/\operatorname{rad}(n)$ nilpotents.
  3. 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$.
  4. 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$. ∎

📐 Theorem 7.26 — Domains, fields and characteristic
  1. In an integral domain, $ab=ac$ and $a\ne0$ imply $b=c$ (cancellation). A finite integral domain is a field.
  2. The characteristic of an integral domain is $0$ or a prime $p$; in characteristic $p$, $(a+b)^p=a^p+b^p$.
  3. $\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$.
  4. 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$. ∎

✏️ Example 1 — The anatomy of $\mathbb{Z}_{72}$
Count the units, the nilpotent elements, the idempotents and the zero divisors of $\mathbb{Z}_{72}$, and list the idempotents. What is the characteristic of $\mathbb{Z}_4\times\mathbb{Z}_6$, and is $\mathbb{Z}_{72}\cong\mathbb{Z}_8\times\mathbb{Z}_9$ as rings?
Units $72=2^3\cdot3^2$: $\varphi(72)=72\cdot\tfrac12\cdot\tfrac23=24$.
Nilpotents The multiples of $\operatorname{rad}(72)=6$: $72/6=12$ of them ($0,6,\dots,66$). E.g. $6^3=216=3\cdot72\equiv0$.
Idempotents $2^2=4$, one for each choice of $e\equiv0$ or $1$ mod $8$ and mod $9$: $0$, $1$; $e\equiv0\ (8)$, $e\equiv1\ (9)$ gives $e=64$; $e\equiv1\ (8)$, $e\equiv0\ (9)$ gives $e=9$. Check: $9^2=81\equiv9$ and $64^2=4096=56\cdot72+64$ ✓.
Zero divisors Every nonzero non-unit: $72-24-1=47$.
The rest $\operatorname{char}(\mathbb{Z}_4\times\mathbb{Z}_6)=\operatorname{lcm}(4,6)=12$. Yes: $\gcd(8,9)=1$ and the CRT map $a\mapsto(a\bmod8,a\bmod9)$ is a ring isomorphism.

Ideals, Quotient Rings and Ring Homomorphisms

📘 Definition 7.18 — Ideal; principal ideal
An additive subgroup $I$ of $R$ is an ideal if $ra\in I$ for all $r\in R$, $a\in I$. The ideal generated by $a_1,\dots,a_k$ is $\langle a_1,\dots,a_k\rangle=\{r_1a_1+\cdots+r_ka_k:r_i\in R\}$; an ideal $\langle a\rangle=aR$ is principal. An ideal $I\ne R$ is proper.
📘 Definition 7.19 — Quotient ring
For an ideal $I$ of $R$, the cosets $a+I$ form the quotient ring $R/I$ with $(a+I)+(b+I)=(a+b)+I$ and $(a+I)(b+I)=ab+I$. Computing in $R/I$ means computing in $R$ and "setting the generators of $I$ equal to $0$".
📘 Definition 7.20 — Ring homomorphism
A map $\phi:R\to S$ with $\phi(a+b)=\phi(a)+\phi(b)$ and $\phi(ab)=\phi(a)\phi(b)$ is a ring homomorphism; it is unital if $\phi(1)=1$. Its kernel $\ker\phi=\{a:\phi(a)=0\}$ is an ideal. (Many GATE questions do not require $\phi(1)=1$; then $\phi(1)$ is an idempotent of $S$.)
📐 Theorem 7.27 — Ideals: first facts
  1. 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$.
  2. 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$.
  3. The ideals of $R\times S$ are exactly the products $I\times J$ of ideals.
  4. 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. ∎

📐 Theorem 7.28 — Isomorphism theorems and the Chinese remainder theorem for rings
  1. If $\phi:R\to S$ is a ring homomorphism, $R/\ker\phi\cong\phi(R)$.
  2. (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$.
  3. (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$. ∎

🧭 Identifying a quotient ring $R/I$
  1. 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).
  2. 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.
  3. 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.
  4. 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$.
✏️ Example 2 — Five quotient rings
Identify (a) $\mathbb{R}[x]/\langle x^2+1\rangle$; (b) $\mathbb{R}[x]/\langle x^2-1\rangle$; (c) $\mathbb{Z}[x]/\langle x^2+1\rangle$; (d) $\mathbb{Z}[i]/\langle2+i\rangle$; (e) $\mathbb{Z}[x]/\langle3,x^2+1\rangle$. Which are fields, which are integral domains?
(a) $\cong\mathbb{C}$, a field Evaluation $f\mapsto f(i)$ maps $\mathbb{R}[x]$ onto $\mathbb{C}$ ($a+bx\mapsto a+bi$). Its kernel is an ideal $\langle g\rangle$ (Theorem 7.35: $\mathbb{R}[x]$ is a PID) containing $x^2+1$ and not containing any nonzero polynomial of degree $\le1$ ($a+bi=0$ forces $a=b=0$), so $g=x^2+1$ up to a constant.
(b) $\cong\mathbb{R}\times\mathbb{R}$, not a domain $x^2-1=(x-1)(x+1)$ with coprime factors; CRT: $f\mapsto(f(1),f(-1))$. The classes of $\tfrac{1+x}2$ and $\tfrac{1-x}2$ are idempotents with product $\tfrac{1-x^2}{4}\equiv0$.
(c) $\cong\mathbb{Z}[i]$, a domain, not a field $f\mapsto f(i)$ maps $\mathbb{Z}[x]$ onto $\mathbb{Z}[i]$; if $f(i)=0$, dividing $f$ by the monic $x^2+1$ in $\mathbb{Z}[x]$ leaves a remainder $a+bx$ with $a+bi=0$, so $f\in\langle x^2+1\rangle$. $\mathbb{Z}[i]\subset\mathbb{C}$ is a domain; $2$ has no inverse in it.
(d) $\cong\mathbb{Z}_5$, a field Modulo $2+i$ we have $i\equiv-2$, so every $a+bi\equiv a-2b$ is congruent to an integer: $\mathbb{Z}\to\mathbb{Z}[i]/\langle2+i\rangle$ is onto. Its kernel: $5=(2+i)(2-i)$ lies in it, and if $n=(2+i)\beta$ then $n^2=N(n)=5N(\beta)$, so $5\mid n$. Hence the quotient is $\mathbb{Z}/5\mathbb{Z}$.
(e) A field with $9$ elements Killing $3$ first: $\mathbb{Z}_3[x]/\langle x^2+1\rangle$. $x^2+1$ has no root in $\mathbb{Z}_3$ ($0,1,2\mapsto1,2,2$), so it is irreducible of degree $2$, and the quotient is a field with $3^2=9$ elements $a+bx$ (Theorem 7.38).

Prime and Maximal Ideals

📘 Definition 7.21 — Prime ideal, maximal ideal
A proper ideal $P$ is prime if $ab\in P$ implies $a\in P$ or $b\in P$. A proper ideal $M$ is maximal if there is no ideal strictly between $M$ and $R$.
📐 Theorem 7.29 — The quotient test
For an ideal $I$ of a commutative ring $R$ with $1$: $$I\text{ prime}\iff R/I\text{ is an integral domain},$$ $$I\text{ maximal}\iff R/I\text{ is a field}.$$ Hence every maximal ideal is prime; $\{0\}$ is prime iff $R$ is a domain; and in a finite ring every prime ideal is maximal.

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). ∎

📐 Theorem 7.30 — Prime and maximal ideals of the standard rings
  1. $\mathbb{Z}$: the prime ideals are $\{0\}$ and $p\mathbb{Z}$; the maximal ones are the $p\mathbb{Z}$.
  2. $\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).
  3. $R\times S$: the prime (maximal) ideals are $P\times S$ and $R\times Q$ with $P$, $Q$ prime (maximal).
  4. $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.
  5. $\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.
  6. $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. ∎

✏️ Example 3 — Prime or maximal in $\mathbb{Z}[x]$?
Decide which of the following ideals of $\mathbb{Z}[x]$ are prime and which are maximal: $\langle x\rangle$, $\langle2,x\rangle$, $\langle4,x\rangle$, $\langle x^2+1\rangle$, $\langle3,x^2+1\rangle$, $\langle5,x^2+1\rangle$.
Method Identify each quotient (strategy box) and apply Theorem 7.29.
Table
ideal $I$$\mathbb{Z}[x]/I$prime?maximal?
$\langle x\rangle$$\mathbb{Z}$yesno
$\langle2,x\rangle$$\mathbb{Z}_2$yesyes
$\langle4,x\rangle$$\mathbb{Z}_4$nono
$\langle x^2+1\rangle$$\mathbb{Z}[i]$yesno
$\langle3,x^2+1\rangle$field of $9$ elementsyesyes
$\langle5,x^2+1\rangle$$\mathbb{Z}_5\times\mathbb{Z}_5$nono
Details $\mathbb{Z}[x]/\langle n,x\rangle\cong\mathbb{Z}_n$ (evaluate at $0$, then reduce mod $n$). Mod $5$, $x^2+1=(x-2)(x+2)$ with $2\ne-2$, so by the CRT $\mathbb{Z}_5[x]/\langle x^2+1\rangle\cong\mathbb{Z}_5\times\mathbb{Z}_5$, which has the zero divisors $(1,0),(0,1)$: indeed $(x-2)(x+2)\in\langle5,x^2+1\rangle$ with neither factor in it. Mod $3$, $x^2+1$ has no root (Example 2(e)).
Lesson $\langle p,x^2+1\rangle$ is maximal iff $-1$ is not a square mod $p$, i.e. iff $p=3$ or $p\equiv3\pmod4$ — the same primes that stay prime in $\mathbb{Z}[i]$.

Divisibility: Euclidean Domains, PIDs and UFDs

📘 Definition 7.22 — Associates, irreducible and prime elements
In an integral domain $R$: $a\mid b$ if $b=ac$; $a,b$ are associates if $a=ub$ with $u$ a unit. A nonzero non-unit $p$ is irreducible if $p=ab$ forces $a$ or $b$ to be a unit, and prime if $p\mid ab$ forces $p\mid a$ or $p\mid b$ (equivalently $\langle p\rangle$ is a nonzero prime ideal).
📘 Definition 7.23 — Euclidean domain (ED)
An integral domain $R$ is a Euclidean domain if there is a function $\delta:R\setminus\{0\}\to\{0,1,2,\dots\}$ such that for all $a$ and all $b\ne0$ there are $q,r$ with $a=qb+r$ and $r=0$ or $\delta(r)\lt\delta(b)$. Examples: $\mathbb{Z}$ with $|\cdot|$; $F[x]$ with the degree; $\mathbb{Z}[i]$ with $N(a+bi)=a^2+b^2$.
📘 Definition 7.24 — Principal ideal domain (PID)
An integral domain in which every ideal is principal.
📘 Definition 7.25 — Unique factorisation domain (UFD)
An integral domain in which every nonzero non-unit is a product of irreducibles, and any two such factorisations $p_1\cdots p_r=q_1\cdots q_s$ have $r=s$ and, after reordering, $p_i$ associate to $q_i$.
📐 Theorem 7.31 — Prime versus irreducible; norms in $\mathbb{Z}[\sqrt d]$
  1. In an integral domain every prime element is irreducible. In a UFD (in particular in a PID) every irreducible element is prime.
  2. 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.
  3. 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. ∎

📐 Theorem 7.32 — Every Euclidean domain is a PID; $\mathbb{Z}[i]$ is Euclidean
(a) If $R$ is a Euclidean domain, every nonzero ideal $I$ is generated by any of its nonzero elements of least $\delta$. (b) $\mathbb{Z}[i]$ is a Euclidean domain with $\delta=N$; in fact the remainder can always be chosen with $N(r)\le\tfrac12N(b)$. $\mathbb{Z}[\sqrt{-2}]$, $\mathbb{Z}[\sqrt2]$, $\mathbb{Z}[\sqrt3]$ (with $|N|$) and the Eisenstein integers $\mathbb{Z}[\omega]$ are also Euclidean.

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). ∎

📐 Theorem 7.33 — Arithmetic in a PID; every PID is a UFD
Let $R$ be a PID. Then:
  1. any $a,b$ have a gcd $d$ with $\langle a,b\rangle=\langle d\rangle$, so $d=ax+by$ (Bézout);
  2. for $p\ne0$: $\langle p\rangle$ is maximal $\iff$ $p$ is irreducible $\iff$ $p$ is prime; every nonzero prime ideal is maximal;
  3. $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. ∎

📐 Theorem 7.34 — The hierarchy and its counterexamples
$$\text{fields}\subsetneq\text{ED}\subsetneq\text{PID}\subsetneq\text{UFD}\subsetneq\text{domains}.$$
  • $\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. ∎

✏️ Example 4 — $\mathbb{Z}[\sqrt{-5}]$ is not a UFD
In $R=\mathbb{Z}[\sqrt{-5}]$: (a) show that $2$, $3$, $1\pm\sqrt{-5}$ are irreducible and pairwise non-associate; (b) show that $2$ is not prime; (c) show that the ideal $\langle2,1+\sqrt{-5}\rangle$ is not principal.
Norms $N(a+b\sqrt{-5})=a^2+5b^2$: $N(2)=4$, $N(3)=9$, $N(1\pm\sqrt{-5})=6$. No element has norm $2$ or $3$: $a^2+5b^2\le3$ forces $b=0$, and $a^2\in\{2,3\}$ is impossible.
(a) A factorisation into two non-units would split the norm into two factors greater than $1$: $4=2\cdot2$, $9=3\cdot3$, $6=2\cdot3$ — each needs an element of norm $2$ or $3$. So all four are irreducible. The units are $\pm1$ (Theorem 7.31(3)), and the four elements are not $\pm$ each other (compare norms, and $1+\sqrt{-5}\ne\pm(1-\sqrt{-5})$). So $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ are two essentially different factorisations into irreducibles.
(b) $2\mid6=(1+\sqrt{-5})(1-\sqrt{-5})$, but $2\nmid1\pm\sqrt{-5}$ because $\tfrac{1\pm\sqrt{-5}}2\notin R$. An irreducible that is not prime — impossible in a UFD (Theorem 7.31(1)).
(c) Every element of $I=\langle2,1+\sqrt{-5}\rangle$ has the form $a+b\sqrt{-5}$ with $a\equiv b\pmod2$: indeed $2(c+d\sqrt{-5})=2c+2d\sqrt{-5}$ and $(1+\sqrt{-5})(c+d\sqrt{-5})$ $=(c-5d)+(c+d)\sqrt{-5}$, with $(c-5d)-(c+d)=-6d$ even. So $1\notin I$ and $I$ is proper. If $I=\langle\alpha\rangle$, then $N(\alpha)$ divides $N(2)=4$ and $N(1+\sqrt{-5})=6$, so $N(\alpha)\in\{1,2\}$; $2$ is impossible, and $N(\alpha)=1$ makes $\alpha$ a unit and $I=R$. Contradiction.
✏️ Example 5 — The Euclidean algorithm in $\mathbb{Z}[i]$
Find $\gcd(17+19i,\ 8+i)$ in $\mathbb{Z}[i]$ and check it with norms.
Step 1 Multiply by the conjugate: $$\frac{17+19i}{8+i}=\frac{(17+19i)(8-i)}{65}=\frac{155+135i}{65},$$ which is about $2.38+2.08i$. Round: $q=2+2i$. Then $(2+2i)(8+i)=14+18i$ and $r=3+i$, with $N(r)=10\lt N(8+i)=65$.
Step 2 $\dfrac{8+i}{3+i}=\dfrac{(8+i)(3-i)}{10}$ $=\dfrac{25-5i}{10}=2.5-0.5i$. Round to $q=2$ (any nearest point works): $r=8+i-2(3+i)=2-i$, $N(r)=5\lt10$.
Step 3 $\dfrac{3+i}{2-i}=\dfrac{(3+i)(2+i)}{5}=\dfrac{5+5i}{5}=1+i$ exactly: $r=0$.
Answer $\gcd=2-i$, up to the units $\pm1,\pm i$ (so also $1+2i$, $-2+i$, $-1-2i$). Check: $17+19i=(2-i)(3+11i)$ and $8+i=(2-i)(3+2i)$. The cofactors are coprime: $N(3+2i)=13$ is prime, so $3+2i$ is irreducible (Theorem 7.31), and it does not divide $3+11i$, because $$\frac{3+11i}{3+2i}=\frac{31+27i}{13}\notin\mathbb{Z}[i].$$ (The norms agree: $N(17+19i)=650$ and $N(8+i)=65$ have $\gcd$ $65$, but the Gaussian gcd has norm only $5$ — the factor $13$ splits as $(3+2i)(3-2i)$, and the two numbers pick different halves.)

Polynomial Rings and Irreducibility

📘 Definition 7.26 — Polynomial ring; content; primitive polynomial
$R[x]$ is the ring of polynomials $f=a_0+a_1x+\cdots+a_nx^n$ with $a_i\in R$; if $a_n\ne0$, $\deg f=n$ and $a_n$ is the leading coefficient ($f$ is monic if $a_n=1$). For $R$ a UFD (e.g. $\mathbb{Z}$), the content $c(f)$ is a gcd of the coefficients, and $f$ is primitive if $c(f)$ is a unit. A non-constant $f\in F[x]$ is irreducible if it is not a product of two polynomials of smaller degree.
📐 Theorem 7.35 — Structure of $R[x]$
  1. If $R$ is an integral domain, so is $R[x]$; then $\deg(fg)=\deg f+\deg g$ and $R[x]^\times=R^\times$.
  2. 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$.)
  3. 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.
  4. (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. ∎

📐 Theorem 7.36 — Gauss's lemma and its consequences
  1. (Gauss's lemma) The product of two primitive polynomials in $\mathbb{Z}[x]$ is primitive; $c(fg)=c(f)c(g)$.
  2. 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]$.
  3. 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.
  4. (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$. ∎

📐 Theorem 7.37 — Eisenstein's criterion
Let $f=a_nx^n+\cdots+a_1x+a_0\in\mathbb{Z}[x]$ and let $p$ be a prime with $p\nmid a_n$, $p\mid a_i$ for $0\le i\lt n$, and $p^2\nmid a_0$. Then $f$ is irreducible over $\mathbb{Q}$. Since $f(x)$ is irreducible iff $f(x+c)$ is, the criterion may be applied after a shift. Consequently $x^n-p$ is irreducible for every $n$ (so $\sqrt[n]p$ has degree $n$), and the cyclotomic polynomial $\Phi_p(x)=x^{p-1}+\cdots+x+1$ is irreducible.

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$. ∎

📐 Theorem 7.38 — The irreducibility toolkit; $F[x]/\langle f\rangle$
  1. 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.)
  2. Over $\mathbb{C}$ only linear polynomials are irreducible; over $\mathbb{R}$ the irreducibles are the linear ones and the quadratics with negative discriminant.
  3. (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.
  4. $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$.
  5. 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$. ∎

🧭 Is $f$ irreducible over $\mathbb{Q}$?
  1. Make $f$ primitive (divide by the content) — this does not change irreducibility over $\mathbb{Q}$.
  2. Degree $2$ or $3$: run the rational root test; no rational root means irreducible.
  3. Try Eisenstein at each prime dividing $a_0$; if none works, try $f(x+1)$ or $f(x-1)$.
  4. Try reduction mod $2$ or $3$; an irreducible reduction of the same degree settles it.
  5. 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.
✏️ Example 6 — Six polynomials
Decide irreducibility over $\mathbb{Q}$: (a) $x^4+10x+5$; (b) $x^4+x^3+x^2+x+1$; (c) $x^3-3x-1$; (d) $x^4+4$; (e) $x^4+1$; (f) $x^4+4x^3+6x^2+4x-1$.
(a) Irreducible Eisenstein at $5$: $5\mid10$, $5\mid5$, $25\nmid5$, $5\nmid1$.
(b) Irreducible It is $\Phi_5$; $\Phi_5(x+1)=x^4+5x^3+10x^2+10x+5$ is Eisenstein at $5$.
(c) Irreducible Degree $3$; the candidates $\pm1$ give $1-3-1=-3$ and $-1+3-1=1$, not $0$.
(d) Reducible No rational root, but $x^4+4=(x^2+2)^2-(2x)^2$, so $x^4+4=(x^2+2x+2)(x^2-2x+2)$.
(e) Irreducible $(x+1)^4+1=x^4+4x^3+6x^2+4x+2$ is Eisenstein at $2$. (Yet $x^4+1$ is reducible modulo every prime: mod $2$ it is $(x+1)^4$, mod $3$ it is $(x^2+x+2)(x^2+2x+2)$ — so reduction mod $p$ could never have proved this.)
(f) Irreducible It is $(x+1)^4-2$; substituting $x\mapsto x-1$ gives $x^4-2$, Eisenstein at $2$.
✏️ Example 7 — Counting in polynomial rings and their quotients
(a) How many monic irreducible quadratics are there over $\mathbb{Z}_5$? (b) Write out the multiplication of $\mathbb{F}=\mathbb{Z}_2[x]/\langle x^2+x+1\rangle$ and show that it is a field with $4$ elements whose nonzero elements form a cyclic group. (c) Find a unit of degree $1$ in $\mathbb{Z}_4[x]$, and count the units of the form $a+bx$ in $\mathbb{Z}_9[x]$. (d) Identify $\mathbb{Z}_3[x]/\langle x^2+2\rangle$ and count its units.
(a) $\tfrac{25-5}2=10$ (Theorem 7.38(5)).
(b) $x^2+x+1$ has no root in $\mathbb{Z}_2$ ($0\mapsto1$, $1\mapsto1$), so it is irreducible and $\mathbb{F}=\{0,1,\alpha,\alpha+1\}$ is a field, $\alpha=\bar x$, with $\alpha^2=\alpha+1$. Then $\alpha(\alpha+1)=\alpha^2+\alpha=1$ and $(\alpha+1)^2=\alpha^2+1=\alpha$. So $\mathbb{F}^\times=\{1,\alpha,\alpha^2=\alpha+1\}$ is cyclic of order $3$, generated by $\alpha$.
(c) $1+2x$: $(1+2x)^2=1+4x+4x^2=1$ in $\mathbb{Z}_4[x]$. In $\mathbb{Z}_9[x]$, $a+bx$ is a unit iff $a$ is a unit ($6$ choices) and $b$ is nilpotent ($b\in\{0,3,6\}$): $6\cdot3=18$ units.
(d) Mod $3$, $x^2+2=x^2-1=(x-1)(x+1)$, with coprime factors, so by the CRT the ring is $\mathbb{Z}_3\times\mathbb{Z}_3$: $9$ elements, $2\cdot2=4$ units, and $9-4-1=4$ nonzero zero divisors.
⚠️ Counterexamples and pitfalls
  1. 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.
  2. 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.
  3. 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}$.
  4. 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]$.
  5. 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$.
  6. 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).
  7. $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]$.
  8. 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]$.
  9. 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$.
  10. 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$.
  11. 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.
📚 Go deeper — full proofs in the CSIR NET course
  • 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

Interactive 1 — The Anatomy of ℤₙ and Its Lattice of Ideals

Left: the residues $0,\dots,n-1$ round a circle — units, nilpotents, other zero divisors, and a green ring round each idempotent. Right: the ideals $\langle d\rangle$, $d\mid n$, ordered by inclusion (bigger ideals higher; $\langle1\rangle=\mathbb{Z}_n$ on top, $\langle n\rangle=0$ at the bottom). The green nodes just below the top are the maximal ideals $\langle p\rangle$ — in $\mathbb{Z}_n$ they are also exactly the prime ideals. Move the slider or press Play, and watch what happens when $n$ is prime, a prime power, or squarefree.

n—
units φ(n)—
nilpotents n/rad(n)—
idempotents · ideals · maximal—
Interactive 2 — Euclid's Algorithm in the Gaussian Integers

The multiples of $b$ — the ideal $\langle b\rangle$ — form a square lattice spanned by $b$ and $ib$. To divide $a$ (red) by $b$, take the nearest lattice point $qb$ (purple); the remainder $r=a-qb$ (green) lies in the shaded square around $qb$, so $|r|\le|b|/\sqrt2$ and $N(r)\le\tfrac12N(b)$ — inside the dashed circle of radius $|b|$. Press Play to run the algorithm $(a,b)\to(b,r)$ until the remainder is $0$; the last nonzero remainder is a gcd.

step—
a = q·b + r—
N(r) / N(b)—
gcd so far—

Exercises

I
Rings and their elements.
  • 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 Units $\{1,5,7,11\}$; zero divisors $\{2,3,4,6,8,9,10\}$; nilpotents $\{0,6\}$; idempotents $\{0,1,4,9\}$ ($4^2=16\equiv4$, $9^2=81\equiv9$).
2 $\varphi(8)\varphi(10)=4\cdot4=16$. Not isomorphic: $\mathbb{Z}_{80}$ has characteristic $80$, the product has characteristic $\operatorname{lcm}(8,10)=40$. ($\mathbb{Z}_{80}$ has $\varphi(80)=32$ units.)
3 $\operatorname{lcm}(4,6,10)=60$.
4 $6^2=36\equiv0$, so $(1+6)^{-1}=1-6=-5\equiv31$. Check: $7\cdot31=217=6\cdot36+1$ ✓.
5 $(a+a)^2=4a^2=4a$, while also $(a+a)^2=a+a=2a$; so $2a=0$ for every $a$. Then $a+b=(a+b)^2=a+ab+ba+b$ gives $ab+ba=0$, i.e. $ab=-ba=ba$.
6 $N(1+\sqrt2)=1-2=-1$, so $1+\sqrt2$ is a unit; its powers are distinct (they are real numbers $\gt1$ increasing to $\infty$) and all are units.
7 Domains: $\mathbb{Z}[x]$ and $\mathbb{Z}_7[x]$. Not: $\mathbb{Z}\times\mathbb{Z}$ ($(1,0)(0,1)=0$), $C[0,1]$ (two nonzero functions with disjoint supports), $\mathbb{Z}_9$ ($3\cdot3=0$), $\mathbb{Z}_2[x]/\langle x^2\rangle$ ($\bar x^2=0$).
8 $a^2+b^2=1$: $\pm1$, $\pm i$. If $3=\alpha\beta$ with non-units, $N(\alpha)N(\beta)=9$ forces $N(\alpha)=3$, but $a^2+b^2=3$ has no integer solution. So $3$ is irreducible (indeed prime, $\mathbb{Z}[i]$ being a PID).
II
Ideals, quotients and homomorphisms.
  • 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 $\tau(36)=9$ ideals; prime (= maximal) ones: $\langle2\rangle$, $\langle3\rangle$ — two.
2 Evaluation $f\mapsto f(\tfrac12)$ is a ring homomorphism onto $\mathbb{R}$ (constants map onto $\mathbb{R}$) with kernel $M$; $C[0,1]/M\cong\mathbb{R}$ is a field.
3 $f\mapsto f(3)$ maps onto $\mathbb{Z}$, and $f(3)=0$ iff $(x-3)\mid f$ (division by the monic $x-3$). So $\cong\mathbb{Z}$.
4 $x^2-5x+6=(x-2)(x-3)$, coprime factors; CRT: $\cong\mathbb{Q}\times\mathbb{Q}$ via $f\mapsto(f(2),f(3))$.
5 $\phi$ is determined by $e=\phi(1)$, which must satisfy $12e=0$ (automatic in $\mathbb{Z}_6$) and $e^2=e$. Idempotents of $\mathbb{Z}_6$: $0,1,3,4$. So $4$ homomorphisms, of which $1$ preserves the identity.
6 See the proof of Theorem 7.34: a generator would divide $2$ and $x$, so it would be $\pm1$ or $\pm2$; the ideal is proper, and $2\nmid x$.
7 Ideals are products: $\tau(6)\tau(10)=4\cdot4=16$. Maximal: $M\times\mathbb{Z}_{10}$ ($2$ choices) or $\mathbb{Z}_6\times M$ ($2$ choices): $4$.
8 $f\mapsto f(\omega)$, $\omega=e^{2\pi i/3}$, maps $\mathbb{Z}[x]$ onto $\mathbb{Z}[\omega]\subset\mathbb{C}$, and (dividing by the monic $x^2+x+1$, whose roots $\omega,\bar\omega$ are not real) the kernel is $\langle x^2+x+1\rangle$. A subring of $\mathbb{C}$ is a domain.
III
Prime and maximal ideals; ED, PID, UFD.
  • 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 $\langle7,x\rangle$: quotient $\mathbb{Z}_7$, maximal. $\langle7,x^2+1\rangle$: $-1$ is not a square mod $7$ (squares $1,2,4$), so $x^2+1$ is irreducible mod $7$ and the quotient is a field of $49$ elements: maximal. $\langle13,x^2+1\rangle$: $5^2=25\equiv-1\pmod{13}$, so $x^2+1=(x-5)(x+5)$ mod $13$ and the quotient is $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$: not even prime. $\langle x^2+1\rangle$: quotient $\mathbb{Z}[i]$, prime but not maximal.
2 $N(a+b\sqrt{-3})=a^2+3b^2$. $4=2\cdot2=(1+\sqrt{-3})(1-\sqrt{-3})$; all three factors have norm $4$, and no element has norm $2$, so they are irreducible; the units are $\pm1$, and $2\ne\pm(1\pm\sqrt{-3})$. Two distinct factorisations.
3 $5=(2+i)(2-i)$ (norms $5$, irreducible); $2=-i(1+i)^2$; $10=-i(1+i)^2(2+i)(2-i)$.
4 $\tfrac{7+5i}{2-i}=\tfrac{(7+5i)(2+i)}5=\tfrac{9+17i}5=1.8+3.4i$, so $q=2+3i$, $qb=(2+3i)(2-i)=7+4i$, $r=i$, $N(r)=1\lt5$.
5 $\tfrac{16+7i}{10-5i}=\tfrac{(16+7i)(10+5i)}{125}=\tfrac{125+150i}{125}=1+1.2i$, $q=1+i$, $(1+i)(10-5i)=15+5i$, so $r=16+7i-(15+5i)=1+2i$. Next $\tfrac{10-5i}{1+2i}=\tfrac{(10-5i)(1-2i)}5=\tfrac{-25i}{5}=-5i$ exactly. So $\gcd=1+2i$ (norm $5$).
6 Theorem 7.33(2): if $\langle p\rangle\ne0$ is prime, $p$ is prime, hence irreducible, hence $\langle p\rangle$ is maximal. In $\mathbb{Z}[x]$, $\langle x\rangle$ is a nonzero prime ideal ($\mathbb{Z}[x]/\langle x\rangle\cong\mathbb{Z}$ is a domain) that is not maximal ($\mathbb{Z}$ is not a field).
7 $N(1+\sqrt{-5})=6$ and no element has norm $2$ or $3$, so it is irreducible. $(1+\sqrt{-5})\mid2\cdot3=6$, but it divides neither $2$ nor $3$: the norms $6\nmid4$ and $6\nmid9$.
8 $\mathbb{Q}[x,y]/\langle x,y\rangle\cong\mathbb{Q}$ (evaluate at $(0,0)$), a field. A generator $f$ would divide $x$ and $y$, forcing $f$ to be a nonzero constant, a unit — but the ideal is proper.
IV
Polynomial rings and irreducibility.
  • 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$?
1 Eisenstein at $3$: $3\mid-6$, $3\mid3$, $9\nmid3$, $3\nmid1$.
2 Values at $0,1,2$: $1$, $1+2+1=4\equiv1$, $8+4+1=13\equiv1$ — no root, degree $3$, irreducible. The quotient has $3^3=27$ elements and is a field (Theorem 7.38(4)).
3 No root ($0\mapsto1$, $1\mapsto1$). The only irreducible quadratic over $\mathbb{Z}_2$ is $x^2+x+1$, and $(x^2+x+1)^2=x^4+x^2+1\ne x^4+x+1$. So it has no factor of degree $1$ or $2$: irreducible.
4 $\tfrac{49-7}2=21$.
5 $x^2+2$ has a root iff $-2\equiv3$ is a square mod $5$; the squares are $0,1,4$. So it is irreducible and the quotient is a field with $25$ elements.
6 Mod $2$, $x^3+x+1$ has no root ($0\mapsto1$, $1\mapsto1$), so it is irreducible of the same degree: irreducible over $\mathbb{Q}$. Rational root test: $\pm1$ give $3$ and $-1$.
7 $x^4+4$ (Example 6(d)) or $(x^2+1)^2$. $x^4+1$ is irreducible (Example 6(e)) and not Eisenstein at any prime as it stands, since no prime divides the constant term $1$.
8 Over $\mathbb{Q}$, $\pm\sqrt2$ are irrational (rational root test: $\pm1,\pm2$ are not roots). Mod $7$, $3^2=9\equiv2$, so $x^2-2=(x-3)(x+3)$. Theorem 7.38(3) says only that an irreducible reduction implies irreducibility, not the converse.
9 $x^3+x+1$ has no root mod $2$, so it is irreducible and the ring is a field with $2^3=8$ elements: every nonzero element is invertible. From $\bar x^3=\bar x+1$: $\bar x(\bar x^2+1)=\bar x^3+\bar x=1$, so $\bar x^{-1}=\bar x^2+1$.
🎯 GATE corner GATE MA · MCQGATE MA · MSQGATE MA · NAT

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$.

Idea Identify the quotients (Example 3) and use Theorem 7.29.
Options (A) $\mathbb{Z}[x]/\langle x\rangle\cong\mathbb{Z}$ and (B) $\cong\mathbb{Z}[i]$ are domains but not fields. (D) $\cong\mathbb{Z}_5\times\mathbb{Z}_5$ is not even a domain, since $x^2+1=(x-2)(x+2)$ mod $5$. (C) $\cong\mathbb{Z}_3[x]/\langle x^2+1\rangle$ is a field with $9$ elements.
Answer (C).

E2. GATE MA · MCQ The number of nilpotent elements in the ring $\mathbb{Z}_{360}$ is (A) $6$; (B) $12$; (C) $30$; (D) $96$.

Idea Theorem 7.25(2): the nilpotents are the multiples of $\operatorname{rad}(360)$.
Compute $360=2^3\cdot3^2\cdot5$, $\operatorname{rad}=30$, so there are $360/30=12$ nilpotents: $0,30,60,\dots,330$.
Options (C) is the radical itself; (D) is $\varphi(360)$, the number of units; (A) is half the right count.
Answer (B).

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]$.

(A) No $\langle2,x\rangle$ is not principal; equivalently $\langle x\rangle$ is a nonzero prime that is not maximal. (It is a UFD.)
(B) Yes $F[x]$ over a field is Euclidean (Theorem 7.35(3)).
(C) Yes Euclidean with the norm (Theorem 7.32).
(D) No $\langle x,y\rangle$ is not principal (Exercise III.8). Also Theorem 7.35(3): $\mathbb{R}[x][y]$ would be a PID only if $\mathbb{R}[x]$ were a field.
Answer (B) and (C).

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$.

(A) Irreducible $(x+1)^4+1=x^4+4x^3+6x^2+4x+2$ is Eisenstein at $2$.
(B) Reducible $x^4+4=(x^2+2x+2)(x^2-2x+2)$.
(C) Irreducible Degree $3$ with no rational root ($\pm1\mapsto3,-1$).
(D) Reducible $x^4+2x^2+1=(x^2+1)^2$ — no rational root, but not irreducible.
Answer (A) and (C).

E5. GATE MA · NAT The number of units in the ring $\mathbb{Z}_2[x]/\langle x^3+1\rangle$ is ______.

Factor Over $\mathbb{Z}_2$, $x^3+1=(x+1)(x^2+x+1)$, and $x^2+x+1$ is irreducible (no root). The factors are coprime.
CRT $\mathbb{Z}_2[x]/\langle x^3+1\rangle$ is isomorphic to $\mathbb{Z}_2[x]/\langle x+1\rangle\times\mathbb{Z}_2[x]/\langle x^2+x+1\rangle$, i.e. to $\mathbb{Z}_2\times\mathbb{F}_4$.
Count Units of a product are pairs of units: $1\cdot3=3$ (they are $1,\bar x,\bar x^2$, since $\bar x^3=1$).
Answer $3$.

E6. GATE MA · NAT The number of monic irreducible polynomials of degree $3$ over the field $\mathbb{Z}_3$ is ______.

Idea A cubic is irreducible iff it has no root; count the monic cubics with a root and subtract from $3^3=27$.
Count reducible Three distinct roots: $\binom33=1$. A double and a simple root: $3\cdot2=6$. A triple root: $3$. One root times an irreducible quadratic: $3\cdot\tfrac{9-3}{2}=9$. Total $19$.
Answer $27-19=8$ $\left(=\tfrac{3^3-3}{3}\right)$.
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  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.
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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.
  2. 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.
  3. 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$?
  4. 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.

Instructor note: $x^3m=x^6+x^5+x^3\equiv1\pmod g$ (since $x^3\equiv x+1$, $x^5\equiv x^2+x+1$, $x^6\equiv x^2+1$, and the sum is $1$), so the remainder is $001$ and the codeword is $1101\,001$. Single errors: $g\nmid x^j$ as $\gcd(g,x)=1$. Two-bit errors: $x^i(x^{j-i}+1)$, and $g\mid x^n+1$ iff $7\mid n$ because $\bar x$ has order $7$ in $\mathbb{F}_8^\times$. $g(1)=1\ne0$, so $(x+1)\nmid g$: three-bit errors such as $g$ itself, i.e. $x^3+x+1$, slip through. With $g=x^3+1=(x+1)(x^2+x+1)$, the two-bit error $x^3+1$ is undetected; every odd-weight error is detected. Simulation: $x^3+x+1$ detects all $1$- and $2$-bit errors and $28$ of the $35$ three-bit patterns; $x^3+1$ misses the $5$ two-bit patterns $x^i(x^3+1)$ ($i=0,\dots,3$) and $x^6+1=(x^3+1)^2$, i.e. it detects $16$ of the $21$, but it catches every $1$- and $3$-bit error.

🧪 Self-check quiz

0/5 correct

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