The math optional, made finite. Daily Practice

Euclidean domains

At a Glance

Why This Chapter Matters

This atom has appeared in 5 of the last 13 years — always a proof, usually in Section A — and the questions cluster tightly around three ideas: the division algorithm (for F[X]F[X] or Z[i]\mathbb{Z}[i]), the implication chain Euclidean \Rightarrow PID \Rightarrow UFD, and the link between irreducibility and maximality of ideals. Once you understand why the norm N(a+bi)=a2+b2N(a+bi)=a^2+b^2 is multiplicative and how rounding controls the remainder, every variant reduces to a two-page structural argument. The irreducibility-via-norm technique (2025 Q) is the same norm argument in miniature and takes under five minutes.

Minimum Theory

Euclidean domain. An integral domain RR is a Euclidean domain (ED) if there exists a function d:R{0}Z0d:R\setminus\{0\}\to\mathbb{Z}_{\ge0} (the Euclidean norm or valuation) such that for every aRa\in R and bR{0}b\in R\setminus\{0\}, there exist q,rRq,r\in R with a=qb+r,r=0 or d(r)<d(b).a = qb + r, \quad r=0 \text{ or } d(r) < d(b). The key examples are: Z\mathbb{Z} with d(n)=nd(n)=|n|; F[X]F[X] (for a field FF) with d(f)=degfd(f)=\deg f; and the Gaussian integers Z[i]\mathbb{Z}[i] with d(a+bi)=a2+b2d(a+bi)=a^2+b^2.

The implication chain. Every Euclidean domain is a PID, and every PID is a UFD: ED    PID    UFD    Integral Domain.\text{ED} \;\Rightarrow\; \text{PID} \;\Rightarrow\; \text{UFD} \;\Rightarrow\; \text{Integral Domain.} Each implication is strict. Z[X]\mathbb{Z}[X] is a UFD but not a PID (the ideal (2,X)(2,X) is not principal). The ring Z ⁣[1+192]\mathbb{Z}\!\left[\tfrac{1+\sqrt{-19}}{2}\right] is a PID but not Euclidean (Dedekind–Hasse counterexample). In a PID: irreducible \Leftrightarrow prime \Leftrightarrow the generated ideal is maximal.

Z[i]\mathbb{Z}[i] in detail. The norm N(a+bi)=a2+b2N(a+bi)=a^2+b^2 is multiplicative: N(αβ)=N(α)N(β)N(\alpha\beta)=N(\alpha)N(\beta). Units are elements of norm 1: {±1,±i}\{\pm1,\pm i\}. To divide α\alpha by β0\beta\ne0, write α/β=x+iy\alpha/\beta = x+iy in Q[i]\mathbb{Q}[i], then round each of xx and yy to the nearest integer mm and nn. Set q=m+niq=m+ni and r=αqβr=\alpha-q\beta. The rounding error on each component is at most 12\tfrac{1}{2}, so N(r)=N ⁣(αβq)N(β)(14+14)N(β)=12N(β)<N(β).N(r) = N\!\left(\tfrac{\alpha}{\beta}-q\right)\cdot N(\beta) \le \left(\tfrac{1}{4}+\tfrac{1}{4}\right)N(\beta) = \tfrac{1}{2}N(\beta) < N(\beta). This is the Euclidean property for Z[i]\mathbb{Z}[i].

Containment hierarchy: ED inside PID inside UFD inside Integral Domain

Question Archetypes

ArchetypeRecognition
euclidean-domain”Show Z[i]\mathbb{Z}[i] is a Euclidean domain / PID / UFD”
ideal-irreducible”Show (f)(f) maximal in K[X]K[X] iff ff irreducible”
division-algorithm”Prove the division algorithm in F[X]F[X]
quotient-field-irreducible”Show R/(a)R/(a) is a field for aa irreducible in a Euclidean ring”
irreducibility-via-norm”Show a specific element is irreducible in Z[i]\mathbb{Z}[i]

euclidean-domain (1 question; 2013)

Show Z[i]\mathbb{Z}[i] is a Euclidean domain, hence a PID and a UFD

Recognition Cues

