Math 129: Algebraic Number Theory Lecture 4

William Stein

Tuesday, February 17, 2004

Note: There’s a book called Algebraic Number Theory and Fermat’s Last Theorem by Stewart and Tall, which appears to have a detailed introduction to algebraic number theory and assumes little background on the part of the reader. There is a discussion of the definition of module, and proofs of basic facts about number fields, and many exercises. If you find Swinnerton-Dyer’s book difficult, you might want to try to get your hands on Stewart and Tall, which costs about $38 new. (Hand around a copy.)

Today we will deduce, with complete proofs, the most important basic property of the ring of integers O_{K} of an algebraic number, namely that every nonzero ideals can be written uniquely as products of prime ideals. After proving this fundamental theorem, we will compute some examples using MAGMA. On Thursday the lecture will consist mostly of examples illustrating the substantial theory we will have already developed, so hang in there!

1 Dedekind Domains

Corollary 1.1. The ring of integers O_{K} of a number field is Noetherian.

Proof. As we saw before using norms, the ring O_{K} is finitely generated as a module over Z, so it is certainly finitely generated as a ring over Z. By the Hilbert Basis Theorem, O_{K} is Noetherian.

If R is an integral domain, the field of fractions of R is the field of all elements a/b, where a, b ∈ R. The field of fractions of R is the smallest field that contains R. For example, the field of fractions of Z is Q and of Z[(1 + \sqrt{5})/2] is Q(\sqrt{5}).

Definition 1.2 (Integrally Closed). An integral domain R is integrally closed in its field of fractions if whenever α is in the field of fractions of R and α satisfies a monic polynomial f ∈ R[x], then α ∈ R.

Proposition 1.3. If K is any number field, then O_{K} is integrally closed. Also, the ring \overline{Z} of all algebraic integers is integrally closed.

Proof. We first prove that \overline{Z} is integrally closed. Suppose c ∈ \overline{Q} is integral over \overline{Z}, so there is a monic polynomial f(x) = x^{n} + a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0} with a_{i} ∈ \overline{Z} and f(c) = 0. The a_{i} all lie in the ring of integers O_{K} of the number field K = Q(a_{0}, a_{1}, … a_{n−1}), and O_{K} is finitely generated as a Z-module, so Z[a_{0}, …, a_{n−1}] is finitely generated as a Z-module. Since f(c) = 0, we can write c^{n} as a Z[a_{0}, …, a_{n−1}]- linear combination of c^{i} for i < n, so the ring Z[a_{0}, …, a_{n−1}, c] is also finitely generated as a Z-module. Thus Z[c] is finitely generated as Z-module because it is a submodule of a finitely generated Z-module, which implies that c is integral over Z.

Suppose c ∈ K is integral over O_{K}. Then since \overline{Z} is integrally closed, c is an element of \overline{Z}, so c ∈ K ∩ \overline{Z} = O_{K}, as required.

Definition 1.4 (Dedekind Domain). An integral domain R is a Dedekind domain if it is Noetherian, integrally closed in its field of fractions, and every nonzero prime ideal of R is maximal.

The ring Q ⊕ Q is Noetherian, integrally closed in its field of fractions, and the two prime ideals are maximal. However, it is not a Dedekind domain because it is not an integral domain. The ring Z[\sqrt{5}] is not a Dedekind domain because it is not integrally closed in its field of fractions, as (1 + \sqrt{5})/2 is integrally over Z and lies in Q(\sqrt{5}), but not in Z[\sqrt{5}]. The ring Z is a Dedekind domain, as is any ring of integers O_{K} of a number field, as we will see below. Also, any field K is a Dedekind domain, since it is a domain, it is trivially integrally closed in itself, and there are no nonzero prime ideals so that condition that they be maximal is empty.

Proposition 1.5. The ring of integers O_{K} of a number field is a Dedekind domain.

Proof. By Proposition 1.3, the ring O_{K} is integrally closed, and by Proposition 1.1 it is Noetherian. Suppose that 𝔭 is a nonzero prime ideal of O_{K}. Let α ∈ 𝔭 be a nonzero element, and let f(x) ∈ Z[x] be the minimal polynomial of α. Then

