\chapter{Unique factorization (finally!)}
\label{ch:unique_factorization}
Took long enough.

\section{Motivation}
Suppose we're interested in solutions to the
Diophantine equation $n = x^2 + 5y^2$ for a given $n$.
The idea is to try and ``factor'' $n$ in $\ZZ[\sqrt{-5}]$,
for example \[ 6 = (1+\sqrt{-5})(1-\sqrt{-5}). \]
Unfortunately, this is not so simple, because as I've said before
we don't have unique factorization of elements:
\[ 6 = 2 \cdot 3 = \left( 1+\sqrt{-5} \right)\left( 1-\sqrt{-5} \right). \]
One reason this doesn't work is that we don't have a notion of a
\emph{greatest common divisor}.
We can write $(35, 77) = 7$, but what do we make of $(3, 1+\sqrt{-5})$?

The trick is to use ideals as a ``generalized GCD''.
Recall that by $(a,b)$ I mean the ideal $\{ax + by \mid x,y \in \ZZ[\sqrt{-5}] \}$.
You can see that $(35, 77) = (7)$,
but $(3, 1+\sqrt{-5})$ will be left ``unsimplified'' because it doesn't
represent an actual value in the ring.
Using these \emph{sets} (ideals) as elements,
it turns out that we can develop a full theory
of prime factorization, and we do so in this chapter.

In other words, we use the ideal $(a_1, \dots, a_m)$
to interpret a ``generalized GCD'' of $a_1$, \dots, $a_m$.
In particular, if we have a number $x$ we want to represent,
we encode it as just $(x)$.

Going back to our example of $6$,
\[ (6) = (2) \cdot (3)
	= \left( 1+\sqrt{-5} \right) \cdot \left( 1-\sqrt{-5} \right). \]
Please take my word for it that in fact,
the complete prime factorization of $(6)$ into prime ideals is
\[
	(6)
	= (2,1-\sqrt{-5})^2 (3,1+\sqrt{-5})(3,1-\sqrt{-5})
	= \kp^2 \kq_1 \kq_2. \]
In fact, $(2) = \kp^2$, $(3) = \kq_1 \kq_2$,
$(1+\sqrt{-5}) = \kp \kq_1$, $(1-\sqrt{-5}) = \kp \kq_2$.
So $6$ indeed factorizes uniquely into ideals,
even though it doesn't factor into elements.

As one can see above,
ideal factorization is more refined than element factorization.
Once you have the factorization into \emph{ideals},
you can from there recover all the factorizations into \emph{elements}.
The upshot of this is that if we want to write $n$ as $x^2+5y^2$,
we just have to factor $n$ into ideals,
and from there we can recover all factorizations into elements,
and finally all ways to write $n$ as $x^2+5y^2$.
Since we can already break $n$ into rational prime factors
(for example $6 = 2 \cdot 3$ above)
we just have to figure out how each rational prime $p \mid n$ breaks down.
There's a recipe for this, \Cref{thm:factor_alg}!
In fact, I'll even tell you what is says in this special case:
\begin{itemize}
	\ii If $t^2+5$ factors as $(t+c)(t-c) \pmod p$,
	then $(p) = (p, c+\sqrt{-5})(p, c-\sqrt{-5})$.
	\ii Otherwise, $(p)$ is a prime ideal.
\end{itemize}
In this chapter we'll develop this theory of unique factorization in full generality.