The question names Z[i]\mathbb{Z}[i] (or a similar ring with a known norm) and asks you to verify one or more properties in the chain Euclidean \Rightarrow PID \Rightarrow UFD. All three may be asked together (as in 2013). The tell is that a specific norm function is either given or obviously available (sum of squares, polynomial degree).

Solution Template

  1. Define the norm. State N(a+bi)=a2+b2N(a+bi)=a^2+b^2 and note it is a non-negative integer with N(α)=0N(\alpha)=0 iff α=0\alpha=0.
  2. Establish multiplicativity (briefly): N(αβ)=N(α)N(β)N(\alpha\beta)=N(\alpha)N(\beta) — this follows from z1z22=z12z22|z_1 z_2|^2=|z_1|^2|z_2|^2.
  3. Prove division with remainder. For α,β0\alpha,\beta\ne0: write α/β=x+iyQ[i]\alpha/\beta = x+iy\in\mathbb{Q}[i], round to q=m+niq=m+ni, set r=αqβr=\alpha-q\beta. Bound N(r/β)=(xm)2+(yn)214+14=12<1N(r/\beta)=(x-m)^2+(y-n)^2\le\tfrac{1}{4}+\tfrac{1}{4}=\tfrac{1}{2}<1, so N(r)<N(β)N(r)<N(\beta). Conclude ED.
  4. PID from ED. Let II be any ideal. If I={0}I=\{0\}, then I=(0)I=(0). Otherwise pick bIb\in I with N(b)N(b) minimal; for any aIa\in I write a=qb+ra=qb+r with N(r)<N(b)N(r)<N(b) — since r=aqbIr=a-qb\in I, minimality forces r=0r=0, so a(b)a\in(b). Hence I=(b)I=(b).
  5. UFD from PID. In a PID every irreducible is prime (standard), and the ascending chain condition holds (bounded norm), so unique factorisation follows.

Worked Example

2013 Paper 2, 2013-P2-Q3a (15 marks)

State whether the Gaussian integers Z[i]\mathbb{Z}[i] form a Euclidean domain, a principal ideal domain, and a unique factorisation domain. Justify your answer in each case.

Euclidean domain. Let α,βZ[i]\alpha,\beta\in\mathbb{Z}[i], β0\beta\ne0. Compute α/β=x+iyQ[i]\alpha/\beta = x+iy\in\mathbb{Q}[i]. Choose m,nZm,n\in\mathbb{Z} with xm12|x-m|\le\tfrac{1}{2} and yn12|y-n|\le\tfrac{1}{2}. Set q=m+niq=m+ni and r=αqβr=\alpha-q\beta. Then: N(r)=N(αqβ)=N ⁣(αβq)N(β)(14+14)N(β)=N(β)2<N(β).N(r) = N(\alpha - q\beta) = N\!\left(\tfrac{\alpha}{\beta}-q\right)\cdot N(\beta) \le \left(\tfrac{1}{4}+\tfrac{1}{4}\right)N(\beta) = \tfrac{N(\beta)}{2} < N(\beta). So α=qβ+r\alpha = q\beta + r with r=0r=0 or N(r)<N(β)N(r)<N(\beta). Since N(a+bi)=a2+b20N(a+bi)=a^2+b^2\ge 0 and N(α)=0α=0N(\alpha)=0\Leftrightarrow\alpha=0, this makes Z[i]\mathbb{Z}[i] a Euclidean domain with norm NN.

PID. Let IZ[i]I\subseteq\mathbb{Z}[i] be any ideal. If I={0}I=\{0\} then I=(0)I=(0). Otherwise choose bIb\in I with N(b)N(b) minimal (possible since NN takes non-negative integer values). For any aIa\in I, apply the Euclidean property: a=qb+ra=qb+r with N(r)<N(b)N(r)<N(b). Since r=aqbIr=a-qb\in I and N(r)<N(b)N(r)<N(b), minimality forces r=0r=0, so a=qb(b)a=qb\in(b). Thus I=(b)I=(b) and Z[i]\mathbb{Z}[i] is a PID.

