\chapter{Flavors of rings}
\label{ch:flavors_rings}
We continue our exploration of rings by considering
some nice-ness properties that rings or ideals can satisfy,
which will be valuable later on.
As before, number theory is interlaced as motivation.
I guess I can tell you at the outset what the completed table
is going to look like, so you know what to expect.

\begin{center}
	\begin{tabular}[h]{lll}
		Ring noun & Ideal adjective & Relation \\ \hline
		PID & principal &
			$R$ is a PID $\iff$ $R$ is an integral domain, \\
			&& \qquad and every $I$ is principal \\
		Noetherian ring & finitely generated &
			$R$ is Noetherian $\iff$ every $I$ is fin.\ gen. \\
		field & maximal & $R/I$ is a field $\iff$ $I$ is maximal \\
		integral domain & prime & $R/I$ is an integral domain
			$\iff$ $I$ is prime \\
	\end{tabular}
\end{center}

\section{Fields}
\prototype{$\QQ$ is a field, but $\ZZ$ is not.}

We already saw this definition last chapter:
a field $K$ is a nontrivial ring for which every nonzero element is a unit.

In particular, there are only two ideals in a field:
the ideal $(0)$, which is maximal, and the entire field $K$.

\section{Integral domains}
\prototype{$\ZZ$ is an integral domain.}

In practice, we are often not so lucky that we have a full-fledged field.
Now it would be nice if we could still conclude the zero product property:
if $ab = 0$ then either $a = 0$ or $b = 0$.
If our ring is a field, this is true: if $b \neq 0$,
then we can multiply by $b\inv$ to get $a = 0$.
But many other rings we consider like $\ZZ$ and $\ZZ[x]$ also have this property,
despite not having division.

Not all rings though: in $\Zc{15}$,
\[ 3 \cdot 5 \equiv 0 \pmod{15}. \]
If $a, b \neq 0$ but $ab=0$ then we say $a$ and $b$ are \vocab{zero divisors}
of the ring $R$.
So we give a name to such rings.
\begin{definition}
	A nontrivial ring with no zero divisors
	is called an \vocab{integral domain}.\footnote{Some
		authors abbreviate this to ``domain'', notably Artin.}
\end{definition}
\begin{ques}
	Show that a field is an integral domain.
\end{ques}
\begin{exercise}
	[Cancellation in integral domains]
	Suppose $ac = bc$ in an integral domain, and $c \neq 0$.
	Show that $a = b$.
	(There is no $c\inv$ to multiply by,
	so you have to use the definition.)
\end{exercise}

\begin{example}
	[Examples of integral domains]
	Every field is an integral domain,
	so all the previous examples apply.
	In addition:
	\begin{enumerate}[(a)]
		\ii $\ZZ$ is an integral domain, but it is not a field.
		\ii $\RR[x]$ is not a field,
		since there is no polynomial $P(x)$ with $xP(x) = 1$.
		However, $\RR[x]$ is an integral domain,
		because if $P(x) Q(x) = 0$ then one of $P$ or $Q$ is zero.
		\ii $\ZZ[x]$ is also an example of an integral domain.
		In fact, $R[x]$ is an integral domain for any integral domain $R$ (why?).
		\ii $\Zc n$ is a field (hence integral domain)
		exactly when $n$ is prime.
		When $n$ is not prime, it is a ring but not an integral domain.
	\end{enumerate}
	The trivial ring $0$ is \emph{not} considered an integral domain.
\end{example}

At this point, we go ahead and say:
\begin{definition}
	An integral domain where all ideals are principal
	is called a \vocab{principal ideal domain (PID)}.
\end{definition}

Recall that the ideal $(a, b)$ is the ring-analog of the $\gcd$ operation, so essentially what this
definition is saying is that:
If any family of elements $\{ a_i \}$ is taken, then the ideal generated by all of the $a_i$ is in
fact generated by a single element $a$.

In other words,
\begin{moral}
	In a PID, you can take the $\gcd$ of any collection of elements.
\end{moral}

The ring $\ZZ/6\ZZ$ is an example of a ring
which is a principal ideal ring, but not an integral domain.
As we alluded to earlier, we will never really use ``principal ideal ring''
in any real way: we typically will want to strengthen it to PID.

\section{Prime ideals}
\prototype{$(5)$ is a prime ideal of $\ZZ$.}

We know that every integer can be factored (up to sign)
as a unique product of primes; for example $15 = 3 \cdot 5$
and $-10 = -2 \cdot 5$.
You might remember the proof involves the so-called B\'ezout's lemma,
which essentially says that $(a,b) = (\gcd(a,b))$;
in other words we've carefully used the fact that $\ZZ$ is a PID.