f(α) = α^{n} + a_{n−1}α^{n−1} + ⋯ + a_{1}α + a_{0} = 0,

so a_{0} = −(α^{n} + a_{n−1}α^{n−1} + ⋯ + a_{1}α) ∈ 𝔭. Since f is irreducible, a_{0} is a nonzero element of Z that lies in 𝔭. Every element of the finitely generated abelian group O_{K}/𝔭 is killed by a_{0}, so O_{K}/𝔭 is a finite set. Since 𝔭 is prime, O_{K}/𝔭 is an integral domain. Every finite integral domain is a field, so 𝔭 is maximal, which completes the proof.

If I and J are ideals in a ring R, the product IJ is the ideal generated by all products of elements in I with elements in J:

IJ = (ab : a ∈ I, b ∈ J) ⊂ R.

Note that the set of all products ab, with a ∈ I and b ∈ J, need not be an ideal, so it is important to take the ideal generated by that set. (See the homework problems for examples.)

Definition 1.6 (Fractional Ideal). A fractional ideal is an O_{K}-submodule of I ⊂ K that is finitely generated as an O_{K}-module.

To avoid confusion, we will sometimes call a genuine ideal I ⊂ O_{K} an integral ideal. Also, since fractional ideals are finitely generated, we can clear denominators of a generating set to see that every fractional ideal is of the form aI = {ab : b ∈ I} for some a ∈ K and ideal I ⊂ O_{K}.

For example, the collection \frac{1}{2}Z of rational numbers with denominator 1 or 2 is a fractional ideal of Z.

Theorem 1.7. The set of nonzero fractional ideals of a Dedekind domain R is an abelian group under ideal multiplication.

Before proving Theorem 1.7 we prove a lemma. For the rest of this section O_{K} is the ring of integers of a number field K.

Definition 1.8 (Divides for Ideals). Suppose that I, J are ideals of O_{K}. Then I divides J if I ⊃ J.

To see that this notion of divides is sensible, suppose K = Q, so O_{K} = Z. Then I = (n) and J = (m) for some integer n and m, and I divides J means that (n) ⊃ (m), i.e., that there exists an integer c such that m = cn, which exactly means that n divides m, as expected.

Lemma 1.9. Suppose I is an ideal of O_{K}. Then there exist prime ideals 𝔭_{1}, …, 𝔭_{n} such that 𝔭_{1} · 𝔭_{2} ⋯ 𝔭_{n} ⊂ I. In other words, I divides a product of prime ideals. (By convention the empty product is the unit ideal. Also, if I = 0, then we take 𝔭_{1} = (0), which is a prime ideal.)

Proof. The key idea is to use that O_{K} is Noetherian to deduce that the set S of ideals that do not satisfy the lemma is empty. If S is nonempty, then because O_{K} is Noetherian, there is an ideal I ∈ S that is maximal as an element of S. If I were prime, then I would trivially contain a product of primes, so I is not prime. By definition of prime ideal, there exists a, b ∈ O_{K} such that ab ∈ I but a ∉ I and b ∉ I. Let J_{1} = I + (a) and J_{2} = I + (b). Then neither J_{1} nor J_{2} is in S, since I is maximal, so both J_{1} and J_{2} contain a product of prime ideals. Thus so does I, since

J_{1}J_{2} = I^{2} + I(b) + (a)I + (ab) ⊂ I,

which is a contradiction. Thus S is empty, which completes the proof.

We are now ready to prove the theorem.

Proof of Theorem 1.7. The product of two fractional ideals is again finitely generated, so it is a fractional ideal, and IO_{K} = O_{K} for any nonzero ideal I, so to prove that the set of fractional ideals under multiplication is a group it suffices to show the existence of inverses. We will first prove that if 𝔭 is a prime ideal, then 𝔭 has an inverse, then we will prove that nonzero integral ideals have inverses, and finally observe that every fractional ideal has an inverse.

Suppose 𝔭 is a nonzero prime ideal of O_{K}. We will show that the O_{K}-module

I = {a ∈ K : a𝔭 ⊂ O_{K}}