UFD. Every PID is a UFD by a standard theorem: in a PID every irreducible element is prime (since the ideal (p)(p) is maximal, hence prime), and the Noetherian property (which holds because ideals are generated by elements of finite norm) prevents infinite ascending chains. Unique factorisation into irreducibles then follows from the prime property plus Noetherian induction. Hence Z[i]\mathbb{Z}[i] is a UFD.

Common Traps


ideal-irreducible (1 question; 2016)

Show the principal ideal (f)(f) in K[X]K[X] is maximal if and only if ff is irreducible over the field KK

Recognition Cues

The question mentions the ideal generated by a polynomial in K[X]K[X] (where KK is a field) and asks for a maximality–irreducibility equivalence, or equivalently asks to show K[X]/(f)K[X]/(f) is a field iff ff is irreducible. The biconditional structure calls for two separate proofs (\Rightarrow and \Leftarrow).

Solution Template

  1. Setup. Note K[X]K[X] is a PID (proved by the division algorithm since KK is a field). The ideals containing (f)(f) are exactly the (g)(g) with gfg\mid f.
  2. (Irreducible \Rightarrow Maximal). Suppose ff is irreducible and (f)J=(g)K[X](f)\subseteq J=(g)\subseteq K[X] for some ideal JJ. Then gfg\mid f. Since ff is irreducible, gg is either a unit or an associate of ff. If gg is a unit, J=K[X]J=K[X]. If gfg\sim f, then J=(f)J=(f). So (f)(f) is maximal.
  3. (Maximal \Rightarrow Irreducible). Suppose (f)(f) is maximal. If f=ghf=gh with g,hg,h non-units, then (f)(g)K[X](f)\subsetneq(g)\subsetneq K[X], contradicting maximality. So ff is irreducible.
  4. Corollary (often asked): K[X]/(f)K[X]/(f) is a field \Leftrightarrow (f)(f) is maximal \Leftrightarrow ff is irreducible.

Worked Example

2016 Paper 2, 2016-P2-Q1a (10 marks)

Show that the ideal (f)(f) in K[X]K[X] is a maximal ideal if and only if ff is an irreducible polynomial over the field KK.

First note: K[X]K[X] is a PID because KK is a field and the division algorithm holds in K[X]K[X] (leading coefficient of gg is invertible in KK). In a PID every ideal is principal, so every ideal containing (f)(f) has the form (g)(g) with gfg\mid f.

(\Leftarrow) Suppose ff is irreducible. Let (f)(g)K[X](f)\subseteq (g)\subseteq K[X]. Then gfg\mid f. Since ff is irreducible, the only divisors of ff are units and associates. If gg is a unit then (g)=K[X](g)=K[X]; if gg is an associate of ff then (g)=(f)(g)=(f). Hence there is no ideal strictly between (f)(f) and K[X]K[X], so (f)(f) is maximal.

(\Rightarrow) Suppose (f)(f) is maximal. Assume for contradiction that f=ghf=gh with neither gg nor hh a unit. Then degg<degf\deg g<\deg f and degh<degf\deg h<\deg f, so fgf\mid g is false, meaning (f)(g)(f)\subsetneq (g). Also gg is a non-unit non-zero polynomial, so (g)K[X](g)\subsetneq K[X]. This gives a proper chain (f)(g)K[X](f)\subsetneq(g)\subsetneq K[X], contradicting maximality. Hence ff is irreducible.

Consequence. (f)(f) maximal K[X]/(f)\Rightarrow K[X]/(f) is a field (a standard ring-theory fact: R/IR/I is a field iff II is maximal).

Common Traps


division-algorithm (1 question; 2017)

Prove the division algorithm in F[X]F[X] for a field FF

Recognition Cues

The question asks you to prove that for f,gF[X]f,g\in F[X] with g0g\ne0, there exist unique q,rF[X]q,r\in F[X] with f=qg+rf=qg+r and degr<degg\deg r < \deg g (with the convention deg0=\deg 0 = -\infty). This is an existence-plus-uniqueness proof; the key tool is induction on degf\deg f.