It turns out that for general rings, the situation is not as nice
as factoring elements because most rings are not PID's.
The classic example of something going wrong is
\[ 6 = 2 \cdot 3 = \left( 1-\sqrt{-5} \right)\left( 1+\sqrt{-5} \right) \]
in $\ZZ[\sqrt{-5}]$.
Nonetheless, we can sidestep the issue
and talk about factoring \emph{ideals}:
somehow the example $10 = 2 \cdot 5$ should be $(10) = (2) \cdot (5)$,
which says ``every multiple of $10$ is the product of a
multiple of $2$ and a multiple of $5$''.
I'd have to tell you then how to multiply two ideals, which I do
in the chapter on unique factorization.

Let's at least figure out what primes are.
In $\ZZ$, we have that $p \neq 1$ is prime if whenever $p \mid xy$,
either $p \mid x$ or $p \mid y$.
We port over this definition to our world of ideals.
\begin{definition}
	\label{def:prime_ideal}
	A \emph{proper} ideal $I \subsetneq R$ is a \vocab{prime ideal}
	if whenever $xy \in I$, either $x \in I$ or $y \in I$.
\end{definition}
The condition that $I$ is proper is analogous to the
fact that we don't consider $1$ to be a prime number.

\begin{example}[Examples and non-examples of prime ideals]
	\listhack
	\begin{enumerate}[(a)]
		\ii The ideal $(7)$ of $\ZZ$ is prime.
		\ii The ideal $(8)$ of $\ZZ$ is not prime,
		since $2 \cdot 4 = 8$.

		\ii The ideal $(x)$ of $\ZZ[x]$ is prime.
		\ii The ideal $(x^2)$ of $\ZZ[x]$ is not prime,
		since $x \cdot x = x^2$.

		\ii The ideal $(3,x)$ of $\ZZ[x]$ is prime.
		This is actually easiest to see
		using \Cref{thm:prime_ideal_quotient} below.

		\ii The ideal $(5) = 5\ZZ + 5i\ZZ$ of $\ZZ[i]$
		is not prime, since the elements
		$3+i$ and $3-i$ have product $10 \in (5)$,
		yet neither is itself in $(5)$.
	\end{enumerate}
\end{example}
\begin{remark}
	\label{rem:unit_sign_issue}
	Ideals have the nice property that they get rid of ``sign issues''.
	For example, in $\ZZ$, do we consider $-3$ to be a prime?
	When phrased with ideals, this annoyance goes away: $(-3) = (3)$.
	More generally, for a ring $R$, talking about ideals
	lets us ignore multiplication by a unit.
	(Note that $-1$ is a unit in $\ZZ$.)
\end{remark}

\begin{exercise}
	What do you call a ring $R$ for which the zero ideal $(0)$ is prime?
\end{exercise}

We also have:
\begin{theorem}[Prime ideal $\iff$ quotient is integral domain]
	\label{thm:prime_ideal_quotient}
	An ideal $I$ is prime if and only if $R/I$ is an integral domain.
\end{theorem}
\begin{exercise}
	[Mandatory]
	Convince yourself the theorem is true;
	it is just definition chasing.
	(A possible start is to consider $R = \ZZ$ and $I = (15)$.)
\end{exercise}