%We saw earlier that in rings, such as $\ZZ[\sqrt{-5}]$, unique factorization can fail:
%\[ 6 = 2 \cdot 3 = \left( 1 - \sqrt{-5} \right)\left( 1 + \sqrt{5} \right). \]
%I mentioned that we thus turned to the notion of \emph{ideals},
%and defined the notion of a prime ideal.
%Then I said
%\begin{quote}
%	I now must regrettably inform you that prime factorization is still
%	not true even with the notion of a ``prime'' ideal
%	(though not I haven't told you how to multiply two ideals yet).
%	But it will work in the situations we care about most:
%	this is covered in the chapter on Dedekind domains.
%\end{quote}
%I can be precise about what's going to happen now.
%We'll define a Dedekind domain, which in particular includes all rings of integers $\OO_K$.
%Then prime factorization will work in Dedekind domains, and we'll throw a small party.

\begin{remark}
	In this chapter, I'll be using the letters $\ka$, $\kb$, $\kp$, $\kq$
	for ideals of $\OO_K$.
	When fractional ideals arise, I'll use $I$ and $J$ for them.
\end{remark}

\section{Ideal arithmetic}
\prototype{$(x)(y) = (xy)$, and $(x)+(y)=(\gcd(x, y))$. In any case, think in terms of generators.}
First, I have to tell you how to add and multiply two ideals $\ka$ and $\kb$.
\begin{definition}
	Given two ideals $\ka$ and $\kb$ of a ring $R$, we define
	\begin{align*}
		\ka + \kb &\defeq \left\{ a+b \mid a \in \ka, b \in \kb \right\} \\
		\ka \cdot \kb &\defeq \left\{ a_1b_1 + \dots + a_n b_n
			\mid a_i \in \ka, b_i \in \kb \right\}.
	\end{align*}
\end{definition}
(Note that infinite sums don't make sense in general rings, which is why in $\ka \cdot \kb$
we cut off the sum after some finite number of terms.)
You can readily check these are actually ideals.
This definition is more natural if you think about it in terms of
the generators of $\ka$ and $\kb$.
\begin{proposition}[Ideal arithmetic via generators]
	Suppose $\ka = \left( a_1, a_2, \dots, a_n \right)$
	and $\kb = \left( b_1, \dots, b_m \right)$ are ideals in a ring $R$.
	Then
	\begin{enumerate}[(a)]
		\ii $\ka + \kb$ is the ideal generated by $a_1, \dots, a_n, b_1, \dots, b_m$.
		\ii $\ka \cdot \kb$ is the ideal generated by $a_i b_j$,
		for $1 \le i \le n$ and $1 \le j \le m$.
	\end{enumerate}
\end{proposition}
\begin{proof}
	Pretty straightforward; just convince yourself that this result is correct.
\end{proof}
In other words, for sums you append the two sets of generators together,
and for products you take products of the generators.
Note that for principal ideals, this coincides with ``normal'' multiplication,
for example
\[ (3) \cdot (5) = (15) \]
in $\ZZ$.
\begin{remark}
Note that for an ideal $\ka$ and an element $c$,
the set \[ c \ka = \left\{ ca \mid a \in \ka \right\} \]
is equal to $(c) \cdot \ka$.
So ``scaling'' and ``multiplying by principal ideals'' are the same thing.
This is important, since we'll be using the two notions interchangeably.
\end{remark}
\begin{remark}
	The addition of two ideals does not correspond to the addition of elements --- for example, $(4)+(6)=(4, 6)=(2)$, but $4+6=10$.

	This is the best we can hope for --- addition of elements does not make sense for ideals --- for example, $1+1=2$ and $1+(-1)=0$, but as ideals, $(1)=(-1)$.

	In fact, addition of ideal is the straightforward generalization of $\gcd$ of elements --- as you can check in the example above, $\gcd(4, 6)=2$.

	Nevertheless, I hope you agree that $\ka+\kb$ is a natural notation, compared to something like $(\ka, \kb)$.

	Because factorization involves \emph{multiplying}, instead of adding, the ideals together, we will not need to use the notation $\ka+\kb$ any time soon.
\end{remark}

Finally, since we want to do factorization we better have some notion of divisibility.
So we define:
\begin{definition}
	We say $\ka$ divides $\kb$ and write $\ka \mid \kb$ if $\ka \supseteq \kb$.
\end{definition}
Note the reversal of inclusions!
So $(3)$ divides $(15)$, because $(15)$ is contained in $(3)$;
every multiple of $15$ is a multiple of $3$.
And from the example in the previous section: In $\ZZ[\sqrt{-5}]$,
$(3,1-\sqrt{-5})$ divides $(3)$ and $(1 - \sqrt{-5})$.

Finally, the \vocab{prime ideals} are defined as in \Cref{def:prime_ideal}:
$\kp$ is prime if $xy \in \kp$ implies $x \in \kp$ or $y \in \kp$.
This is compatible with the definition of divisibility:
\begin{exercise}
	A nonzero proper ideal $\kp$ is prime
	if and only if whenever $\kp$ divides $\ka \kb$,
	$\kp$ divides one of $\ka$ or $\kb$.
\end{exercise}
As mentioned in \Cref{rem:unit_sign_issue},
this also lets us ignore multiplication by units: $(-3) = (3)$.

\section{Dedekind domains}
\prototype{Any $\OO_K$ is a Dedekind domain.}
We now define a Dedekind domain as follows.
\begin{definition}
	An integral domain $\mathcal A$ is a \vocab{Dedekind domain}
	if it is Noetherian, integrally closed, and
	\emph{every nonzero prime ideal of $\mathcal A$ is in fact maximal}.
	(The last condition is the important one.)
\end{definition}

\begin{remark}
	We'll prove momentarily that
	$\OO_K$ is a Dedekind domain for any number field $K$.
	This is really the only case we'll use in Napkin.
	So, introducing the term ``Dedekind domain'' is mainly here to highlight
	which properties of $\OO_K$ are used for unique factorization,
	not because we will actually encounter other kinds of Dedekind domains.
\end{remark}

Here there's one new word I have to define for you, but we won't make much use of it.
\begin{definition}
	Let $R$ be an integral domain and let $K$ be its field of fractions.
	We say $R$ is \vocab{integrally closed} if
	the only elements $a \in K$ which are roots of \emph{monic} polynomials in $R$
	are the elements of $R$ (which are roots of the trivial $x-r$ polynomial).
\end{definition}
The \emph{interesting} condition in the definition
of a Dedekind domain is the last one: prime ideals and maximal ideals
are the same thing.
The other conditions are just technicalities,
but ``primes are maximal'' has real substance.
\begin{example}[$\ZZ$ is a Dedekind domain]
	The ring $\ZZ$ is a Dedekind domain.
	Note that
	\begin{itemize}
		\ii $\ZZ$ is Noetherian (for obvious reasons).
		\ii $\ZZ$ has field of fractions $\QQ$.
		If $f(x) \in \ZZ[x]$ is monic, then by the rational root theorem
		any rational roots are integers
		(this is the same as the proof that $\ol\ZZ \cap \QQ = \ZZ$).
		Hence $\ZZ$ is integrally closed.
		\ii The nonzero prime ideals of $\ZZ$ are $(p)$,
		which also happen to be maximal.
	\end{itemize}
\end{example}

The case of interest is a ring $\OO_K$ in which we wish to do factorizing.
We're now going to show that for any number field $K$, the ring $\OO_K$ is a Dedekind domain.
First, the boring part.
\begin{proposition}[$\OO_K$ integrally closed and Noetherian]
	For any number field $K$, the ring $\OO_K$ is integrally closed and Noetherian.
\end{proposition}
\begin{proof}
	Boring, but here it is anyways for completeness.

	Since $\OO_K \cong \ZZ^{\oplus n}$,\footnote{By \Cref{thm:OK_free_Z_module}.}
	we get that it's Noetherian.

	Now we show that $\OO_K$ is integrally closed.
	Suppose that $\eta \in K$ is the root of some polynomial with coefficients in $\OO_K$.
	Thus
	\[ \eta^n = \alpha_{n-1} \cdot \eta^{n-1} + \alpha_{n-2} \cdot \eta^{n-2}
		+ \dots + \alpha_0 \]
	where $\alpha_i \in \OO_K$. We want to show that $\eta \in \OO_K$ as well.

	Well, from the above, $\OO_K[\eta]$ is finitely generated\dots\
	thus $\ZZ[\eta] \subseteq \OO_K[\eta]$ is finitely generated.
	So $\eta \in \ol\ZZ$, and hence $\eta \in K \cap \ol\ZZ = \OO_K$.
\end{proof}
Now let's do the fun part.
We'll prove a stronger result, which will re-appear repeatedly.
\begin{theorem}[Important: prime ideals divide rational primes]
	\label{thm:prime_ideals_over_rational}
	Let $\OO_K$ be a ring of integers
	and $\kp$ a nonzero prime ideal inside it.
	Then $\kp$ contains a rational prime $p$.
	Moreover, $\kp$ is maximal.
\end{theorem}
For a concrete example, consider $(2+i) \subseteq \ZZ[i]$. In this case, $p = 5$,
and because $p \in (2+i)$, we get that the lattice is periodic in both dimensions
with period $5$, which implies finitely many points in $\{a+bi \mid 0 \le a, b \le 4, a, b \in \ZZ\}$
suffices to cover all cosets modulo the ideal.

The proof of the finiteness of the quotient here is closely related to the
statement that the mesh of the lattice is finite,
which will be covered in the next section.
% Point is, the proof is not that tricky.
% You just need to remember the last step is "finite integral domain imply field".
\begin{proof}
	Take any $\alpha \neq 0$ in $\kp$.
	Its Galois conjugates are algebraic integers
	so their product $\Norm(\alpha)/\alpha$ is in $\OO_K$
	(even though each individual conjugate need not be in $K$).
	Consequently, $\Norm(\alpha) \in \kp$,
	and we conclude $\kp$ contains some integer.

	Then take the smallest positive integer in $\kp$, say $p$.
	We must have that $p$ is a rational prime, since otherwise $\kp \ni p = xy$
	implies one of $x,y \in \kp$.
	This shows the first part.

	We now do something pretty tricky to show $\kp$ is maximal.
	Look at $\OO_K / \kp$;
	since $\kp$ is prime it's supposed to be an integral domain\dots\
	but we claim that it's actually finite!
	To do this, we forget that we can multiply on $\OO_K$.
	Recalling that $\OO_K \cong \ZZ^{\oplus n}$ as an abelian group,
	we obtain a map
	\[ {\FF_p}^{\oplus n} \cong \OO_K / (p) \surjto \OO_K / \kp. \]
	Hence $\left\lvert \OO_K / \kp \right\rvert \le p^n$ is \emph{finite}.
	Since finite integral domains are fields (\Cref{prob:finite_domain_field})
	we are done.
\end{proof}
Since every nonzero prime $\kp$ is maximal, we now know that $\OO_K$ is a Dedekind domain.
Note that this tricky proof is essentially inspired by the solution to \Cref{prob:dedekind_sample}.

\begin{remark}
	\label{remark:prime_ideals_are_maximal}
	An alternative proof for the first part is:
	because $\kp$ is an ideal, $\alpha \cdot \OO_K \subseteq \kp$, but $\alpha \cdot \OO_K$ is a
	free $\ZZ$-module of rank $n$, so $\kp$ is squeezed between two free $\ZZ$-modules of rank $n$,
	by \Cref{thm:fund_fg_abelian_group} we must have $\kp$ is also free of rank $n$.
	So the quotient is finite, then use \Cref{lemma:ideal_divides_norm}.
\end{remark}

\section{Unique factorization works}
Okay, I'll just say it now!
\begin{moral}
	Unique factorization works perfectly in Dedekind domains!
\end{moral}

\begin{remark}
	[Comparison between Dedekind domain and UFD]
	If we temporarily forget about the Noetherian and integrally closed condition, we have:
	\begin{itemize}
		\ii An integral domain admits unique factorization of elements if the prime elements and the irreducible elements are the same.
		\ii An integral domain admits unique factorization of ideals if the prime ideals and the maximal ideals are the same.
	\end{itemize}
	Notice the similarity --- in either case, the Noetherian condition is ``merely'' to ensure that, if you keep extracting prime factors, you will terminate in a finite time.
\end{remark}

\begin{example}
	[What went wrong if $\mathcal A$ is not integrally closed?]
	Consider $\mathcal A = 2\ZZ$, which is an ideal of $\ZZ$.
	Clearly, every nonzero prime ideal is maximal.

	Nevertheless, in $\mathcal A$,
	$(2 \cdot 3 \cdot 5)=(60)$ is not a prime ideal (so of course it isn't a maximal ideal),
	but we cannot break it down into, for example, $(2 \cdot 3) \cdot (5)$.
\end{example}

\begin{theorem}[Prime factorization works]
	Let $\ka$ be a nonzero proper ideal of a Dedekind domain $\mathcal A$.
	Then $\ka$ can be written as a finite product of nonzero prime ideals $\kp_i$, say
	\[ \ka = \kp_1^{e_1} \kp_2^{e_2} \dots \kp_g^{e_g} \]
	and this factorization is unique up to the order of the $\kp_i$.

	Moreover, $\ka$ divides $\kb$ if and only if for every prime ideal $\kp$,
	the exponent of $\kp$ in $\ka$ is less than or equal to the corresponding exponent in $\kb$.
\end{theorem}
%% Ofer joke
% As ideals, you and I are coprime because together we are (1).

I won't write out the proof, but I'll describe the basic method of attack.
Section 3 of \cite{ref:ullery} does a nice job of explaining it.
When we proved the fundamental theorem of arithmetic, the basic plot was:
\begin{enumerate}[(1)]
	\ii Show that if $p$ is a rational prime\footnote{Note
		that the kindergarten definition of a prime is
		that ``$p$ isn't the product of two smaller integers''.
		This isn't the correct definition of a prime:
		the definition of a prime is that $p \mid bc$
		means $p \mid b$ or $p \mid c$.
		The kindergarten definition is something called ``irreducible''.
		Fortunately, in $\ZZ$, primes and irreducibles are the same thing,
		so no one ever told you that your definition of ``prime'' was wrong.}
	then $p \mid bc$ means $p \mid b$ or $p \mid c$.  (This is called Euclid's Lemma.)
	\ii Use strong induction to show that every $N > 1$ can be written as the product of primes (easy).
	\ii Show that if $p_1 \dots p_m = q_1 \dots q_n$ for some primes (not necessarily unique),
	then $p_1 = q_i$ for some $i$, say $q_1$.
	\ii Divide both sides by $p_1$ and use induction.
\end{enumerate}
What happens if we try to repeat the proof here?
We get step 1 for free, because we're using a better definition of ``prime''.
We can also do step 3, since it follows from step 1.
But step 2 doesn't work,
because for abstract Dedekind domains
we don't really have a notion of size.
And step 4 doesn't work because we don't yet have a
notion of what the inverse of a prime ideal is.

Well, it turns out that we \emph{can} define the inverse $\ka\inv$ of an ideal,
and I'll do so by the end of this chapter.
You then need to check that $\ka \cdot \ka\inv = (1) = \mathcal A$.
In fact, even this isn't easy.
You have to check it's true for prime ideals $\kp$,
\emph{then} prove prime factorization,
and then prove that this is true.
Moreover, $\ka\inv$ is not actually an ideal, so you need to
work in the field of fractions $K$ instead of $\mathcal A$.

So the main steps in the new situation are as follows:
\begin{enumerate}[(1)]
	\ii First, show that every ideal $\ka$ divides $\kp_1 \dots \kp_g$
	for some finite collection of primes.
	(This is an application of Zorn's Lemma.)
	\ii Define $\kp\inv$ and show that $\kp \kp\inv = (1)$.
	\ii Show that a factorization exists (again using Zorn's Lemma).
	\ii Show that it's unique, using the new inverse we've defined.
\end{enumerate}

Finally, let me comment on how nice this is if $\mathcal A$ is a PID (like $\ZZ$).
Thus every element $a \in \mathcal A$ is in direct correspondence with an ideal $(a)$.
Now suppose $(a)$ factors as a product of ideals $\kp_i = (p_i)$, say,
\[ (a) = (p_1)^{e_1} (p_2)^{e_2} \dots (p_n)^{e_n} . \]
This verbatim reads \[ a = u p_1^{e_1} p_2^{e_2} \dots p_n^{e_n} \]
where $u$ is some unit (recall \Cref{def:unit}).
Hence, Dedekind domains which are PID's satisfy unique factorization
for \emph{elements}, just like in $\ZZ$.
(In fact, the converse of this is true.)

\section{The factoring algorithm}
Let's look at some examples from quadratic fields.
Recall that if $K = \QQ(\sqrt{d})$, then
\[
	\OO_K =
	\begin{cases}
		\ZZ[\sqrt d] & d \equiv 2,3 \pmod 4 \\
		\ZZ\left[ \frac{1+\sqrt d}{2} \right] & d \equiv 1 \pmod 4.
	\end{cases}
\]
Also, recall that the norm of $a+b\sqrt{-d}$ is given by $a^2+db^2$.

%In what follows, we are going to often use the trick that
%\[ \ZZ[\alpha] \cong \ZZ[x] / (f) \]
%where $f$ is the minimal polynomial of $\alpha$.

\begin{example}[Factoring $6$ in the integers of $\QQ(\sqrt{-5})$]
	Let $\OO_K = \ZZ[\sqrt{-5}]$ arise from $K = \QQ(\sqrt{-5})$.
	We've already seen that
	\[ (6) = (2) \cdot (3) = \left( 1+\sqrt{-5} \right)\left( 1-\sqrt{-5} \right) \]
	and you can't get any further with these principal ideals.
	But let
	\[ \kp = \left( 1+\sqrt{-5}, 2 \right) = \left( 1-\sqrt{-5}, 2 \right)
		\quad\text{and}\quad \kq_1 = (1+\sqrt{-5},3),
		\; \kq_2 = (1-\sqrt{-5},3). \]
	Then it turns out $(6) = \kp^2\kq_1\kq_2$.
	More specifically, $(2) = \kp^2$, $(3) = \kq_1\kq_2$,
	and $(1+\sqrt{-5}) = \kp\kq_1$ and $(1-\sqrt{-5}) = \kp\kq_2$.
	(Proof in just a moment.)
\end{example}
I want to stress that all our ideals are computed relative to $\OO_K$.
So for example, \[ (2) = \left\{ 2x \mid x \in \OO_K \right\}. \]

How do we know in this example that $\kp$ is prime/maximal?
(Again, these are the same since we're in a Dedekind domain.)
Answer: look at $\OO_K / \kp$ and see if it's a field.
There is a trick to this: we can express
\[ \OO_K = \ZZ[\sqrt{-5}] \cong \ZZ[x] / (x^2+5). \]
%\begin{ques}
%	Convince yourself this is true.
%	(More generally, if $\theta \in \ol\ZZ$ has minimal polynomial $p$,
%	then $\ZZ[\theta] \cong \ZZ[x] / (p)$).
%\end{ques}
So when we take \emph{that} mod $\kp$, we get that
\[ \OO_K / \kp = \ZZ[x] / (x^2+5, 2, 1+x) \cong \FF_2[x] / (x^2+5,x+1) \]
as rings.
\begin{ques}
	Conclude that $\OO_K / \kp \cong \mathbb F_2$,
	and satisfy yourself that $\kq_1$ and $\kq_2$ are also maximal.
\end{ques}
I should give an explicit example of an ideal multiplication: let's compute
\begin{align*}
	\kq_1\kq_2 &= \left( (1+\sqrt{-5})(1-\sqrt{-5}), 3(1+\sqrt{-5}), 3(1-\sqrt{-5}), 9 \right) \\
	&= \left( 6, 3+3\sqrt{-5}, 3-3\sqrt{-5}, 9 \right) \\
	&= \left( 6, 3+3\sqrt{-5}, 3-3\sqrt{-5}, 3 \right) \\
	&= (3)
\end{align*}
where we first did $9-6=3$ (think Euclidean algorithm!),
then noted that all the other generators don't contribute
anything we don't already have with the $3$
(again these are ideals computed in $\OO_K$).
You can do the computation for $\kp^2$, $\kp\kq_1$, $\kp\kq_2$ in the same way.

Finally, it's worth pointing out that we should quickly
verify that $\kp \neq (x)$ for some $x$;
in other words, that $\kp$ is not principal.
Assume for contradiction that it is.
Then $x$ divides both $1+\sqrt{-5}$ and $2$, in the sense
that $1+\sqrt{-5} = \alpha_1 x$ and $2 = \alpha_2 x$
for some $\alpha_1, \alpha_2 \in \OO_K$.
(Principal ideals are exactly the ``multiples'' of $x$, so $(x) = x \OO_K$.)
Taking the norms, we find that $\Norm_{K/\QQ}(x)$ divides both
\[ \Norm_{K/\QQ}(1+\sqrt{-5}) = 6 \quad\text{and}\quad \Norm_{K/\QQ}(2) = 4. \]
Since $\kp \neq (1)$, $x$ cannot be a unit, so its norm must be $2$.
But there are no elements of norm $2 = a^2+5b^2$ in $\OO_K$.

\begin{example}[Factoring $3$ in the integers of $\QQ(\sqrt{-17})$]
	Let $\OO_K = \ZZ[\sqrt{-17}]$ arise from $K = \QQ(\sqrt{-17})$.
	We know $\OO_K \cong \ZZ[x] / (x^2+17)$.
	Now
	\[
		\OO_K / 3\OO_K \cong \ZZ[x] / (3,x^2+17)
		\cong \FF_3[x] / (x^2-1).
	\]
	This already shows that $(3)$ cannot be a prime (i.e.\ maximal) ideal,
	since otherwise our result should be a field.
	Anyways, we have a projection
	\[ \OO_K \surjto \FF_3[x] / \left( (x-1)(x+1) \right). \]
	Let $\kq_1$ be the pre-image of $(x-1)$ in the image, that is,
	\[ \kq_1 = (3, \sqrt{-17}-1). \]
	Similarly, \[ \kq_2 = (3, \sqrt{-17}+1). \]
	We have $\OO_K / \kq_1 \cong \FF_3$, so $\kq_1$ is maximal (prime).
	Similarly $\kq_2$ is prime.
	Magically, you can check explicitly that
	\[ \kq_1 \kq_2 = (3). \]
	Hence this is the factorization of $(3)$ into prime ideals.
\end{example}

The fact that $\kq_1 \kq_2 = (3)$ looks magical, but it's really true:
\begin{align*}
	\kq_1\kq_2
	&= (3, \sqrt{-17}-1) (3, \sqrt{-17}+1) \\
	&= (9, 3\sqrt{-17}+3, 3\sqrt{-17}-3, 18) \\
	&= (9, 3\sqrt{-17}+3, 6) \\
	&= (3, 3\sqrt{-17}+3, 6) \\
	&= (3).
\end{align*}
In fact, it turns out this always works in general:
given a rational prime $p$, there is an algorithm
to factor $p$ in any $\OO_K$ of the form $\ZZ[\theta]$.

\begin{theorem}[Factoring algorithm / Dedekind-Kummer theorem]
	\label{thm:factor_alg}
	Let $K$ be a number field.
	Let $\theta \in \OO_K$ with $|\OO_K / \ZZ[\theta]| = j < \infty$,
	and let $p$ be a prime not dividing $j$.
	Then $(p) = p \OO_K$ is factored as follows:
	\begin{quote}
		Let $f$ be the minimal polynomial of $\theta$ and
		factor $\ol f$ mod $p$ as
		\[ \ol f \equiv \prod_{i=1}^g (\ol f_i)^{e_i} \pmod p. \]
		Then $\kp_i = (f_i(\theta), p)$ is prime for each $i$
		and the factorization of $(p)$ is
		\[ \OO_K \supseteq (p) = \prod_{i=1}^g \kp_i^{e_i}. \]
	\end{quote}
	In particular, if $K$ is monogenic with $\OO_K = \ZZ[\theta]$ then $j=1$
	and the theorem applies for all primes $p$.
\end{theorem}
In almost all our applications in this book, $K$ will be monogenic; i.e.\ $j=1$.
Here $\ol \psi$ denotes the image in $\FF_p[x]$ of a polynomial $\psi \in \ZZ[x]$.

\begin{ques}
	There are many possible pre-images $f_i$ we could have chosen
	(for example if $\ol{f_i} = x^2+1 \pmod 3$, we could pick $f_i = x^2 + 3x + 7$.)
	Why does this not affect the value of $\kp_i$?
\end{ques}

Note that earlier, we could check the factorization worked
for any particular case.
The proof that this works is much the same, but we need one extra tool, the ideal norm.
After that we leave the proposition as \Cref{prob:prove_factoring_algorithm}.

This algorithm gives us a concrete way to compute prime factorizations of $(p)$
in any monogenic number field with $\OO_K = \ZZ[\theta]$. To summarize the recipe:
\begin{enumerate}
	\ii Find the minimal polynomial of $\theta$, say $f \in \ZZ[x]$.
	\ii Factor $f$ mod $p$ into irreducible polynomials
	${\ol f_1}^{e_1} {\ol f_2}^{e_2} \dots {\ol f_g}^{e_g}$.
	\ii Compute $\kp_i = (f_i(\theta), p)$ for each $i$.
\end{enumerate}
Then your $(p) = \kp_1^{e_1} \dots \kp_g^{e_g}$.

Or even shorter:
\begin{moral}
	In order to factorize $p$ in $\ZZ[x]/(f(x))$, we can factorize $f(x)$ in $\ZZ[x]/(p)$ instead.
\end{moral}
Both are equivalent to factorizing $0$ in $\ZZ[x]/(f(x), p)$ --- in other words, writing
$\ZZ[x]/(f(x), p)$ as a direct sum of $\ZZ[x]$-modules.

\begin{exercise}
	Factor $(29)$ in $\ZZ[i]$ using the above algorithm.
\end{exercise}

%\begin{remark}
%	What if $K$ isn't monogenic?
%	It turns out that we can still apply the
%	factoring algorithm to ``almost all primes'' as follows.
%	Suppose $K$ is a number field and $\alpha \in \OO_K$ such that
%	$|\OO_K / \ZZ[\alpha]| = j < \infty$.
%	Then as long as $p \nmid j$, we can apply the above algorithm
%	with $f$ the minimal polynomial of $\alpha$.
%	The formulation we presented above was the special case where $j=1$.
%\end{remark}

\section{Fractional ideals}
\prototype{Analog to $\QQ$ for $\ZZ$, allowing us to take inverses of ideals.
Prime factorization works in the nicest way possible.}
We now have a neat theory of factoring ideals of $\mathcal A$,
just like factoring the integers.
Now note that our factorization of $\ZZ$ naturally gives a way to factor
elements of $\QQ$; just factor the numerator and denominator separately.

Let's make the analogy clearer.
The analogue of a rational number is as follows.

\begin{definition}
	Let $\mathcal A$ be a Dedekind domain with field of fractions $K$.
	A \vocab{fractional ideal} $J$ of $K$ is a set of the form
	\[ J = \frac{1}{x} \cdot \ka \quad \text{where $x \in \mathcal A$, and $\ka$ is an integral ideal.} \]
	For emphasis, ideals of $\mathcal A$ will be sometimes referred to as \vocab{integral ideals}.
\end{definition}

You might be a little surprised by this definition:
one would expect that a fractional ideal should be of the form $\frac{\ka}{\kb}$
for some integral ideals $\ka$, $\kb$.
But in fact, it suffices to just take $x \in \mathcal A$ in the denominator.
The analogy is that when we looked at $\OO_K$, we found that we only needed
integer denominators: $\frac{1}{4-\sqrt3} = \frac{1}{13}(4+\sqrt3)$.
Similarly here, it will turn out that we only need to look at $\frac1x \cdot \ka$
rather than $\frac{\ka}{\kb}$, and so we define it this way from the beginning.
See \Cref{prob:fractional_ideal_alt_def} for a different equivalent definition.

\begin{example}[$\frac52\ZZ$ is a fractional ideal]
	The set \[ \frac52 \ZZ = \left\{ \frac52n \mid n \in \ZZ \right\} = \half (5) \]
	is a fractional ideal of $\ZZ$.
\end{example}

Now, as we prescribed, the fractional ideals form a multiplicative group:
\begin{theorem}[Fractional ideals form a group]
	Let $\mathcal A$ be a Dedekind domain and $K$ its field of fractions.
	For any integral ideal $\ka$, the set
	\[ \ka\inv = \left\{ x \in K
			\mid x\ka \subseteq (1) = \mathcal A \right\} \]
	is a fractional ideal with $\ka \ka\inv = (1)$.
\end{theorem}

(This result is nontrivial.
To prove $\ka \ka\inv = (1)$, one approach is to prove it first
for prime $\ka$, then consider the factorization of $\ka$ into prime ideals.)
% approach used by Neukirch.
% I find proving 𝔞 𝔞⁻¹ ⊆ (1) trivial, but the reverse inclusion is difficult.

\begin{definition}
	Thus nonzero fractional ideals of $K$ form a group under multiplication
	with identity $(1) = \mathcal A$.
	This \vocab{ideal group} is denoted $J_K$.
\end{definition}

\begin{example}[$(3)\inv$ in $\ZZ$]
	Please check that in $\ZZ$ we have
	\[ (3)\inv = \left\{ \frac 13 n \mid n \in \ZZ \right\} = \frac 13 \ZZ. \]
\end{example}

It follows that every fractional ideal $J$ can be uniquely written as
\[ J = \prod_i \kp_i^{n_i} \cdot \prod_i \kq_i^{-m_i} \]
where $n_i$ and $m_i$ are positive integers.
In fact, $\ka$ is an integral ideal if and only if all its exponents are nonnegative,
just like the case with integers.
So, a perhaps better way to think about fractional ideals is
as products of prime ideals, possibly with negative exponents.

\section{The ideal norm}
One last tool is the ideal norm,
which gives us a notion of the ``size'' of an ideal.
\begin{definition}
	The \vocab{ideal norm} (or absolute norm)
	of a nonzero ideal $\ka \subseteq \OO_K$ is defined as
	$|\OO_K / \ka|$ and denoted $\Norm(\ka)$.
\end{definition}
\begin{example}[Ideal norm of $(5)$ in the Gaussian integers]
	Let $K = \QQ(i)$, $\OO_K = \ZZ[i]$.
	Consider the ideal $(5)$ in $\OO_K$.
	We have that
	\[ \OO_K / (5) \cong \{ a+bi \mid a,b \in \Zc5 \} \]
	so $(5)$ has ideal norm $25$,
	corresponding to the fact that $\OO_K/(5)$ has $5^2=25$ elements.
\end{example}

\begin{example}[Ideal norm of $(2+i)$ in the Gaussian integers]
	You'll notice that \[ \OO_K / (2+i) \cong \FF_5 \]
	since mod $2+i$ we have both $5 \equiv 0$ and $i \equiv -2$.
	(Indeed, since $(2+i)$ is prime we had better get a field!)
	Thus $\Norm\left( (2+i) \right) = 5$; similarly $\Norm\left( (2-i) \right) = 5$.
\end{example}

Thus the ideal norm measures how ``roomy'' the ideal is:
that is, $(5)$ is a lot more spaced out in $\ZZ[i]$ than it is in $\ZZ$.
(This intuition will be important when we will actually view $\OO_K$ as a lattice.)

\begin{ques}
	What are the ideals with ideal norm one?
\end{ques}
% Regrettably, ideals with more elements have smaller norms.

Our example with $(5)$ suggests several properties of the ideal norm
which turn out to be true:
\begin{lemma}[Properties of the absolute norm]
	Let $\ka$ be a nonzero ideal of $\OO_K$.
	\begin{enumerate}[(a)]
		\ii $\Norm(\ka)$ is finite.
		\ii For any other nonzero ideal $\kb$, $\Norm(\ka\kb) = \Norm(\ka)\Norm(\kb)$.
		\ii If $\ka = (a)$ is principal, then $\Norm(\ka) = |\Norm_{K/\QQ}(a)|$.
		% \ii The ideal norm $\Norm(\ka)$ equals the GCD of $\Norm_{K/\QQ}(\alpha)$ across
		% all $\alpha \in \ka$. In particular, if $\ka = (\alpha)$ is principal
		% then $\Norm(\ka) = \Norm_{K/\QQ}(\alpha)$.
	\end{enumerate}
\end{lemma}
I unfortunately won't prove these properties, though we already did (a) in our proof that $\OO_K$
was a Dedekind domain.
% Anyways, this lemma provides another way to show an ideal isn't principal.

%\begin{example}[Example of an Ideal Norm]
%	Let $K = \QQ(\sqrt 3)$, so $\OO_K = \ZZ[\sqrt 3]$.
%	% \ii The norm of the principal ideal $(4+\sqrt 3)$ is the norm of the element, $(4+\sqrt3)(4-\sqrt3) = 13$.
%	% \ii
%	Consider $\ka = (2, \sqrt3)$.
%		We need to have
%		\[ \Norm(\ka) \mid \gcd(\Norm_{K/\QQ}(2), \Norm_{K/\QQ}(3)) = \gcd(4, 3) = 1. \]
%		So in fact, $\Norm(\ka) = 1$. Surprise!
%		This actually means $\ka = (1)$,
%		which in hindsight also follows from the fact that
%		$\sqrt 3 \in \ka$, thus $\sqrt 3 \cdot \sqrt 3 \in \ka$ and $3 \in \ka$;
%		but $2 \in \ka$ so $1 \in \ka$.
%\end{example}

As with the case of the norm of an element, the ideal norm also has a geometrical interpretation:
Recall that if $\ka = (a)$, let $\mu_a$ be the multiplication-by-$a$ map,
then $\Norm_{K/\QQ}(a) = |\det \mu_a|$ measures how much $K$ is stretched under $\mu_a$ when viewed
as a $\QQ$-vector space.
\begin{exercise}
	Convince yourself that if $\mu_a(\OO_K) \subseteq \OO_K$, then $|\OO_K / a \OO_K|$ is
	exactly equal to $|\det \mu_a|$.
\end{exercise}
This explains why $\Norm(\ka) = |\Norm_{K/\QQ}(a)|$, although note that $\ka = (a) = (-a)$, so there
need not be an unique multiplication-by-$\ka$ map.

The fact that $\Norm$ is completely multiplicative lets us also consider the norm
of a fractional ideal $J$ by the natural extension
\[ J = \prod_i \kp_i^{n_i} \cdot \prod_i \kq_i^{-m_i}
	\quad \implies \quad
	\Norm(J) \defeq \frac{\prod_i \Norm(\kp_i)^{n_i}}{\prod_i \Norm(\kq_i)^{m_i}}. \]
Thus $\Norm$ is a natural group homomorphism $J_K \to \QQ^\times$.


\section\problemhead
\begin{problem}
	Show that there are three different factorizations of $77$ in $\OO_K$,
	where $K = \QQ(\sqrt{-13})$.
\end{problem}

\begin{problem}
	Let $K = \QQ(\cbrt 2)$;
	take for granted that $\OO_K = \ZZ[\cbrt 2]$.
	Find the factorization of $(5)$ in $\OO_K$.
\end{problem}

\begin{problem}
	[Fermat's little theorem]
	Let $\kp$ be a prime ideal in some ring of integers $\OO_K$.
	Show that for $\alpha \in \OO_K$,
	\[ \alpha^{\Norm(\kp)} \equiv \alpha \pmod{\kp}. \]
	\begin{hint}
		Copy the proof of the usual Fermat's little theorem.
	\end{hint}
	\begin{sol}
		If $\alpha \equiv 0 \pmod{\kp}$ it's clear, so assume this isn't the case.
		Then $\OO_K/\kp$ is a finite field with $\Norm(\kp)$ elements.
		Looking at $(\OO_K/\kp)^\ast$, it's a multiplicative group with $\Norm(\kp)-1$ elements,
		so $\alpha^{\Norm(\kp)-1} \equiv 1 \pmod{\kp}$, as desired.
	\end{sol}
\end{problem}

\begin{dproblem}
	Let $\mathcal A$ be a Dedekind domain with field of fractions $K$,
	and pick $J \subseteq K$.
	Show that $J$ is a fractional ideal if and only if
	\begin{enumerate}[(i)]
		\ii $J$ is closed under addition and multiplication
		by elements of $\mathcal A$, and
		\ii $J$ is finitely generated as an abelian group.
	\end{enumerate}
	More succinctly: $J$ is a fractional ideal $\iff$ $J$ is a finitely generated $\mathcal A$-module.
	\label{prob:fractional_ideal_alt_def}
	\begin{hint}
		Clear denominators!
	\end{hint}
	\begin{sol}
		Suppose it's generated by some elements in $K$; we can write them as
		$\frac{\beta_i}{\alpha_i}$ for $\alpha_i, \beta_i \in \mathcal A$.
		Hence
		\[ J = \left\{ \sum_i \gamma_i \cdot \frac{\beta_i}{\alpha_i}
		\mid \alpha_i, \beta_i, \gamma_i \in \OO_K \right\}. \]
		Now ``clear denominators''. Set $\alpha = \alpha_1 \dots \alpha_n$,
		and show that $\alpha J$ is an integral ideal.
	\end{sol}
\end{dproblem}

\begin{problem}
	\label{prob:prove_factoring_algorithm}
	In the notation of \Cref{thm:factor_alg}, let $I = \prod_{i=1}^g \kp_i^{e_i}$.
	Assume for simplicity that $K$ is monogenic, hence $\OO_K = \ZZ[\theta]$.
	\begin{enumerate}[(a)]
		\ii Prove that each $\kp_i$ is prime.
		\ii Show that $(p)$ divides $I$.
		\ii Use the norm to show that $(p) = I$.
	\end{enumerate}
	\begin{hint}
		(a) is straightforward.
		For (b) work mod $p$.
		For (c) use norms.
	\end{hint}
	\begin{sol}
	For part (a), note that the $\kp_i$ are prime
	just because
	\[ \OO_K / \kp_i
		\cong (\ZZ[x] / f) / (p, f_i)
		\cong \FF_p[x] / (f_i) \]
	is a field, since the $f_i$ are irreducible.

	We check (b).
		Computing the product modulo $p$ yields\footnote{%
			For example, suppose we want to know that $(3, 1+\sqrt{7})(3, 1-\sqrt{7})$ is contained in $(3)$.
			We could do the full computation and get $(9, 3+3\sqrt{7}, 3-3\sqrt{7}, 6)$.
			But if all we care about is that every element is divisible by $3$, we could have just taken ``mod $3$''
			at the beginning and looked at just $(1+\sqrt{7})(1-\sqrt{7}) = (6)$;
			all the other products we get will obviously have factors of $3$.
		}
		\[ \prod_{i=1}^{g} (f_i(\theta))^{e_i}
			\equiv (f(\theta)) \equiv 0 \pmod p \]
		so we've shown that $I \subseteq (p)$.

	Finally, we prove (c) with a size argument.
		The idea is that $I$ and $(p)$ really should have the same size;
		to nail this down we'll use the ideal norm.
		Since $(p)$ divides $I$, we can write
		$ (p) = \prod_{i=1}^g \kp_i^{e_i'} $
		where $e_i' \le e_i$ for each $i$.
		Remark $\OO_K / (p) \cong \Zc p[x] / (f)$ has size $p^{\deg f}$.
		Similarly, $\OO_K / \kp_i$ has size $p^{\deg f_i}$ for each $i$.
		Compute $\Norm( (p) )$ using the $e_i'$ now and compare the results.
%		Hence
%		\[ p^{\deg f} = \Norm(p)
%		= \prod_{i=1}^r \Norm(\kp_i)^{e_i'}
%		= p^{e_1' \deg f_1 + \dots + e_g' \deg f_g}. \]
%		Hence
%		\[ e_1' \deg f_1 + \dots e_g' \deg f_g = \deg f. \]
%		On the other hand, it's obvious that \[ \deg f = e_1 \deg f_1 + \dots + e_g \deg f_g. \]
%		As $e_i' \le e_i$ for each $i$, we can only have $e_i = e_i'$.
	\end{sol}
\end{problem}

\begin{problem}
	[USEMO 2025]
	\onechili
	Let $k$ be a positive integer not divisible by $6$.
	Suppose that there exists a prime $p$
	such that $p$ divides both $2025^k-1$ and $2026^k-1$.
	Prove that $p<3^k$.
	\begin{hint}
		Let $\omega$ be a $k$'th root of unity.
		Let $\kp$ be any prime ideal above $p$ in the ring of integers of $K = \QQ(\omega)$.
		Show that there exist indices $i$ and $j$ such that
		$2025-\omega^i$ and $2026-\omega^j$ are in $\kp$.
		Then show that $1+\omega^i-\omega^j$ is nonzero with norm at most $3^k$.
	\end{hint}
	\begin{sol}
		As before, set $\omega \coloneq e^{\frac{2i\pi}{k}}$.
		Let $K = \QQ(\omega)$ and choose any prime ideal $\kp$ of $\mathcal{O}_K$ lying over $p\ZZ$.

		We know that
		\[ \prod_{i=0}^{k-1} (2025-\omega^i) = 2025^k-1 \in (p) \subseteq \kp \]
		and since $\kp$ is prime ideal, we know $2025-\omega^i \in \kp$ for some $i$.
		Similarly $2026-\omega^j \in \kp$ for some $j$.
		Subtracting,
		\[ (2026-\omega^j) - (2025-\omega^i) = 1 + \omega^i - \omega^j \in \kp \implies p \mid \Norm_{K/\QQ}(1+\omega^i-\omega^j). \]
		Since $6\nmid k$, it follows that $1 + \omega^i - \omega^j \neq 0$,
		and so $p$ is at most the norm above.
		However, straight from the definitions,
		\[  \left|\Norm_{\mathbb{Q}(\omega)/\mathbb{Q}}(1+\omega^i-\omega^j) \right|
			= \prod_{\gcd(m,k)=1, 1\le m\le k} |1+\omega^{mi}-\omega^{mj}| \le 3^k. \]
	\end{sol}
\end{problem}
