\documentclass[12pt]{article}1\usepackage[active]{srcltx}2\usepackage{graphicx}3\input{macros}4\hoffset=-0.05\textwidth5\textwidth=1.1\textwidth6\voffset=-0.08\textheight7\textheight=1.16\textheight89\title{Math 129: Algebraic Number Theory\\10{\bf Lecture 4}}11\author{William Stein}12\date{Tuesday, February 17, 2004}13\begin{document}14\maketitle1516Note: There's a book called {\em Algebraic Number Theory and Fermat's17Last Theorem} by Stewart and Tall, which appears to have a detailed18introduction to algebraic number theory and assumes little background19on the part of the reader. There is a discussion of the definition of20module, and proofs of basic facts about number fields, and many21exercises. If you find Swinnerton-Dyer's book difficult, you might22want to try to get your hands on Stewart and Tall, which costs about23\$38 new. (Hand around a copy.)2425Today we will deduce, with complete proofs, the most important basic26property of the ring of integers $\O_K$ of an algebraic number, namely27that every nonzero ideals can be written uniquely as products of prime28ideals. After proving this fundamental theorem, we will compute some29examples using MAGMA. On Thursday the lecture will consist mostly of30examples illustrating the substantial theory we will have already31developed, so hang in there!3233\section{Dedekind Domains}34\begin{corollary}\label{prop:intnoetherian}35The ring of integers $\O_K$ of a number field is Noetherian.36\end{corollary}37\begin{proof}38As we saw before using norms, the ring $\O_K$ is finitely generated as39a module over~$\Z$, so it is certainly finitely generated as a ring40over~$\Z$. By the Hilbert Basis Theorem, $\O_K$ is Noetherian.41\end{proof}4243If $R$ is an integral domain, the {\em field of fractions} of $R$ is44the field of all elements $a/b$, where $a,b \in R$. The field of45fractions of $R$ is the smallest field that contains~$R$. For46example, the field of fractions of $\Z$ is $\Q$ and of47$\Z[(1+\sqrt{5})/2]$ is $\Q(\sqrt{5})$.4849\begin{definition}[Integrally Closed]50An integral domain $R$ is {\em integrally closed in its field of51fractions} if whenever $\alpha$ is in the field of fractions of $R$52and $\alpha$ satisfies a monic polynomial $f\in R[x]$, then $\alpha53\in R$.54\end{definition}5556\begin{proposition}\label{prop:integrallyclosed}57If $K$ is any number field, then $\O_K$ is integrally closed. Also,58the ring $\Zbar$ of all algebraic integers is integrally closed.59\end{proposition}60\begin{proof}61We first prove that~$\Zbar$ is integrally closed. Suppose $c\in\Qbar$62is integral over~$\Zbar$, so there is a monic polynomial $f(x)=x^n +63a_{n-1}x^{n-1} + \cdots + a_1 x + a_0$ with $a_i\in\Zbar$ and64$f(c)=0$. The $a_i$ all lie in the ring of integers $\O_K$ of the65number field $K=\Q(a_0,a_1,\ldots a_{n-1})$, and $\O_K$ is finitely66generated as a $\Z$-module, so $\Z[a_0,\ldots, a_{n-1}]$ is finitely67generated as a $\Z$-module. Since $f(c)=0$, we can write $c^n$ as a68$\Z[a_0,\ldots, a_{n-1}]$-linear combination of $c^i$ for $i<n$, so69the ring $\Z[a_0,\ldots, a_{n-1},c]$ is also finitely generated as a70$\Z$-module. Thus $\Z[c]$ is finitely generated as $\Z$-module71because it is a submodule of a finitely generated $\Z$-module, which72implies that~$c$ is integral over~$\Z$.7374Suppose $c\in K$ is integral over $\O_K$. Then since $\Zbar$ is75integrally closed,~$c$ is an element of $\Zbar$, so $c\in K \cap76\Zbar=\O_K$, as required.77\end{proof}7879\begin{definition}[Dedekind Domain]80An integral domain~$R$ is a {\em Dedekind domain} if it is Noetherian,81integrally closed in its field of fractions, and every nonzero prime82ideal of $R$ is maximal.83\end{definition}84The ring $\Q\oplus \Q$ is Noetherian, integrally closed in its field85of fractions, and the two prime ideals are maximal. However, it is86not a Dedekind domain because it is not an integral domain. The ring87$\Z[\sqrt{5}]$ is not a Dedekind domain because it is not integrally88closed in its field of fractions, as $(1+\sqrt{5})/2$ is integrally89over $\Z$ and lies in $\Q(\sqrt{5})$, but not in $\Z[\sqrt{5}]$. The90ring $\Z$ is a Dedekind domain, as is any ring of integers $\O_K$ of a91number field, as we will see below. Also, any field $K$ is a Dedekind92domain, since it is a domain, it is trivially integrally closed in93itself, and there are no nonzero prime ideals so that condition that94they be maximal is empty.9596\begin{proposition}97The ring of integers $\O_K$ of a number field is a Dedekind domain.98\end{proposition}99\begin{proof}100By Proposition~\ref{prop:integrallyclosed}, the ring $\O_K$ is101integrally closed, and by Proposition~\ref{prop:intnoetherian} it is102Noetherian. Suppose that~$\p$ is a nonzero prime ideal of $\O_K$.103Let $\alpha\in \p$ be a nonzero element, and let $f(x)\in\Z[x]$ be the104minimal polynomial of~$\alpha$. Then105$$f(\alpha)=\alpha^n+a_{n-1}\alpha^{n-1}+\cdots+a_1\alpha+a_0=0,$$ so106$a_0 = -(\alpha^n+a_{n-1}\alpha^{n-1}+\cdots+a_1\alpha)\in \p$. Since107$f$ is irreducible, $a_0$ is a nonzero element of $\Z$ that lies108in~$\p$. Every element of the finitely generated abelian group109$\O_K/\p$ is killed by~$a_0$, so $\O_K/\p$ is a finite set.110Since~$\p$ is prime, $\O_K/\p$ is an integral domain. Every finite111integral domain is a field, so $\p$ is maximal, which112completes the proof.113\end{proof}114115If $I$ and $J$ are ideals in a ring $R$, the product $IJ$ is the ideal116generated by all products of elements in $I$ with elements in $J$:117$$118IJ = (ab : a\in I, b\in J) \subset R.119$$120Note that the set of all products $ab$, with $a\in I$ and $b\in J$,121need not be an ideal, so it is important to take the ideal generated122by that set. (See the homework problems for examples.)123124\begin{definition}[Fractional Ideal]\label{def:fracideal}125A {\em fractional ideal} is an $\O_K$-submodule of $I\subset K$ that126is finitely generated as an $\O_K$-module.127\end{definition}128To avoid confusion, we will sometimes call a genuine ideal $I\subset129\O_K$ an {\em integral ideal}. Also, since fractional ideals are130finitely generated, we can clear denominators of a generating set to131see that every fractional ideal is of the form $a I = \{a b : b \in132I\}$ for some $a\in K$ and ideal $I\subset \O_K$.133134For example, the collection $\frac{1}{2}\Z$ of rational numbers with135denominator $1$ or $2$ is a fractional ideal of $\Z$.136137\begin{theorem}\label{thm:ddabgrp}138The set of nonzero fractional ideals of a Dedekind domain~$R$ is an139abelian group under ideal multiplication.140\end{theorem}141Before proving Theorem~\ref{thm:ddabgrp} we prove a lemma. For the142rest of this section $\O_K$ is the ring of integers of a number143field~$K$.144145146\begin{definition}[Divides for Ideals]147Suppose that $I,J$ are ideals of $\O_K$.148Then~$I$ {\em divides}~$J$ if $I\supset J$.149\end{definition}150To see that this notion of divides is sensible, suppose $K=\Q$, so151$\O_K=\Z$. Then $I=(n)$ and $J=(m)$ for some integer $n$ and $m$, and152$I$ divides $J$ means that $(n)\supset (m)$, i.e., that there exists153an integer~$c$ such that $m=cn$, which exactly means that $n$ divides154$m$, as expected.155156\begin{lemma}\label{lem:divprod}157Suppose~$I$ is an ideal of $\O_K$. Then there exist prime ideals158$\p_1,\ldots, \p_n$ such that $\p_1\cdot \p_2\cdots \p_n \subset{}I$.159In other words,~$I$ divides a product of prime ideals. (By convention160the empty product is the unit ideal. Also, if $I=0$, then we take161$\p_1=(0)$, which is a prime ideal.)162\end{lemma}163\begin{proof}164The key idea is to use that $\O_K$ is Noetherian to deduce that the165set~$S$ of ideals that do not satisfy the lemma is empty. If~$S$ is166nonempty, then because $\O_K$ is Noetherian, there is an ideal $I\in167S$ that is maximal as an element of~$S$. If~$I$ were prime, then~$I$168would trivially contain a product of primes, so~$I$ is not prime. By169definition of prime ideal, there exists $a,b\in \O_K$ such that $ab\in170I$ but $a\not\in I$ and $b\not\in I$. Let $J_1 = I+(a)$ and171$J_2=I+(b)$. Then neither $J_1$ nor $J_2$ is in $S$, since $I$ is172maximal, so both $J_1$ and $J_2$ contain a product of prime ideals.173Thus so does $I$, since174$$J_1 J_2 = I^2 + I(b)+ (a)I+ (ab) \subset I,$$175which is a contradiction. Thus~$S$ is empty, which completes the proof.176\end{proof}177178We are now ready to prove the theorem.179180\begin{proof}[Proof of Theorem~\ref{thm:ddabgrp}]181The product of two fractional ideals is again finitely generated, so182it is a fractional ideal, and $I\O_K=\O_K$ for any nonzero ideal~$I$,183so to prove that the set of fractional ideals under multiplication is184a group it suffices to show the existence of inverses. We will first185prove that if $\p$ is a prime ideal, then $\p$ has an inverse, then we186will prove that nonzero integral ideals have inverses, and finally187observe that every fractional ideal has an inverse.188189Suppose $\p$ is a nonzero prime ideal of $\O_K$. We will show that190the $\O_K$-module191$$192I = \{a \in K : a\p \subset \O_K \}193$$194is a fractional ideal of $\O_K$ such that $I\p = \O_K$, so that195$I$ is an inverse of $\p$.196197For the rest of the proof, fix a nonzero element $b\in \p$. Since~$I$198is an $\O_K$-module, $bI\subset \O_K$ is an $\O_K$ ideal, hence~$I$ is199a fractional ideal. Since $\O_K \subset I$ we have $\p \subset I \p200\subset \O_K$, hence either $\p = I\p$ or $I\p = \O_K$. If201$I\p=\O_K$, we are done since then~$I$ is an inverse of~$\p$. Thus202suppose that $I\p=\p$. Our strategy is to show that there is some203$d\in I$ not in $\O_K$; such a~$d$ would leave~$\p$ invariant (i.e.,204$d \p \subset \p$), so since $\p$ is an $\O_K$-module it will follow205that $d\in \O_K$, a contradiction.206207By Lemma~\ref{lem:divprod}, we can choose a product $\p_1,\ldots, \p_m$,208with~$m$ minimal, such that209$$210\p_1\p_2\cdots \p_m \subset (b) \subset \p.211$$ If no $\p_i$ is contained in $\p$, then we can choose for each $i$212an $a_i \in \p_i$ with $a_i\not\in \p$; but then $\prod a_i\in \p$,213which contradicts that $\p$ is a prime ideal. Thus some $\p_i$, say214$\p_1$, is contained in $\p$, which implies that $\p_1 = \p$ since215every nonzero prime ideal is maximal. Because~$m$ is minimal,216$\p_2\cdots \p_m$ is not a subset of $(b)$, so there exists $c\in217\p_2\cdots \p_m$ that does not lie in $(b)$. Then $\p(c) \subset (b)$,218so by definition of $I$ we have $d=c/b\in I$. However, $d\not\in219\O_K$, since if it were then $c$ would be in $(b)$. We have thus220found our element $d\in I$ that does not lie in $\O_K$. To finish the221proof that $\p$ has an inverse, we observe that $d$ preserves the222$\O_K$-module $\p$, and is hence in $\O_K$, a contradiction. More223precisely, if $b_1,\ldots, b_n$ is a basis for $\p$ as a $\Z$-module,224then the action of~$d$ on~$\p$ is given by a matrix with entries in225$\Z$, so the minimal polynomial of $d$ has coefficients in $\Z$. This226implies that $d$ is integral over $\Z$, so $d\in \O_K$, since $\O_K$227is integrally closed by Proposition~\ref{prop:integrallyclosed}.228(Note how this argument depends strongly on the fact that $\O_K$ is229integrally closed!)230231So far we have proved that if $\p$ is a prime ideal of $\O_K$, then232$\p^{-1} = \{a \in \K : a\p \subset \O_K\}$ is the inverse of $\p$ in233the monoid of nonzero fractional ideals of $\O_K$. As mentioned after234Definition~\ref{def:fracideal}, every nonzero fractional ideal is of235the form $aI$ for $a\in K$ and $I$ an integral ideal, so since $(a)$236has inverse $(1/a)$, it suffices to show that every integral ideal~$I$237has an inverse. If not, then there is a nonzero integral ideal~$I$238that is maximal among all nonzero integral ideals that do not have an239inverse. Every ideal is contained in a maximal ideal, so there is a240nonzero prime ideal $\p$ such that $I\subset \p$. Then $I \subset241\p^{-1} I \subset \O_K$. If $I = \p^{-1} I$, then (arguing as in the242previous paragraph) each element of $\p^{-1}$ preserves that243$\O_K$-ideal~$I$ and is hence integral, so $\p^{-1}\subset \O_K$,244which implies that $\O_K = \p \p^{-1} \subset \p$, a contradiction.245Thus $I \neq \p^{-1} I$. Because $I$ is maximal among ideals that do246not have an inverse, the ideal $\p^{-1} I$ does have an inverse, call247it~$J$. Then $\p{}J$ is the inverse of $I$, since $\O_K =248(\p{}J)(\p^{-1}I) = JI$.249\end{proof}250251We can finally deduce the crucial Theorem~\ref{thm:intuniqfac}, which252will allow us to show that any nonzero ideal of a Dedekind domain can253be expressed uniquely as a product of primes (up to order). Thus254unique factorization holds for ideals in a Dedekind domain, and it is255this unique factorization that initially motivated the introduction of256rings of integers of number fields over a century ago.257258\begin{theorem}\label{thm:uniqfac}259Suppose $I$ is an integral ideal of $\O_K$. Then $I$ can260be written as a product261$$262I = \p_1\cdots \p_n263$$ of prime ideals of $\O_K$, and this representation is unique up to264order. (Exception: If $I=0$, then the representation is not unique.)265\end{theorem}266\begin{proof}267Suppose $I$ is an ideal that is maximal among the set of all ideals in268$\O_K$ that can not be written as a product of primes. Every ideal is269contained in a maximal ideal, so $I$ is contained in a nonzero prime270ideal $\p$. If $I\p^{-1} = I$, then by Theorem~\ref{thm:ddabgrp} we271can cancel $I$ from both sides of this equation to see that272$\p^{-1}=\O_K$, a contradiction. Thus $I$ is strictly contained in273$I\p^{-1}$, so by our maximality assumption on $I$ there are maximal274ideals $\p_1,\ldots, \p_n$ such that $I\p^{-1} = \p_1\cdots \p_n$.275Then $I=\p\cdot \p_1\cdots \p_n$, a contradiction. Thus every ideal276can be written as a product of primes.277278Suppose $\p_1\cdots \p_n=\q_1\cdots \q_m$. If no $\q_i$ is contained in279$\p_1$, then for each $i$ there is an $a_i\in \q_i$ such that280$a_i\not\in\p_1$. But the product of the $a_i$ is in the $\p_1\cdots281\p_n$, which is a subset of $\p_1$, which contradicts the fact that282$\p_1$ is a prime ideal. Thus $\q_i=\p_1$ for some~$i$. We can thus283cancel $\q_i$ and $\p_1$ from both sides of the equation. Repeating284this argument finishes the proof of uniqueness.285\end{proof}286287\begin{corollary}\label{thm:intuniqfac}288If $I$ is a fractional ideal of $\O_K$ then there exists289prime ideals $\p_1,\ldots, \p_n$ and $\q_1,\ldots, \q_m$,290unique up to order, such that291$$292I = (\p_1\cdots \p_n)(\q_1\cdots \q_m)^{-1}.293$$294\end{corollary}295\begin{proof}296We have $I=(a/b)J$ for some $a,b\in\O_K$ and integral ideal $J$.297Applying Theorem~\ref{thm:intuniqfac} to $(a)$, $(b)$, and $J$ gives298an expression as claimed. For uniqueness, if one has two such product299expressions, multiply through by the denominators and use the300uniqueness part of Theorem~\ref{thm:intuniqfac}301\end{proof}302303\section{Using MAGMA}304This section is a first introduction to MAGMA, which is an excellent305package for doing algebraic number theory computations. You can use306it via the web page \verb|http://modular.fas.harvard.edu/calc|. MAGMA307is not free, but if you would like a copy for your personal computer,308send me an email, and I can arrange for you to obtain a legal copy for309free. (Say something about my visiting MAGMA in Sydney three times,310and how MAGMA compares to Maple, Mathematica, and PARI.)311312\begin{enumerate}313\item MAGMA web page314%\item Pictures of some people who work for MAGMA315%\item Claus Fieker is responsible for much of the algebraic number316%theory code in MAGMA.317\item Example code to illustrate things so far in course, and relevant318to each homework problems. Experiment with students suggesting what319examples to try.320\end{enumerate}321322323\section{Algorithms for Algebraic Number Theory}324The best overall reference for algorithms for doing basic algebraic325number theory computations is Henri Cohen's book {\em A Course in326Computational Algebraic Number Theory}, Springer, GTM 138.327328Our main long-term algorithmic goals for this course are to understand329good algorithms for solving the following problems in particular330cases:331\begin{itemize}332\item {\bf Ring of integers:} Given a number field $K$ (by giving a333polynomial), compute the full ring $\O_K$ of integers.334\item {\bf Decomposition of primes:} Given a prime number $p\in\Z$, find the335decomposition of the ideal $p\O_K$ as a product336of prime ideals of $\O_K$.337\item {\bf Class group:} Compute the group of equivalence classes338of nonzero ideals of $\O_K$, where $I$ and $J$339are equivalent if there exists $\alpha \in \O_K$340such that $IJ^{-1}=(\alpha)$.341\item {\bf Units:} Compute generators for the group of342units of $\O_K$.343\end{itemize}344345As we will see, somewhat surprisingly it turns out that346algorithmically by far the most time-consuming step in computing the347ring of integers $\O_K$ is to factor the discriminant of a polynomial348whose root generates the field~$K$. The algorithm(s) for computing349$\O_K$ are quite complicated to describe, but the first step is to350factor this discriminant, and it takes much longer in practice than351all the other complicated steps.352353\end{document}354