I now must regrettably inform you that unique factorization is still
not true even with the notion of a ``prime'' ideal
(though again I haven't told you how to multiply two ideals yet).
But it will become true with some additional assumptions
that will arise in algebraic number theory
(relevant buzzword: Dedekind domain).

\section{Maximal ideals}
\prototype{The ideal $(x,5)$ is maximal in $\ZZ[x]$, by quotient-ing.}

Here's another flavor of an ideal.
\begin{definition}
	A proper ideal $I$ of a ring $R$ is \vocab{maximal} if
	it is not contained in any other proper ideal.
\end{definition}

\begin{example}
	[Examples of maximal ideals]
	\listhack
	\begin{enumerate}[(a)]
		\ii The ideal $I = (7)$ of $\ZZ$ is maximal, because
		if an ideal $J$ contains $7$
		and an element $n$ not in $I$
		it must contain $\gcd(7,n) = 1$, and hence $J = \ZZ$.
		\ii The ideal $(x)$ is \emph{not} maximal in $\ZZ[x]$,
		because it's contained in $(x,5)$ (among others).
		\ii On the other hand, $(x,5)$ is indeed maximal in $\ZZ[x]$.
		This is actually easiest to verify using
		\Cref{thm:max_ideal_quotient} below.
		\ii Also, $(x)$ is maximal in $\CC[x]$,
		again appealing to \Cref{thm:max_ideal_quotient} below.
	\end{enumerate}
\end{example}

\begin{exercise}
	What do you call a ring $R$ for which the zero ideal $(0)$ is maximal?
\end{exercise}

There's an analogous theorem to the one for prime ideals.
\begin{theorem}
	[$I$ maximal $\iff$ $R/I$ field]
	\label{thm:max_ideal_quotient}
	An ideal $I$ is maximal if and only if $R/I$ is a field.
\end{theorem}
\begin{proof}
	A ring is a field if and only if $(0)$ is the only maximal ideal.
	So this follows by \Cref{prob:inclusion_preserving}.
\end{proof}

\begin{corollary}
	[Maximal ideals are prime]
	If $I$ is a maximal ideal of a ring $R$, then $I$ is prime.
\end{corollary}
\begin{proof}
	If $I$ is maximal, then $R/I$ is a field,
	hence an integral domain, so $I$ is prime.
\end{proof}

In practice, because modding out by generated ideals is pretty convenient,
this is a very efficient way to check whether an ideal is maximal.
\begin{example}
	[Modding out in $\ZZ{[x]}$]
	\listhack
	\begin{enumerate}[(a)]
		\ii This instantly implies that $(x,5)$ is a maximal ideal
		in $\ZZ[x]$, because if we mod out by $x$ and $5$ in $\ZZ[x]$,
		we just get $\FF_5$, which is a field.
		\ii On the other hand, modding out by just $x$ gives $\ZZ$,
		which is an integral domain but not a field; that's why $(x)$ is
		prime but not maximal.
	\end{enumerate}
\end{example}

As we saw, any maximal ideal is prime.
But now note that $\ZZ$ has the special property that
all of its nonzero prime ideals are also maximal.
It's with this condition and a few other minor conditions
that you get a so-called \emph{Dedekind domain}
where prime factorization of ideals \emph{does} work.
More on that later.

\section{Field of fractions}
\prototype{$\Frac(\ZZ) = \QQ$.}
As long as we are here, we take the time to introduce a useful
construction that turns any integral domain into a field.

\begin{definition}
	Given an integral domain $R$,
	we define its \vocab{field of fractions} or \vocab{fraction field}
	$\Frac(R)$ as follows:
	it consists of elements $a / b$, where $a,b \in R$ and $b \neq 0$.
	We set $a / b \sim c / d$ if and only if $bc = ad$.
	Addition and multiplication is defined by
	\begin{align*}
		\frac ab + \frac cd &= \frac{ad+bc}{bd} \\
		\frac ab \cdot \frac cd &= \frac{ac}{bd}.
	\end{align*}
\end{definition}
In fact everything you know about $\QQ$ basically carries over by analogy.
You can prove if you want that this indeed a field, but
considering how comfortable we are that $\QQ$ is well-defined,
I wouldn't worry about it\dots

\begin{definition}
	Let $k$ be a field.
	We define $k(x) = \Frac(k[x])$
	(read ``$k$ of $x$''),
	and call it the \vocab{field of rational functions}.
\end{definition}

\begin{example}
	[Examples of fraction fields]
	\listhack
	\begin{enumerate}[(a)]
		\ii By \emph{definition}, $\Frac(\ZZ) = \QQ$.
		\ii The field $\RR(x)$ consists of rational functions in $x$:
		\[ \RR(x) = \left\{ \frac{f(x)}{g(x)} \mid f,g \in \RR[x] \right\}. \]
		For example, $\frac{2x}{x^2-3}$ might be a typical element.
	\end{enumerate}
\end{example}

\begin{example}
	[Gaussian rationals]
	\label{ex:gaussian_rationals}
	Just like we defined $\ZZ[i]$ by abusing notation,
	we can also write $\QQ(i) = \Frac(\ZZ[i])$.
	Officially, it should consist of
	\[ \QQ(i) = \left\{ \frac{f(i)}{g(i)} \mid g(i) \neq 0 \right\} \]
	for polynomials $f$ and $g$ with rational coefficients.
	But since $i^2=-1$ this just leads to
	\[ \QQ(i) = \left\{ \frac{a+bi}{c+di} \mid a,b,c,d \in \QQ,
		(c,d) \neq (0,0) \right\}. \]
	And since $\frac{1}{c+di} = \frac{c-di}{c^2+d^2}$ we end up with
	\[ \QQ(i) = \left\{ a+bi \mid a,b \in \QQ \right\}. \]
\end{example}


\section{Unique factorization domains (UFD's)}
\prototype{$\ZZ$ and polynomial rings in general.}

Here is one stray definition that will be important
for those with a number-theoretic inclination.
Over the positive integers, we have a fundamental theorem of arithmetic,
stating that every integer is uniquely the product of prime numbers.

We can even make an analogous statement in $\ZZ$ or $\ZZ[i]$,
if we allow representations like $6 = (-2)(-3)$ and so on.
The trick is that we only consider everything \emph{up to units};
so $6 = (-2)(-3) = 2 \cdot 3$ are considered the same.

The general definition goes as follows.
\begin{definition}
	A nonzero non-unit of an integral domain $R$ is
	\vocab{irreducible} if it cannot be written as the product of two non-units.

	An integral domain $R$ is a \vocab{unique factorization domain}
	if every nonzero non-unit of $R$ can be written
	as the product of irreducible elements,
	which is unique up to multiplication by units.
\end{definition}
\begin{ques}
	Verify that $\ZZ$ is a UFD.
\end{ques}

\begin{example}
	[Examples of UFD's]
	\listhack
	\begin{enumerate}[(a)]
		\ii Fields are a ``degenerate'' example of UFD's:
		every nonzero element is a unit,
		so there is nothing to check.

		\ii $\ZZ$ is a UFD.
		The irreducible elements are $p$ and $-p$,
		for example $5$ or $-17$.

		\ii $\QQ[x]$ is a UFD:
		polynomials with rational coefficients
		can be uniquely factored, up to scaling by constants
		(as the units of $\QQ[x]$ are just the rational numbers).

		\ii $\ZZ[x]$ is a UFD.

		\ii The Gaussian integers $\ZZ[i]$ turns out to be a UFD too
		(and this will be proved in the chapters on algebraic number theory).

		\ii $\ZZ[\sqrt{-5}]$ is the classic non-example of a UFD:
		one may write
		\[ 6 = 2 \cdot 3 = \left( 1-\sqrt{-5} \right)
			\left( 1+\sqrt{-5} \right) \]
		but each of $2$, $3$, $1 \pm \sqrt{-5}$ is irreducible.
		(It turns out the right way to fix this is
		by considering prime \emph{ideals} instead,
		and this is one big motivation for \Cref{part:algnt1}.)

		%\ii Theorem we won't prove: every PID is a UFD.
		\ii Theorem we won't prove: if $R$ is a UFD,
		so is $R[x]$ (and hence by induction so is
		$R[x,y]$, $R[x,y,z]$, \dots).
	\end{enumerate}
\end{example}

We have the following theorem:
\begin{theorem}
	Let $R$ be a PID. Then $R$ is a UFD.
\end{theorem}

If we look at the non-example above:
\[ 6 = 2 \cdot 3 = \left( 1-\sqrt{-5} \right) \left( 1+\sqrt{-5} \right) \]
The failure of $\ZZ[\sqrt{-5}]$ to be a UFD here is reflected by the fact that we cannot decompose
any factor into further irreducible factor, indeed, the ideal
\[ \left( 2, 1 + \sqrt{-5} \right) \]
is not principal --- there is no element that is the $\gcd$ of $2$ and $1 + \sqrt{-5}$.

In a similar manner, we can prove that a PID is a UFD, assuming a decomposition into irreducible
factors exist.

\section{Extra: Euclidean domains}

This chapter will not be used later on, but it is of historical interest.

Recall that a PID is a ring where you can take the $\gcd$ of any family of elements.

We all know that the most popular algorithm to compute the $\gcd$ of two elements in $\ZZ$ is the
Euclidean algorithm:
\begin{itemize}
	\ii Start with two integers $a$ and $b$.
	\ii If either of $a$ and $b$ is $0$, we're done. The $\gcd$ is the nonzero element.
	\ii Otherwise, assume $|a| \geq |b|$, divide $a$ by $b$ to get some remainder $r$ such that
	$|r| < |b|$, replace $a$ with $r$, and continue the algorithm.
\end{itemize}
This algorithm is very efficient --- it can be proven that the algorithm only takes logarithmically
many steps in the size of $a$ and $b$ --- for instance, if $a$ and $b$ are on the order of
$10^{100}$, at worst $500$ steps are needed.

Naturally, the following questions are raised:
\begin{quote}
	On which rings can we perform the same algorithm?
\end{quote}
We will see that we can in fact do it on several rings! For example, the ring of Gaussian integers
$\ZZ[i]$, the Eisenstein integers $\ZZ[\omega]$, and so on.

If we look at the algorithm description above, what makes the algorithm work?
It's the absolute value $|\cdot|$ which is used to compare the magnitude of two numbers,
and this absolute value satisfies two conditions:
\begin{itemize}
	\ii It outputs nonnegative integer values --- that way, the algorithm will eventually terminate.
	\ii For any two ring elements $a$ and $b$, where $b \neq 0$, there exist some $q$ such that
	$r = a-qb$ has smaller absolute value than $b$.
\end{itemize}
So, naturally, for any ring with a similar integer-valued function, we can perform the algorithm.
We call a function $\Norm \colon R \to \ZZ_{\geq 0}$ that satisfies the two conditions above an
\vocab{Euclidean norm}, and an integral domain $R$ that has a norm a \vocab{Euclidean domain}.

\begin{example}[The ring of Gaussian integers is a Euclidean domain]
	On $\ZZ[i]$, the usual norm
	\[ |a + bi| = a^2 + b^2 \]
	is a Euclidean norm.

	Indeed, for any elements $a$ and $b$ with $b \neq 0$, we can compute the remainder $r$
	by dividing $a$ by $b$, let $q$ be the Gaussian integer that is closest to $\frac{a}{b}$ (that
	is, $|\frac{a}{b}-q|$ is minimized) and let $r = a-b q$, then it can be proven that $|r| < |b|$.

	The proof is done by showing $|\frac{a}{b}-q| < 1$ --- if we look at the lattice of points
	contained in $\ZZ[i]$ embedded in the complex plane,
	then for any value of $\frac{a}{b} \in \CC$, rounding it to the nearest integer will move it by
	at most $\frac{\sqrt 2}{2} < 1$.
	\begin{center}
	\begin{asy}
		size(4cm);
		for(int x=-2; x<=2;++x){
			for(int y=-2; y<=2;++y){
				dot((x, y), blue);
			}
		}
		for(var p: new pair[]{
			(0.3, 0.4),
			(-1.1, 1.6),
			(-1.5, -1.5),
		}){
			dot(p, red);
			draw(p--(round(p.x), round(p.y)), Arrow);
		}
		graph.xaxis(xmin=-2.4, xmax=2.4);
		graph.yaxis(ymin=-2.4, ymax=2.4);
	\end{asy}
	\end{center}
\end{example}
\begin{example}[The ring of Eisenstein integers is a Euclidean domain]
	Similarly, let $\omega = \frac{1 + \sqrt 3 i}{2}$ (that is $\omega^3 = -1$), then $\ZZ[\omega]$ is
	a Euclidean domain with the usual norm
	\[ |a + bi| = a^2 + b^2 \]
	or equivalently
	\[ |a + b\omega| = a^2 + ab + b^2. \]
\end{example}
\begin{example}[The ring {$\ZZ[\sqrt{11}]$} is a Euclidean domain]
	As before. This time, the natural norm\footnote{%
	See \Cref{sec:norms_traces} for the explanation why this norm is the natural one.}
	will be:
	\[
		\Norm_{\QQ(\sqrt{11})/\QQ}(a + b \sqrt{11}) = (a + b \sqrt{11}) (a - b \sqrt{11})
		= a^2 - 11 b^2.
	\]
	Since we need a Euclidean norm, we will take $\Norm(a + b \sqrt{11}) = |a^2 - 11 b^2|.$

	Given two elements $a$ and $b$ in $\ZZ[\sqrt{11}]$ with $b \neq 0$,
	we will try to compute $r$ such that $\Norm(r) < \Norm(b)$ as $r = a - q b$ as before.

	This time around, we cannot draw $\ZZ[\sqrt{11}]$ as a lattice of points --- it is dense in
	$\RR$ --- so, each point $a + b \sqrt{11}$ will be drawn at the coordinate
	$(a + b \sqrt{11}, a - b \sqrt{11})$.

	The set of points with norm $< 1$ will be drawn below.
	\begin{center}
	\begin{asy}
		size(6cm);
		pair pointof(real a, real b){
			return (a+b*sqrt(11), a-b*sqrt(11));
		}
		real threshold=6.5;
		bool valid(real x, real y){
			return -threshold<=x && x<=threshold && -threshold<=y && y<=threshold;
		}
		bool valid(pair p){ return valid(p.x, p.y); }

		for(int a=-8; a<=8;++a){
			for(int b=-2; b<=2;++b){
				var p=pointof(a, b);
				if(valid(p)) dot(p, blue);
			}
		}

		var axisthreshold=threshold+0.2;
		graph.xaxis(xmin=-axisthreshold, xmax=axisthreshold);
		graph.yaxis(ymin=-axisthreshold, ymax=axisthreshold);

		var t=graph.graph(new real(real a){ return 1/a; }, -axisthreshold, -1/axisthreshold);
		var p=red;
		draw(t, p);
		draw(scale(-1)*t, p);
		draw(scale(1, -1)*t, p);
		draw(scale(-1, 1)*t, p);


		real norm(pair p){
			return abs(p.x*p.y);
		}

		pair[] tryround(pair q){
			pair[] l;
			for(int a=-8; a<=8;++a){
				for(int b=-2; b<=2;++b){
					var p=pointof(a, b);
					if(valid(p) && norm(p-q)<1) l.push(p);
				}
			}
			l=sort(l, new bool(pair a, pair b){
				return norm(a-q)<norm(b-q);
			});
			return l;
		}

		for(pair p: new pair[]{
			(-2, 1.4),
			(-1.7, 1.8),
			(3.1, 3.7),
			(4, -5),
		}){
			var l=tryround(p);
			draw(p--l[0], Arrow);
			for(var q: l[1:]){
				draw(p--q, Arrow, p=gray);
			}
			dot(p, red);
		}

		for(int a=-8; a<=8;++a){
			for(int b=-2; b<=2;++b){
				var p=pointof(a, b);
				if(valid(p)) dot(p, blue);
			}
		}
	\end{asy}
	\end{center}

	Instead of a ball (as in imaginary quadratic fields, that is, $\QQ(\sqrt{-d})$ for integer $d$),
	the set of points with norm $1$ forms a hyperbola.

	As such, rounding to the nearest point is not always the best way --- nevertheless, it can be
	proven (by exhaustive case checking, similar to the case of $\ZZ[i]$) that for every value of
	$\frac{a}{b} \in \QQ(\sqrt{11})$, there is some $q \in \ZZ[\sqrt{11}]$ such that
	$\Norm(\frac{a}{b}-q) < 1$. Thus $\Norm$ is a Euclidean norm.
\end{example}

That having said, sometimes the natural norm of a Euclidean domain need not be Euclidean.
$\ZZ[\frac{1 + \sqrt{69}}{2}]$ is the first example.
%DOI 10.1007/BF02567617

\begin{example}[{$\QQ[x]$ is a Euclidean domain}]
	Similarly, in $\QQ[x]$ we can let the norm be the degree of a polynomial --- the polynomial
	division with remainder algorithm will take care of computing the $\gcd$.
\end{example}

Back to the topic of PID. In a Euclidean domain, you can compute the $\gcd$ of any two elements.
What about an infinite family of elements?

Turns out the situation is very nice:
\begin{proposition}
	A Euclidean domain is a PID.
\end{proposition}
Actually, we don't need to provide an explicit algorithm to compute the $\gcd$ of an infinite family
of elements --- of course any such algorithm cannot terminate in a finite amount of time! --- but we
only need to show the $\gcd$ exists, we can cheat our way out.

Note that in the Euclidean algorithm, the norm of the elements \emph{keep decreasing} until one of
the elements become $0$. So, if we're given an arbitrary family of elements, we take the ideal
generated by these elements --- certainly the $\gcd$ is inside that ideal --- and we \emph{take the
nonzero element with the smallest norm}. This is the $\gcd$.

With that intuition in mind, we formalize our proof:
\begin{proof}
	Let $I$ be any ideal. We need to show $I$ is principal.

	Let $a$ be a nonzero element with smallest norm in $I$ --- such an element exists because
	$\ZZ_{\geq 0}$ is well-ordered.
	\begin{ques}
		Show that, for every other element $b \in I$, we have $a \mid b$.
	\end{ques}
	Thus, $I = (a)$, we're done.
\end{proof}


\begin{example}[{The ring $\ZZ[\frac{1 + \sqrt{-19}}{2}]$ is not a Euclidean domain}]
	Let $R = \ZZ[\frac{1 + \sqrt{-19}}{2}]$.

	With the above example in mind, what can we say about this ring?

	This is in fact a principal ideal domain (we will not prove it here), but there is in fact no
	Euclidean norm on this ring.
	% https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-55/issue-12/The-Euclidean-algorithm/bams/1183514381.full
	% universal side divisor
\end{example}

We will prove the above claim. The general plan is:
\begin{itemize}
	\ii Show that the existence of a Euclidean norm implies the existence of something that we
	call a \vocab{universal side divisor}.
	\ii Show that $R$ has no universal side divisor.
	\ii Thus, $R$ cannot have a Euclidean norm.
\end{itemize}

First, look at the examples above of $\ZZ[i]$ and $\ZZ[\omega]$. We see that the units are the
elements with the smallest norm.

So far, nothing useful --- every ring has the unit $1$. Next, we look at the elements with the
next-smallest norm:
\begin{itemize}
	\ii In $\ZZ[i]$, the element $1 + i$ has norm $2$, and is an element with smallest norm that is
	not $0$ or a unit. (The other elements are $\pm 1 \pm i$.)
	\ii In $\ZZ[\omega]$, the units are $\{ \pm 1, \pm \omega, \pm (\omega-1) \}$ with norm $1$. An
	element with next-smallest norm is $1 + \omega$, with norm $3$.
\end{itemize}

Now, in order to proceed with the proof, we have to define a \emph{side divisor}.
Recall that $b$ is a divisor of $a$ if there is some $q$ such that $a = bq$.
We say $b$ is a \vocab{side divisor} (read: ``almost divisor'') of $a$ if there is some $q$ such
that the remainder $a-bq$ is either $0$ or an unit.

\begin{example}
	In $\ZZ[i]$, consider $b = 3 + i$. The set of numbers $a$ for which $b \mid a$ is drawn in red
	below.
	\begin{center}
	\begin{asy}
		size(8cm);
		for(int x=-7; x<=7; ++x)
		for(int y=-7; y<=7; ++y){
			var q=(x+I*y)/(3+I);
			dot((x, y), q==(round(q.x), round(q.y)) ? red: mediumgray);
		}
		graph.xaxis(xmin=-7.4, xmax=7.4, "$x$");
		graph.yaxis(ymin=-7.4, ymax=7.4, "$y$");
	\end{asy}
	\end{center}

	If we add a unit to these values of $a$, we get the set of numbers $a$ for which $b$ is a side
	divisor of $a$, thus give a picture to the concept of ``almost divisor''.

	The points $a$ where $b$ is a side divisor of $a$ is marked in red and blue below.
	\begin{center}
	\begin{asy}
		size(8cm);
		for(int x=-7; x<=7; ++x)
		for(int y=-7; y<=7; ++y){
			var q=(x+I*y)/(3+I);
			var r=(round(q.x), round(q.y));
			dot((x, y), q==r ? red: abs((x+I*y)-r*(3+I))<=1 ? blue: mediumgray);
		}
		graph.xaxis(xmin=-7.9, xmax=7.9, "$x$");
		graph.yaxis(ymin=-7.9, ymax=7.9, "$y$");
	\end{asy}
	\end{center}
\end{example}

Finally, we define a \vocab{universal side divisor} to be a number $b$ such that $b$ is a side
divisor of every element $a \in R$.

\begin{example}
	Drawing a picture similar to the above, in $\ZZ[i]$, then $2 + i$ and $1 + i$ are side divisors.
	\begin{center}
	\begin{asy}
		size(8cm);
		for(int x=-7; x<=7; ++x)
		for(int y=-7; y<=7; ++y){
			var p=x+I*y, q=p/(2+I), r=(round(q.x), round(q.y));
			if(abs(p-r*(2+I))==1){
				dot(p, blue);
				var x=(r*(2+I)).x, y=(r*(2+I)).y;
				if(-7<=x && x<=7 && -7<=y && y<=7){
					draw((r*(2+I))--p, Arrow, DotMargin);
				}
			}
		}
		for(int x=-7; x<=7; ++x)
		for(int y=-7; y<=7; ++y){
			var p=x+I*y, q=p/(2+I), r=(round(q.x), round(q.y));
			if(q==r){
				dot(p, red);
			}
		}
		graph.xaxis(xmin=-7.9, xmax=7.9, "$x$");
		graph.yaxis(ymin=-7.9, ymax=7.9, "$y$");
	\end{asy}
	\end{center}
\end{example}

Now, the connection between the two concepts considered above.
\begin{lemma}
	In a Euclidean domain,
	the smallest-norm nonzero element $b$ that is not a unit is a universal side divisor.
\end{lemma}
\begin{proof}
	Just run the Euclidean algorithm between any number and $b$ for one step, the remainder must be
	$0$ or a unit.
\end{proof}

And finally,
\begin{proposition}
	There is no universal side divisor in $R$.
\end{proposition}
% actually I haven't worked through the proof yet -user202729 % draft solution below - palindrome868
\begin{proof}
All numbers are of the form, $\frac{a}{2} + \frac{b\sqrt{-19}}{2}$ where $a$ and $b$ have the same parity. The absolute value of a complex number, defined as $\frac{a^2}{4} + \frac{19b^2}{4}$, is multiplicative and is greater than $1$ for all numbers in $\mathbb Z [\frac{1+\sqrt{-19}}{2}]$ except for $-1, 0, 1$, which have absolute values of $1, 0, 1$, respectively. Since there are no numbers in the ring with absolute values greater than $0$ and less than $1$, all numbers in the ring with absolute values greater than $1$ do not have multiplicative inverses in the ring. Hence, the only units are $1$ and $-1$.

When we multiply all the elements in the ring by $x$, the distances between pairs of elements in the complex plane multiplies by $|x|$. Initially, the distances between pairs of elements were at least $1$.
\begin{itemize}
\item If $x$ is real and $|x| \geq 2$, then $xR$ doesn't contain any elements of the form $a + \frac{\sqrt{-19}}{2}$, so $x$ is not a universal side divisor.
\item If $x$ is non-real and $|x| \geq 2$, then an element in $xR$ can only be real if it was previously non-real. This means the elements of $xR$ on the real axis have absolute value of at least $2|\frac{1+\sqrt{-19}}{2}| = 2\sqrt{5} \geq 4$. Hence, $x$ is not a side divisor of $2$, so $x$ is not a universal side divisor.
\end{itemize}
Since $R$ does not have a universal side divisor, $R$ is not a Euclidean domain.
\end{proof}

\section{\problemhead}
Not olympiad problems, but again the spirit is very close
to what you might see in an olympiad.

\begin{problem}
	Consider the ring
	\[ \QQ[\sqrt2] = \left\{ a + b\sqrt2 \mid a,b \in \QQ \right\}. \]
	Is it a field?
	\begin{hint}
		Yes.
	\end{hint}
\end{problem}

\begin{problem}
	[Homomorphisms from fields are injective]
	\label{prob:field_hom}
	Let $K$ be a field and $R$ a nontrivial ring.
	Prove that any homomorphism $\psi \colon K \to R$
	is injective.\footnote{Note that $\psi$
		cannot be the zero map for us,
		since we require $\psi(1_K) = 1_R$.
		You sometimes find different statements in the literature.}
	\begin{hint}
		The kernel is an ideal of $K$!
	\end{hint}
\end{problem}

\begin{sproblem}
	[Pre-image of prime ideals]
	\label{prob:prime_preimage}
	Suppose $\phi \colon R \to S$ is a ring homomorphism,
	and $I \subseteq S$ is a prime ideal.
	Prove that $\phi\pre(I)$ is prime as well.
	\begin{hint}
		This is just a definition chase.
	\end{hint}
	\begin{sol}
		Consider $ab \in \phi\pre(I)$,
		meaning $\phi(ab) = \phi(a) \phi(b) \in I$.
		Since $I$ is prime, either $\phi(a) \in I$ or $\phi(b) \in I$.
		In the former case we get $a \in \phi\pre(I)$ as needed;
		the latter case we get $b \in \phi\pre(I)$.
	\end{sol}
\end{sproblem}

\begin{sproblem}
	\onechili
	Let $R$ be an integral domain with finitely many elements.
	Prove that $R$ is a field.
	\label{prob:finite_domain_field}
	\begin{hint}
		Fermat's little theorem type argument;
		cancellation holds in integral domains.
	\end{hint}
	\begin{sol}
		Let $x \in R$ with $x \neq 0$.
		Look at the powers $x$, $x^2$, \dots.
		By pigeonhole, eventually two of them coincide.
		So assume $x^m = x^n$ where $m < n$, or equivalently
		\[ 0  = x \cdot x \cdot \dots \cdot x
			\cdot \left( x^{n-m} - 1 \right). \]
		Since $x \neq 0$, we get $x^{n-m} - 1 = 0$,
		or $x^{n-m} = 1$.
		So $x^{n-m-1}$ is an inverse for $x$.

		This means every nonzero element has an inverse,
		ergo $R$ is a field.
	\end{sol}
\end{sproblem}

\begin{sproblem}
	[Krull's theorem]
	\label{prob:krull_max_ideal}
	Let $R$ be a ring and $J$ a proper ideal.
	\begin{enumerate}[(a)]
		\ii Prove that if $R$ is Noetherian,
		then $J$ is contained in a maximal ideal $I$.
		\ii Use Zorn's lemma (\Cref{ch:zorn})
		to prove the result even if $R$ isn't Noetherian.
	\end{enumerate}
	\begin{hint}
		Just keep on adding in elements to get an ascending chain.
	\end{hint}
	\begin{sol}
		For part (b), look at the poset of \emph{proper} ideals.
		Apply Zorn's lemma (again using a union trick to verify the condition;
		be sure to verify that the union is proper!).
		In part (a) we are given no ascending infinite chains,
		so no need to use Zorn's lemma.
	\end{sol}
\end{sproblem}

\begin{problem}
	[{$\Spec k[x]$}]
	Describe the prime ideals of $\CC[x]$ and $\RR[x]$.
	\begin{hint}
		Use the fact that both are PID's.
	\end{hint}
	\begin{sol}
		The ideal $(0)$ is of course prime in both.
		Also, both rings are PID's.

		For $\CC[x]$ we get a prime ideal $(x-z)$ for each $z \in \CC$.

		For $\RR[x]$ a prime ideal $(x-a)$ for each $a \in \RR$
		and a prime ideal $(x^2 - ax + b)$ for each quadratic
		with two conjugate non-real roots.
	\end{sol}
\end{problem}

\begin{dproblem}
	How many prime ideals of $\ZZ[\sqrt{2017}]$ are \emph{not} maximal ideals?
	\label{prob:dedekind_sample}
	\begin{hint}
		Show that the quotient $\ZZ[\sqrt{2017}]/I$ has finitely many elements
		for any nonzero prime ideal $I$.
		Therefore, the quotient is an integral domain, it is also a field,
		and thus $I$ was a maximal ideal.
	\end{hint}
	\begin{sol}
		Only one; the ideal $(0)$ which is not maximal.
		We contend every other prime ideal is maximal.

		Indeed, let $I$ be any ideal (not necessarily prime),
		and let $a + b \sqrt{2017}$ be a nonzero element of it.
		Then $I$ also contains $(a^2-2017b^2)$.
		That means when taking modulo $I$ we may take modulo the integer
		$n \coloneqq |a^2-2017b^2| \neq 0$.

		So every element in $R$ is equivalent modulo $I$
		to an element of the form $x + y \sqrt{2017}$,
		where $x,y \in \{0, 1, \dots, n-1\}$.
		In other words, the quotient $R/I$ has at most finitely many elements.

		When $I$ is prime, it follows $R/I$ is an integral domain, too.
		An integral domain with finitely many elements must be a field.
		Hence, from $R/I$ being a field, we conclude $I$ is maximal.
	\end{sol}
\end{dproblem}

\begin{problem}
	Let $R$ denote the set of rational numbers $q$ such that,
	when $q$ is written in lowest terms, the denominator is not a multiple of $5$.
	Then $R$ is a ring (under the usual addition and multiplication).
	Classify all the ideals of $R$.
	Which of these ideals are prime / maximal?
	\begin{sol}
		The ideals are $(0)$, $(1) = R$, and $(5^n) = 5^n R$ for each $n \ge 1$.
		The ideal $(0)$ is prime and the ideal $(5)$ is maximal
		(because the quotient $R/(5) \cong \FF_5$ is a field).
	\end{sol}
\end{problem}

\begin{problem}
	Recall from \Cref{prob:akizuki} that a ring $R$ is \vocab{Artinian}
	if it satisfies the \vocab{descending chain condition}:
	there does \emph{not} exist an infinite descending chain of ideals
	$I_1 \supsetneq I_2 \supsetneq I_3 \supsetneq \dots$.
	\begin{enumerate}[(a)]
		\ii Show that if $R$ is Artinian and an integral domain, then it's a field.
		\ii More generally, show that every prime ideal in an Artinian ring is maximal.
	\end{enumerate}
\end{problem}
