Why it isn't obvious
Imagine a world that only has the numbers \(1, 5, 9, 13, 17, 21, \dots\), those leaving remainder 1 when divided by 4. Products of such numbers stay in the world (\(1 \times 1 \equiv 1\) mod 4), so it makes sense to talk about factoring. Call a number in this world "irreducible" if it can't be written as a product of two smaller numbers from the world. For example 9 is irreducible here, because 3 isn't in the world. So are 21 and 49.
Now look at 441:
\[ 441 = 9 \times 49 = 21 \times 21. \]Two different factorisations into irreducibles. The world is missing the numbers 3 and 7 that would explain everything: \(441 = 3 \cdot 3 \cdot 7 \cdot 7\), grouped two ways. This example, due to Hilbert, shows that unique factorisation in \(\mathbb{Z}\) is a genuine theorem that depends on the structure of the integers. Let's find out what it depends on.
Units, associates, irreducibles, primes
Work in an integral domain \(R\). Factorisations are only unique "up to units": \(6 = 2 \cdot 3 = (-2)(-3)\) shouldn't count as different. So we need some vocabulary.
Definitions
- \(a\) and \(b\) are associates if \(a = ub\) for a unit \(u\). (In \(\mathbb{Z}\): \(n\) and \(-n\).)
- A non-zero non-unit \(p\) is irreducible if whenever \(p = ab\), one of \(a, b\) is a unit. (It can't be broken up.)
- A non-zero non-unit \(p\) is prime if whenever \(p \mid ab\), then \(p \mid a\) or \(p \mid b\). (Euclid's lemma; equivalently, \((p)\) is a prime ideal.)
In \(\mathbb{Z}\) these two notions coincide, which is why school maths never separates them. In general, only one direction holds:
Theorem
In an integral domain, every prime element is irreducible.
Show proof
Let \(p\) be prime and \(p = ab\). Then \(p \mid ab\), so say \(p \mid a\): \(a = pc\). Then \(p = pcb\), and cancelling \(p\) (we're in a domain) gives \(cb = 1\). So \(b\) is a unit. ∎
A useful tool for deciding whether something is irreducible is a norm: a multiplicative measure of size. In rings like \(\mathbb{Z}[i]\) or \(\mathbb{Z}[\sqrt{-5}]\), the norm is the squared distance from 0:
If \(\alpha = \beta\gamma\), then \(N(\alpha) = N(\beta)N(\gamma)\). So norms turn questions about factoring in a strange ring into questions about factoring ordinary whole numbers.
Failure in \(\mathbb{Z}[\sqrt{-5}]\)
The ring \(\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}\) sits inside \(\mathbb{C}\), so it's a domain. Its norm is \(N(a + b\sqrt{-5}) = a^2 + 5b^2\), and its only units are \(\pm 1\) (the only solutions of \(a^2 + 5b^2 = 1\)). In this ring,
\[ 6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5}). \]Why are all four factors irreducible? Suppose \(2 = \beta\gamma\) with neither a unit. Taking norms, \(4 = N(\beta)N(\gamma)\), so \(N(\beta) = 2\). But \(a^2 + 5b^2 = 2\) has no integer solutions. The same argument works for 3 (norm 9, would need norm 3) and for \(1 \pm \sqrt{-5}\) (norm 6, would need norm 2 or 3). So all four are irreducible, and since the units are just \(\pm 1\), they aren't associates of each other.
The root of the trouble: 2 is irreducible but not prime. It divides \((1 + \sqrt{-5})(1 - \sqrt{-5}) = 6\), but it divides neither factor (\(\tfrac{1 + \sqrt{-5}}{2}\) isn't in the ring). In Hilbert's world, 9 has the same defect: it divides \(21 \times 21\) without dividing 21.
Unique factorisation domains
Definition
A domain is a unique factorisation domain (UFD) if every non-zero non-unit is a product of irreducibles, and that product is unique up to the order of the factors and replacing factors by associates.
The example above suggests what makes the difference, and it's exactly right:
Theorem
Suppose every non-zero non-unit in a domain \(R\) is a product of irreducibles. Then \(R\) is a UFD if and only if every irreducible element is prime.
Show proof of the main direction
Suppose irreducibles are prime and \(p_1 p_2 \cdots p_m = q_1 q_2 \cdots q_n\) are two factorisations. Since \(p_1\) is prime and divides the right side, it divides some \(q_j\). But \(q_j\) is irreducible, so \(q_j = u p_1\) with \(u\) a unit. Cancel \(p_1\) from both sides (absorbing \(u\) into another factor) and repeat with \(p_2\). Each \(p_i\) is matched with an associate \(q_j\), so the factorisations agree. This is exactly the proof you would give for \(\mathbb{Z}\). ∎
So the real content of the fundamental theorem of arithmetic is Euclid's lemma. And Euclid's lemma, as Unit 2 showed, comes from Bézout's identity, which comes from Euclid's algorithm, which comes from division with remainder. The next two sections follow that chain.
Principal ideal domains
Definition
A principal ideal domain (PID) is a domain in which every ideal is principal: of the form \((a)\).
In a PID, Bézout's identity holds automatically. The ideal \((a, b)\) must equal \((d)\) for some \(d\), and that \(d\) is a greatest common divisor: \(d = ax + by\) for some \(x, y\).
Theorem
Every PID is a UFD.
Show proof sketch
Irreducibles are prime. If \(p\) is irreducible and \((p) \subseteq (a)\), then \(a \mid p\), so \(a\) is a unit (giving \((a) = R\)) or an associate of \(p\) (giving \((a) = (p)\)). So \((p)\) is maximal, hence prime (Unit 7).
Factorisations exist. If some element can't be factored into irreducibles, it splits as a product of two non-units, one of which also can't be factored, and so on forever. That gives an infinite strictly increasing chain of ideals \((a_1) \subsetneq (a_2) \subsetneq \cdots\). Their union is an ideal, so it's \((d)\) for some \(d\); but \(d\) lies in some \((a_k)\), and then the chain can't grow past \((a_k)\). Contradiction. ∎
The converse fails. \(\mathbb{Z}[x]\) is a UFD (Gauss proved that \(R[x]\) is a UFD whenever \(R\) is), but it's not a PID: the ideal \((2, x)\), the polynomials with even constant term, isn't principal. If it were \((f)\), then \(f\) would divide both 2 and \(x\), forcing \(f = \pm 1\), and then \((f)\) would be everything. But \(1 \notin (2, x)\).
In \(\mathbb{Z}[\sqrt{-5}]\), the ideal \((2, 1 + \sqrt{-5})\) isn't principal either. Failure of unique factorisation and failure of principal ideals go hand in hand there.
Euclidean domains
The easiest way to prove a ring is a PID is to give it a division algorithm.
Definition
A Euclidean domain is a domain with a size function \(\nu\) (taking non-negative whole-number values on non-zero elements) such that for any \(a\) and any \(b \neq 0\) there are \(q, r\) with
\[ a = qb + r, \qquad r = 0 \text{ or } \nu(r) < \nu(b). \]| Ring | Size \(\nu\) | Division |
|---|---|---|
| \(\mathbb{Z}\) | \(|n|\) | Ordinary division with remainder. |
| \(F[x]\) | degree | Polynomial long division (Unit 4). |
| \(\mathbb{Z}[i]\) | norm \(a^2 + b^2\) | Divide in \(\mathbb{C}\) and round to the nearest lattice point (below). |
Theorem
Every Euclidean domain is a PID.
Show proof
Let \(I\) be a non-zero ideal, and choose \(b \in I\) of smallest possible size. For any \(a \in I\), divide: \(a = qb + r\). Then \(r = a - qb \in I\). If \(r \neq 0\) it would be an element of \(I\) smaller than \(b\), which is impossible. So \(r = 0\) and \(a\) is a multiple of \(b\). Hence \(I = (b)\). ∎
This one argument proves that every ideal of \(\mathbb{Z}\) and of \(F[x]\) is principal, facts we have used since Unit 6.
The Gaussian integers deserve a picture. To divide \(\alpha\) by \(\beta\), note that the multiples of \(\beta\) form a tilted square grid (the ideal \((\beta)\), as in Unit 6). Every point of the plane lies in one of its squares, so \(\alpha\) is close to some multiple \(q\beta\):
Why does this always work? \(\alpha/\beta\) is some complex number. Round each coordinate to the nearest integer to get \(q\). The rounding error is at most \(\tfrac12\) in each direction, so \(\left|\alpha/\beta - q\right|^2 \le \tfrac14 + \tfrac14 = \tfrac12 < 1\). Multiply by \(|\beta|^2\): \(N(r) = N(\alpha - q\beta) < N(\beta)\). So \(\mathbb{Z}[i]\) is Euclidean, hence a PID, hence a UFD. Unit 9 exploits this.
The same rounding argument fails for \(\mathbb{Z}[\sqrt{-5}]\): its lattice is a rectangle with sides 1 and \(\sqrt5\), and a point in the middle of a rectangle is at squared distance \(\tfrac14 + \tfrac54 = \tfrac32 > 1\) from every corner.
The ladder
Ideal numbers
In 1847 Gabriel Lamé announced a proof of Fermat's Last Theorem. He factored \(x^p + y^p\) using complex roots of unity and assumed the factorisation was unique. Ernst Kummer pointed out that unique factorisation fails in those rings (the first failure is at \(p = 23\)), and the proof collapsed.
Kummer's rescue was to invent "ideal numbers": phantom factors that restore uniqueness, just as 3 and 7 restore it in Hilbert's world. Dedekind later realised the phantoms could be made concrete as ideals, which is where the word comes from. In \(\mathbb{Z}[\sqrt{-5}]\) define
\[ P = (2, 1 + \sqrt{-5}), \qquad Q = (3, 1 + \sqrt{-5}), \qquad Q' = (3, 1 - \sqrt{-5}). \]None of these is principal, but they're prime ideals, and one can check that
\[ (2) = P^2, \quad (3) = QQ', \quad (1 + \sqrt{-5}) = PQ, \quad (1 - \sqrt{-5}) = PQ'. \]So both factorisations of 6 are the same factorisation of ideals, grouped differently:
\[ (6) = \underbrace{P^2}_{(2)} \cdot \underbrace{QQ'}_{(3)} = \underbrace{PQ}_{(1 + \sqrt{-5})} \cdot \underbrace{PQ'}_{(1 - \sqrt{-5})}. \]Going deeper: Dedekind domains and the class group
Rings like \(\mathbb{Z}[\sqrt{-5}]\), in which every non-zero ideal factors uniquely into prime ideals, are called Dedekind domains. They include the ring of integers of every number field. How far such a ring is from being a PID is measured by its class group: the non-zero ideals modulo the principal ones. For \(\mathbb{Z}[\sqrt{-5}]\) the class group has 2 elements, which is why every factorisation failure there involves exactly two "shapes" of ideal. Gauss conjectured, and Heegner, Baker and Stark proved in the 1950s and 60s, that exactly nine imaginary quadratic fields have class number 1: those of \(\sqrt{-d}\) for \(d = 1, 2, 3, 7, 11, 19, 43, 67, 163\).
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. Use the norm to find all units of \(\mathbb{Z}[i]\).
Show answer
A unit \(u\) has \(N(u)N(u^{-1}) = N(1) = 1\), so \(N(u) = a^2 + b^2 = 1\). The solutions are \(\pm 1\) and \(\pm i\), and all four are units.
2. Is 3 irreducible in \(\mathbb{Z}[i]\)? Is 5?
Show answer
3: yes. A proper factor would have norm 3, but \(a^2 + b^2 = 3\) is impossible. 5: no, \(5 = (2 + i)(2 - i)\), each of norm 5.
3. Show that \(1 + \sqrt{-5}\) is not prime in \(\mathbb{Z}[\sqrt{-5}]\).
Show answer
It divides \(2 \cdot 3 = 6\). If it divided 2, its norm 6 would divide \(N(2) = 4\); if it divided 3, 6 would divide \(N(3) = 9\). Neither holds.
4. In Hilbert's world \(\{1, 5, 9, 13, \dots\}\), find two different factorisations of 693 into irreducibles.
Show answer
\(693 = 9 \times 77 = 21 \times 33\). All four factors are \(\equiv 1 \pmod 4\), and each is irreducible in the world because its only factorisations use 3, 7 or 11, which are \(\equiv 3 \pmod 4\).
5. Divide \(11 + 3i\) by \(1 + 2i\) in \(\mathbb{Z}[i]\), with remainder.
Show answer
\(\frac{11 + 3i}{1 + 2i} = \frac{(11 + 3i)(1 - 2i)}{5} = \frac{17 - 19i}{5} = 3.4 - 3.8i\). Round: \(q = 3 - 4i\). Then \(q(1 + 2i) = 11 + 2i\), so \(r = i\), with \(N(r) = 1 < 5\).
6. Show that \(\mathbb{Q}[x, y]\) is not a PID by looking at the ideal \((x, y)\).
Show answer
If \((x, y) = (f)\), then \(f\) divides \(x\) and \(y\). The only common divisors of \(x\) and \(y\) are non-zero constants, so \(f\) would be a unit and \((f)\) everything. But every element of \((x, y)\) has constant term 0, so \(1 \notin (x, y)\).
Summary and glossary
- Unique factorisation is not automatic: it fails in Hilbert's world and in \(\mathbb{Z}[\sqrt{-5}]\), where \(6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})\).
- Prime (Euclid's lemma) implies irreducible (can't be broken up). Unique factorisation holds exactly when the converse holds too.
- Norms convert factoring questions into questions about whole numbers.
- Euclidean \(\Rightarrow\) PID \(\Rightarrow\) UFD. \(\mathbb{Z}\), \(F[x]\) and \(\mathbb{Z}[i]\) are Euclidean.
- When elements fail to factor uniquely, ideals may still do so: that was the origin of ideals.
- Associates
- Elements differing by a unit factor.
- Irreducible
- A non-unit that can't be split into two non-units.
- Prime element
- A non-unit satisfying Euclid's lemma.
- Norm
- A multiplicative size, e.g. \(N(a + bi) = a^2 + b^2\).
- UFD
- Unique factorisation domain.
- PID
- Principal ideal domain: every ideal is \((a)\).
- Euclidean domain
- A domain with division with remainder.
- Dedekind domain
- A domain where ideals factor uniquely into prime ideals.