Solution Template

  1. Trivial case. If degf<degg\deg f < \deg g, set q=0q=0, r=fr=f; the condition degr<degg\deg r < \deg g is satisfied.
  2. Inductive step. Let degf=ndegg=m\deg f = n \ge \deg g = m, with leading coefficients ana_n and bmb_m. Define f1=f(an/bm)Xnmgf_1 = f - (a_n/b_m)X^{n-m}g. Note bmb_m is invertible in FF (field hypothesis). Then degf1<n\deg f_1 < n (the leading terms cancel). Apply the induction hypothesis to f1f_1 and gg: f1=q1g+r1f_1 = q_1 g + r_1 with degr1<degg\deg r_1 < \deg g. Set q=q1+(an/bm)Xnmq = q_1 + (a_n/b_m)X^{n-m}, r=r1r=r_1.
  3. Uniqueness. Suppose f=qg+r=qg+rf=qg+r=q'g+r'. Then (qq)g=rr(q-q')g = r'-r. If qqq\ne q', then deg((qq)g)=deg(qq)+deggdegg\deg((q-q')g)=\deg(q-q')+\deg g\ge\deg g, but deg(rr)<degg\deg(r'-r)<\deg g — contradiction. So q=qq=q' and r=rr=r'.

Worked Example

2017 Paper 2, 2017-P2-Q2c (20 marks)

Let FF be a field and f(X),g(X)F[X]f(X),\,g(X)\in F[X] with g(X)0g(X)\ne0. Prove that there exist unique polynomials q(X)q(X) and r(X)r(X) in F[X]F[X] such that f(X)=q(X)g(X)+r(X)f(X)=q(X)g(X)+r(X) and either r(X)=0r(X)=0 or degr(X)<degg(X)\deg r(X)<\deg g(X).

Existence (by induction on n=degfn=\deg f).

Base. If f=0f=0 or degf<degg=m\deg f < \deg g = m, take q=0q=0, r=fr=f. Then f=0g+ff=0\cdot g+f and degr<degg\deg r<\deg g. \checkmark

Step. Suppose existence holds for all polynomials of degree <n< n, and let degf=nm\deg f=n\ge m. Write f=anXn+f=a_n X^n+\cdots and g=bmXm+g=b_m X^m+\cdots. Since FF is a field, bmb_m has an inverse bm1Fb_m^{-1}\in F. Define f1=fanbm1Xnmg.f_1 = f - a_n b_m^{-1} X^{n-m} g. The coefficient of XnX^n in f1f_1 is ananbm1bm=0a_n - a_n b_m^{-1}\cdot b_m = 0, so degf1n1<n\deg f_1 \le n-1 < n. By the induction hypothesis, f1=q1g+r1f_1 = q_1 g + r_1 with r1=0r_1=0 or degr1<m\deg r_1 < m. Then f=anbm1Xnmg+f1=(anbm1Xnm+q1)qg+r1.f = a_n b_m^{-1} X^{n-m} g + f_1 = \underbrace{\bigl(a_n b_m^{-1} X^{n-m} + q_1\bigr)}_{q} g + r_1. Setting r=r1r=r_1 gives f=qg+rf=qg+r with degr<degg\deg r < \deg g. \checkmark

