Engineering / Mathematics — Fields, Series and Factorisation
Unique Factorization in Euclidean and Principal Ideal Domains
Why Euclidean domains are principal ideal domains and why principal ideal domains have unique factorisation.
Executive summary
The implications from Euclidean to principal ideal domain to unique factorisation domain are the structural backbone of everything computational in this collection.
Each step has a short proof, and together they explain why the integers and polynomial rings over a field behave identically.
Learning objectives
- Prove that Euclidean domains are principal ideal domains.
- Prove that principal ideal domains have unique factorisation.
- Identify where each implication fails to reverse.
01Euclidean implies principal
Euclidean domain
An integral domain with a size function N: R \ {0} → Z≥0 such that for all a and non-zero b there exist q, r with a = bq + r and either r = 0 or N(r) < N(b).
Euclidean implies PID
Every ideal of a Euclidean domain is principal.
Proof. For a non-zero ideal I, take b ∈ I of least size. For any a ∈ I, division gives a = bq + r with r = a − bq ∈ I. Minimality forces r = 0, so I = (b).
This is the same argument used for the integers and for polynomials over a field, stated once at the level of generality where it belongs. Both instances are corollaries.
02Principal implies unique factorisation
PID implies UFD
Every principal ideal domain is a unique factorisation domain.
Existence of factorisations
A PID is Noetherian, so no infinite strictly ascending chain of ideals exists. An element with no irreducible factorisation would generate such a chain.
Irreducibles generate maximal ideals
If r is irreducible then (r) is maximal among proper principal ideals, hence maximal.
Maximal implies prime
The quotient by a maximal ideal is a field, hence an integral domain, so the ideal is prime.
Uniqueness
Prime irreducibles give Euclid's lemma, and the usual cancellation induction completes the proof.
The chain condition is doing the work in the first step and is easy to overlook. Without it, an element could factor into ever-smaller pieces without ever reaching irreducibles, which is what happens in rings that are not Noetherian.
03Where the implications fail to reverse
| Ring | Property | Fails |
|---|---|---|
| Z[(1+√−19)/2] | PID | Not Euclidean for any size function |
| Z[X] | UFD | Not a PID — the ideal (2, X) is not principal |
| F[X, Y] | UFD | Not a PID — the ideal (X, Y) is not principal |
| Z[√−5] | Integral domain | Not a UFD |
This is the practical significance of the whole hierarchy. Unique factorisation is a structural guarantee; the Euclidean property is what makes it computable. Every gcd algorithm in this collection rests on the top row, and the algorithms transfer between the integers and polynomials precisely because both sit there.
04Frequently asked questions
Why is a PID Noetherian?
Because an ascending chain of ideals has a union that is itself an ideal, hence principal, and its generator lies in some member of the chain — which must then be the whole union, terminating the chain.
Is there a PID that is not Euclidean?
Yes, and Z[(1+√−19)/2] is the standard example. Proving no size function works requires showing the ring has no universal side divisor, which is a genuinely delicate argument.
Does the hierarchy matter for computation?
Decisively. The Euclidean property gives an algorithm; PID and UFD give existence results without one. Everything algorithmic in this collection lives in Euclidean domains, which is why the integers and F[X] receive parallel treatment.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 390-397.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.