is a fractional ideal of O_{K} such that I𝔭 = O_{K}, so that I is an inverse of 𝔭.

For the rest of the proof, fix a nonzero element b ∈ 𝔭. Since I is an O_{K}-module, bI ⊂ O_{K} is an O_{K} ideal, hence I is a fractional ideal. Since O_{K} ⊂ I we have 𝔭 ⊂ I𝔭 ⊂ O_{K}, hence either 𝔭 = I𝔭 or I𝔭 = O_{K}. If I𝔭 = O_{K}, we are done since then I is an inverse of 𝔭. Thus suppose that I𝔭 = 𝔭. Our strategy is to show that there is some d ∈ I not in O_{K}; such a d would leave 𝔭 invariant (i.e., d𝔭 ⊂ 𝔭), so since 𝔭 is an O_{K}-module it will follow that d ∈ O_{K}, a contradiction.

By Lemma 1.9, we can choose a product 𝔭_{1}, …, 𝔭_{m}, with m minimal, such that

𝔭_{1}𝔭_{2} ⋯ 𝔭_{m} ⊂ (b) ⊂ 𝔭.

If no 𝔭_{i} is contained in 𝔭, then we can choose for each i an a_{i} ∈ 𝔭_{i} with a_{i} ∉ 𝔭; but then ∏ a_{i} ∈ 𝔭, which contradicts that 𝔭 is a prime ideal. Thus some 𝔭_{i}, say 𝔭_{1}, is contained in 𝔭, which implies that 𝔭_{1} = 𝔭 since every nonzero prime ideal is maximal. Because m is minimal, 𝔭_{2} ⋯ 𝔭_{m} is not a subset of (b), so there exists c ∈ 𝔭_{2} ⋯ 𝔭_{m} that does not lie in (b). Then 𝔭(c) ⊂ (b), so by definition of I we have d = c/b ∈ I. However, d ∉ O_{K}, since if it were then c would be in (b). We have thus found our element d ∈ I that does not lie in O_{K}. To finish the proof that 𝔭 has an inverse, we observe that d preserves the O_{K}-module 𝔭, and is hence in O_{K}, a contradiction. More precisely, if b_{1}, …, b_{n} is a basis for 𝔭 as a Z-module, then the action of d on 𝔭 is given by a matrix with entries in Z, so the minimal polynomial of d has coefficients in Z. This implies that d is integral over Z, so d ∈ O_{K}, since O_{K} is integrally closed by Proposition 1.3. (Note how this argument depends strongly on the fact that O_{K} is integrally closed!)

So far we have proved that if 𝔭 is a prime ideal of O_{K}, then 𝔭^{−1} = {a ∈ K : a𝔭 ⊂ O_{K}} is the inverse of 𝔭 in the monoid of nonzero fractional ideals of O_{K}. As mentioned after Definition 1.6, every nonzero fractional ideal is of the form aI for a ∈ K and I an integral ideal, so since (a) has inverse (1/a), it suffices to show that every integral ideal I has an inverse. If not, then there is a nonzero integral ideal I that is maximal among all nonzero integral ideals that do not have an inverse. Every ideal is contained in a maximal ideal, so there is a nonzero prime ideal 𝔭 such that I ⊂ 𝔭. Then I ⊂ 𝔭^{−1}I ⊂ O_{K}. If I = 𝔭^{−1}I, then (arguing as in the previous paragraph) each element of 𝔭^{−1} preserves that O_{K}-ideal I and is hence integral, so 𝔭^{−1} ⊂ O_{K}, which implies that O_{K} = 𝔭𝔭^{−1} ⊂ 𝔭, a contradiction. Thus I ≠ 𝔭^{−1}I. Because I is maximal among ideals that do not have an inverse, the ideal 𝔭^{−1}I does have an inverse, call it J. Then 𝔭J is the inverse of I, since O_{K} = (𝔭J)(𝔭^{−1}I) = JI.

We can finally deduce the crucial Theorem 1.11, which will allow us to show that any nonzero ideal of a Dedekind domain can be expressed uniquely as a product of primes (up to order). Thus unique factorization holds for ideals in a Dedekind domain, and it is this unique factorization that initially motivated the introduction of rings of integers of number fields over a century ago.