Uniqueness. Suppose f=qg+r=qg+rf=qg+r=q'g+r' with degr,degr<degg\deg r,\deg r'<\deg g. Then (qq)g=rr(q-q')g=r'-r. If qqq\ne q' then deg((qq)g)=deg(qq)+deggdegg\deg\bigl((q-q')g\bigr) = \deg(q-q')+\deg g \ge \deg g (using that F[X]F[X] is a domain, so degree is additive). But deg(rr)max(degr,degr)<degg\deg(r'-r)\le\max(\deg r',\deg r)<\deg g — contradiction. Hence q=qq=q' and therefore r=rr=r'. \square

Common Traps


quotient-field-irreducible (1 question; 2019)

Show R/(a)R/(a) is a field when aa is irreducible in a Euclidean ring RR

Recognition Cues

The question gives a Euclidean ring RR (or Euclidean domain), an irreducible element aRa\in R, and asks to show the quotient ring R/(a)R/(a) is a field. The Euclidean hypothesis is load-bearing: it guarantees a division algorithm and hence a gcd theory (Bézout’s identity).

Solution Template

  1. Show (a)R(a)\ne R. Since aa is irreducible, it is a non-unit, so 1(a)1\notin(a), meaning (a)R(a)\subsetneq R. Hence R/(a)R/(a) is a non-trivial ring.
  2. Show every nonzero coset is invertible. Take xˉ=x+(a)0ˉ\bar{x}=x+(a)\ne\bar{0}, so axa\nmid x. Since aa is irreducible and axa\nmid x, we have gcd(a,x)=1\gcd(a,x)=1 (an irreducible has only unit and associate divisors; xx is not a multiple of aa, so gcd=1\gcd=1).
  3. Bézout. In a Euclidean domain, gcd(a,x)=1\gcd(a,x)=1 means there exist u,vRu,v\in R with ua+vx=1ua+vx=1.
  4. Conclude. In R/(a)R/(a): uˉaˉ+vˉxˉ=1ˉ\bar{u}\cdot\bar{a}+\bar{v}\cdot\bar{x}=\bar{1}, and aˉ=0ˉ\bar{a}=\bar{0}, so vˉxˉ=1ˉ\bar{v}\cdot\bar{x}=\bar{1}. Thus xˉ\bar{x} has inverse vˉ\bar{v}. Since xˉ\bar{x} was arbitrary, R/(a)R/(a) is a field.

Worked Example

2019 Paper 2, 2019-P2-Q3d (10 marks)

Let RR be a Euclidean ring and aRa\in R an irreducible element. Prove that R/(a)R/(a) is a field.

Step 1: (a)(a) is a proper ideal. Since aa is irreducible, aa is not a unit. Hence 1(a)1\notin (a), so (a)R(a)\ne R, and R/(a)R/(a) is a non-trivial quotient ring.

Step 2: Every non-zero element of R/(a)R/(a) is a unit. Let xˉ=x+(a)0ˉ\bar{x}=x+(a)\ne\bar{0}, so axa\nmid x. Consider d=gcd(a,x)d=\gcd(a,x) in RR (which exists since RR is Euclidean, hence a PID). Since dad\mid a and aa is irreducible, dd is either a unit or an associate of aa. If dad\sim a then axa\mid x, contradicting axa\nmid x. So dd is a unit, i.e., gcd(a,x)=1\gcd(a,x)=1 (up to units).

Step 3: Bézout. Since RR is a Euclidean domain and gcd(a,x)=1\gcd(a,x)=1, the ideal (a,x)=R(a,x)=R (in a PID, (a,x)=(gcd(a,x))=(1)=R(a,x)=(\gcd(a,x))=(1)=R). Hence there exist u,vRu,v\in R with ua+vx=1.ua + vx = 1.

Step 4: Invertibility. Reduce modulo (a)(a): uˉ0ˉ+vˉxˉ=1ˉ\bar{u}\cdot\bar{0}+\bar{v}\cdot\bar{x}=\bar{1}, giving vˉxˉ=1ˉ\bar{v}\cdot\bar{x}=\bar{1}. So xˉ\bar{x} has multiplicative inverse vˉ\bar{v} in R/(a)R/(a).

Since every nonzero element of R/(a)R/(a) is invertible, R/(a)R/(a) is a field. \square

Common Traps


irreducibility-via-norm (1 question; 2025)

Show that a specific element is irreducible in Z[i]\mathbb{Z}[i] using the norm

Recognition Cues

The question names an element αZ[i]\alpha\in\mathbb{Z}[i] (a rational integer like 33, or a Gaussian integer like 1+i1+i) and asks to show it is irreducible. The method: compute N(α)N(\alpha) and note that any factorisation α=βγ\alpha=\beta\gamma gives N(α)=N(β)N(γ)N(\alpha)=N(\beta)N(\gamma); then show the only factorisations of N(α)N(\alpha) force one factor to have norm 1 (i.e., to be a unit).

Solution Template

  1. Compute N(α)N(\alpha). For αZ\alpha\in\mathbb{Z}, N(α)=α2N(\alpha)=\alpha^2.
  2. Norm factorisation. If α=βγ\alpha=\beta\gamma then N(α)=N(β)N(γ)N(\alpha)=N(\beta)N(\gamma); list all ways to write N(α)N(\alpha) as a product of two positive integers.
  3. Eliminate non-trivial splits. For each split {d1,d2}\{d_1,d_2\} of N(α)N(\alpha): if d1=1d_1=1 or d2=1d_2=1, one factor is a unit — this is the irreducible conclusion. Otherwise, show no Gaussian integer of that norm exists (sum of two squares argument) or arrive at a contradiction.
  4. Conclude. Since every factorisation forces one factor to be a unit, α\alpha is irreducible in Z[i]\mathbb{Z}[i].

Worked Example

2025 Paper 2, 2025-P2-Q2b (15 marks)

Show that 33 is an irreducible element in the integral domain Z[i]\mathbb{Z}[i].

Setup. In Z[i]\mathbb{Z}[i], the norm is N(a+bi)=a2+b2N(a+bi)=a^2+b^2, and NN is multiplicative. The units are elements of norm 1: {±1,±i}\{\pm1,\pm i\}. Suppose 3=βγ3=\beta\gamma for some β,γZ[i]\beta,\gamma\in\mathbb{Z}[i]. Then N(3)=N(β)N(γ)    9=N(β)N(γ).N(3) = N(\beta)\,N(\gamma) \implies 9 = N(\beta)\,N(\gamma).

Cases. The factorisation 9=d1d29 = d_1 d_2 with d1,d2Z>0d_1,d_2\in\mathbb{Z}_{>0} has three forms: {1,9}\{1,9\} or {3,3}\{3,3\} or {9,1}\{9,1\}.

Case {1,9}\{1,9\} or {9,1}\{9,1\}. N(β)=1N(\beta)=1 means β\beta is a unit, so 33 is irreducible in this case. \checkmark

Case {3,3}\{3,3\}. Suppose N(β)=a2+b2=3N(\beta)=a^2+b^2=3 for some a,bZa,b\in\mathbb{Z}. Check: a2+b2=3a^2+b^2=3 has no integer solution (since 33(mod4)3\equiv 3\pmod{4}, and any sum of two squares satisfies a2+b2≢3(mod4)a^2+b^2\not\equiv 3\pmod{4} — because squares are 0\equiv 0 or 1(mod4)1\pmod{4}, so sums of two squares are 0,1,\equiv 0,1, or 2(mod4)2\pmod{4}). Hence no Gaussian integer has norm 33, and this case is impossible.

Conclusion. In every factorisation 3=βγ3=\beta\gamma, one factor has norm 1 and is therefore a unit. Hence 33 is irreducible in Z[i]\mathbb{Z}[i]. \square

Remark. Alternatively: since 33(mod4)3\equiv 3\pmod{4}, the prime 33 is inert in Z[i]\mathbb{Z}[i] (by the two-squares characterisation), meaning it remains a Gaussian prime. But the norm argument above is self-contained and does not require this theorem.

Common Traps


Marks-Aware Writing

For a 10-mark proof (ideal-irreducible or quotient-field): The mark scheme rewards structure. Write the two directions (\Leftarrow and \Rightarrow) as clearly labelled separate paragraphs. Each direction needs: one sentence of setup, the key chain of reasoning (3–5 lines), and a boxed or underlined conclusion. Avoid vague phrases like “by standard theory”; write the one or two lines that constitute the argument.

For a 15-mark proof (Z[i] Euclidean, or irreducibility-via-norm): The Euclidean proof must show the rounding bound N(r)N(b)/2N(r)\le N(b)/2 explicitly — this is the only novel computation. The subsequent PID and UFD steps are brief (3–4 sentences each). For irreducibility-via-norm, the modular arithmetic argument for “no Gaussian integer of norm 3” is the key step and must be written out in full.

For a 20-mark proof (division algorithm): This is the most substantial proof; allocate roughly 8 marks to the existence induction and 4 marks to uniqueness. The inductive step must display the polynomial f1f_1 with its formula and confirm degf1<degf\deg f_1 < \deg f. The field hypothesis (invertibility of the leading coefficient) must be explicitly invoked.

General. Box every final conclusion. Number steps in inductions. If a direction is shorter (e.g., the “maximal \Rightarrow irreducible” direction in 2016), still give it its own paragraph — do not bury it in the other direction.

Practice Set

We've mapped all 13 years of this exam. Get new chapters, tools, and solutions as we release them — free.