Theorem 1.10. Suppose I is an integral ideal of O_{K}. Then I can be written as a product

I = 𝔭_{1} ⋯ 𝔭_{n}

of prime ideals of O_{K}, and this representation is unique up to order. (Exception: If I = 0, then the representation is not unique.)

Proof. Suppose I is an ideal that is maximal among the set of all ideals in O_{K} that can not be written as a product of primes. Every ideal is contained in a maximal ideal, so I is contained in a nonzero prime ideal 𝔭. If I𝔭^{−1} = I, then by Theorem 1.7 we can cancel I from both sides of this equation to see that 𝔭^{−1} = O_{K}, a contradiction. Thus I is strictly contained in I𝔭^{−1}, so by our maximality assumption on I there are maximal ideals 𝔭_{1}, …, 𝔭_{n} such that I𝔭^{−1} = 𝔭_{1} ⋯ 𝔭_{n}. Then I = 𝔭 · 𝔭_{1} ⋯ 𝔭_{n}, a contradiction. Thus every ideal can be written as a product of primes.

Suppose 𝔭_{1} ⋯ 𝔭_{n} = 𝔮_{1} ⋯ 𝔮_{m}. If no 𝔮_{i} is contained in 𝔭_{1}, then for each i there is an a_{i} ∈ 𝔮_{i} such that a_{i} ∉ 𝔭_{1}. But the product of the a_{i} is in the 𝔭_{1} ⋯ 𝔭_{n}, which is a subset of 𝔭_{1}, which contradicts the fact that 𝔭_{1} is a prime ideal. Thus 𝔮_{i} = 𝔭_{1} for some i. We can thus cancel 𝔮_{i} and 𝔭_{1} from both sides of the equation. Repeating this argument finishes the proof of uniqueness.

Corollary 1.11. If I is a fractional ideal of O_{K} then there exists prime ideals 𝔭_{1}, …, 𝔭_{n} and 𝔮_{1}, …, 𝔮_{m}, unique up to order, such that

I = (𝔭_{1} ⋯ 𝔭_{n})(𝔮_{1} ⋯ 𝔮_{m})^{−1}.

Proof. We have I = (a/b)J for some a, b ∈ O_{K} and integral ideal J. Applying Theorem 1.11 to (a), (b), and J gives an expression as claimed. For uniqueness, if one has two such product expressions, multiply through by the denominators and use the uniqueness part of Theorem 1.11

2 Using MAGMA

This section is a first introduction to MAGMA, which is an excellent package for doing algebraic number theory computations. You can use it via the web page

http://modular.fas.harvard.edu/calc. MAGMA is not free, but if you would

like a copy for your personal computer, send me an email, and I can arrange for you to obtain a legal copy for free. (Say something about my visiting MAGMA in Sydney three times, and how MAGMA compares to Maple, Mathematica, and PARI.)

1. MAGMA web page

2. Example code to illustrate things so far in course, and relevant to each homework problems. Experiment with students suggesting what examples to try.

3 Algorithms for Algebraic Number Theory

The best overall reference for algorithms for doing basic algebraic number theory computations is Henri Cohen’s book A Course in Computational Algebraic Number Theory, Springer, GTM 138.

Our main long-term algorithmic goals for this course are to understand good algorithms for solving the following problems in particular cases:

• Ring of integers: Given a number field K (by giving a polynomial), compute the full ring O_{K} of integers.

• Decomposition of primes: Given a prime number p ∈ Z, find the decomposition of the ideal pO_{K} as a product of prime ideals of O_{K}.

• Class group: Compute the group of equivalence classes of nonzero ideals of O_{K}, where I and J are equivalent if there exists α ∈ O_{K} such that IJ^{−1} = (α).

• Units: Compute generators for the group of units of O_{K}.

As we will see, somewhat surprisingly it turns out that algorithmically by far the most time-consuming step in computing the ring of integers O_{K} is to factor the discriminant of a polynomial whose root generates the field K. The algorithm(s) for computing O_{K} are quite complicated to describe, but the first step is to factor this discriminant, and it takes much longer in practice than all the other complicated steps.