# Gracious Living

Ideals: Numbers But Better
March 8, 2011, 14:27
Filed under: Algebra, Math | Tags: , , ,

I left you with a bit of a teaser.  We’d defined rings, integral domains, and fields, and even seen a few examples, but in such a short exposition, there wasn’t very much time to give you the tools to work with them.  There turn out to be ideas that make better sense in a ring, like primality and divisibility.  But to understand them, we need to develop a little machinery, which in this case is the theory of ideals.  As I show below, ideals are like better-behaved numbers, and help us understand the structure of, among other things, the integers.

Modern commutative algebra essentially arose in the early 19th century, under the guidance of mathematicians like Dedekind and Abel.  As you’re probably aware, in $\mathbb{Z}$, every number has a unique factorization into primes, up to sign (and if you’re not aware of it, a prime is a number with no factors but itself and $1$, like $2,3,5,7,\dotsc$ but not $4=2\cdot 2, 6=2\cdot 3,\dotsc$).  The proof is really not hard: if a number is a prime, then we’re done, and if it’s not, then it has other factors, and we use induction to factorize each of them into primes; then if we have two different factorizations, we can divide through by one of them to get a prime factorization for $1$, and it’s easy to see that the only such factorization is the trivial one.

The surprise is that such a theorem doesn’t always hold, even in familiar rings.  One example is the ring $\{a+b\sqrt{-5}:a,b\in\mathbb{Z}\}$, which we’ll call $\mathbb{Z}[sqrt{-5}]$.  We now have

$\displaystyle 6=2\cdot 3=(1+\sqrt{-5})(1-\sqrt{-5})$

and it’s possible to show that all four of these numbers are primes in $\mathbb{Z}[\sqrt{-5}]$.

Dedekind arrived at a resolution by realizing that unique prime factorization exists if we suitably abstract our definition of “number.” Now, I held off on showing you this because it’s actually related to the method of Dedekind cuts described in the last post, and seeing that in a relatively intuitive setting can be very helpful in the more unintuitive one here.  I don’t actually know if Dedekind was aware of the relationship between the two.

To be perfectly rigorous, we’ll define the divisibility relation in a ring $R$ as follows: $a|b$ if there is a $r\in R$ with $ra=b$.  (Worst notation ever: it is symmetrical for an asymmetric relation, and looks like the letter l or number $1$ if you’re sloppy.)  So in a field, everything is divisible by everything nonzero, for example.  It should be easy to see that this is a partial order.  We then define the principal ideal generated by $a$ to be the set $(a)=\{b:a|b\}$.  A lot of properties of ring elements are expressed in their ideals.  For example, in $\mathbb{Z}$, $p$ is prime iff $xy\in(p)\Rightarrow x\in(p)$ or $y\in(p)$: if any multiple of $p$ has factors, then at least one of the factors is a multiple of $p$.

But divisibility has some other properties.  If $a|b$ and $a|c$, then $a|(b+c)$.  If $a|b$ and $c\in R$ is arbitrary, then $a|cb$.  We now define an ideal to be any subset $I$ of $R$ such that $a,b\in I$ implies $(a+b)\in I$, and $a\in I,r\in R$ implies $ra\in I$.  If you think about it, ideals are very nearly the Dedekind cuts of $R$, under the divisibility relation!  “Ideal” originally stood for “ideal number,” because they generalize the “numbers” in $R$ in the same way that the reals generalize the rationals.  (Though note that $R$ doesn’t really embed into its set of ideals: if $a|b$ and $b|a$, then $(a)=(b)$.  If $R$ is an integral domain, we have $a=ub$ where $u$ is a unit, an element with a multiplicative inverse, like $\pm 1$ in $\mathbb{Z}$.)

In particular, we can operate on ideals like we do on numbers.  The sum of two ideals, $I+J$, is just the set $\{i+j:i\in I,j\in J\}$.  This is clearly an ideal, and moreover, it’s the smallest ideal containing both $I$ and $J$ — their least upper bound under the inclusion relation.  The greatest lower bound, meanwhile, is just the intersection $I\cap J$.  But we can also take the product $IJ$ — in order for this to be an ideal, we need to define it as $\left\{\sum_{n=1}^N i_nj_n:i_n\in I,j_n\in J,N\in\mathbb{N}\right\}$.  You should check that all of these operations give ideals, and that $IJ\subseteq I\cap J$ for all $I,J$.  Sadly, sum isn’t a group operation, but we do have a semiring in the sense that product is associative and distributes over sum (and is commutative if $R$ is).  But we are able to write generators for non-principal ideals: define $(a_1,\dotsc,a_n)=(a_1)+\dotsb+(a_n)$, the set of “linear combinations” of the $a_i$.

So if ideals are idealized numbers, and we can idealize their sum and product like the above, we can also idealize primeness.  We define $I$ to be a prime ideal if it’s not the whole ring, and if whenever $xy\in I$, then $x\in I$ or $y\in I$.

And the beautiful thing is: in $\mathbb{Z}[\sqrt{-5}]$, though numbers don’t factorize uniquely into primes, ideals factorize uniquely into prime ideals.  We have

$\displaystyle (6)=(2)(3)=(2,1+\sqrt{-5})^2(3,2+\sqrt{-5})(3,1+\sqrt{-5})=(1+\sqrt{-5})(1-\sqrt{-5}).$

And using a little more machinery, we’ll be able to show that all of the ideals in the middle are, in fact, prime.

I’ll conclude with an exploration of these ideas in the integers.  The integers are an integral domain, but they’re even nicer than most integral domains!  This is because of the following great and simple theorem:

• Theorem (Division algorithm for the integers).  For any $a,b\in\mathbb{Z}$ with $b\ne 0$, there exist a unique $q,r\in\mathbb{Z}$ with $0\le r and $a=bq+r$.

So essentially, there’s a unique way to divide integers with remainder.  The proof is an easy induction, and is left to you.  (Euclid was the first to record this theorem; the $q$ is for “quotient” and $r$ for “remainder.”)  In general, we define a Euclidean domain to be an integral domain $R$ with a Euclidean function $d:R-\{0\}\rightarrow\mathbb{N}$, such that for all $a,b\in R$ with $b\ne 0$, we have $q,r\in R$ with $a=bq+r$ and either $r=0$ or $d(r).  In the integers, the absolute value is such a function (though there are others).

What makes this nice is the following.  Define the greatest common divisor or gcd of $a,b\in R$ to be an element $c\in R$ that divides $a$ and $b$ and is a multiple of anything that divides them both.  (Likewise, define the least common multiple or lcm to be an element that is divisible by both but divides everything else that’s divisible by both.)  These may not exist and aren’t uniquely defined; even in an integral domain, they’re only defined up to multiplication by a unit.  They do generalize the familiar notions of gcd and lcm in $\mathbb{Z}$, though.  We now have:

• Theorem (Euclidean algorithm/Bézout’s identity).  In a Euclidean domain $R$, for any $a,b\in R$, there are $x,y\in R$ with $ax+by=\text{gcd}(a,b)$.

Proof.  As the name suggests, Euclid actually invented an algorithm to find the gcd, and a slight extension lets you get the identity.  It’s a pretty cool trick for hand math.  The division algorithm gives

$\displaystyle a=bq_0+r_0$.

If $r_0=0$, then $b|a$, so $b=\text{gcd}(a,b)$.  If it’s not zero, we basically repeat the process until it becomes zero.

$\displaystyle b=r_0q_1+r_1$

$\displaystyle r_0=r_1q_2+r_2$

$\displaystyle \vdots$

If $d$ is our Euclidean function, then $d(r_i)$ is strictly decreasing until some $r_i$ is zero, say $r_{n-1}=r_nq_{n+1}$.  I claim that $r_n$ is the gcd.  Working back through the steps of the algorithm, we have

$r_{n-2}=r_{n-1}q_n+r_n=r_n(q_{n+1}q_n+1)$

$r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}=r_n(q_{n+1}q_nq_{n-1}+q_{n-1}+q_{n+1})$

$\vdots$

And eventually, we have $b$ and $a$ as multiples of $r_n$.  But on the other hand:

$r_n=r_{n-2}-r_{n-1}q_n$

$r_n=(r_{n-4}-r_{n-3}q_{n-2})-(r_{n-3}-r_{n-2}q_{n-1})q_n$

$\vdots$

We continue substituting later remainders for earlier ones, and end with $r_n=ax+by$, the statement of Bézout’s identity.  This finally proves that $r_n=\text{gcd}(a,b)$: if $c|a,b$, then $c|ax+by=r_n$, as desired.  $\square$

(All right, let’s do an example: for $a=54, b=42$, we have

$54=42\cdot 1+12$

$42=12\cdot 3+6$

$12=6\cdot 2$

so $6$ is the gcd, and working backwards gives

$6=42-12\cdot 3$

$6=42-(54-42)\cdot 3$

$6=54\cdot (-3)+42\cdot 4$

which should give you some idea of how this works in practice.)

Here’s where I’m going with this: by induction, we can find gcds of arbitrary finite sets of elements of a Euclidean domain.  So if $I=(a_1,\dotsc,a_n)$ in a Euclidean domain, and the gcd of the $a_i$ is $b$, then $a_i\in (b)$ for all $i$, since it divides all of them; but at the same time, $b\in I$ because of Bézout’s identity expressing $b$ as a linear combination of the $a_i$.  Thus, every ideal is of the form $(b)$!  We call a domain in which this holds a principal ideal domain or PID.  We have just shown:

• Corollary. Every Euclidean domain is a principal ideal domain.

In the integers, this means that the only ideals are those of the form $(n)$.  Note that $(-n)=(n)$, so we might as well take $n$ to be nonnegative.  A little thought gives us the following easy formulas for working with ideals: $(m)+(n)=(\text{gcd}(m,n)),(m)\cap (n)=(\text{lcm}(m,n)),(m)(n)=(mn)$.  $n$ generates a prime ideal iff for every $xy$ divisible by $n$, either $x$ or $y$ is divisible by $n$.  In particular, this means the only factors $n$ has are itself and units, so $n$ is zero or a prime number.  So the only prime ideals are $0$ and $(p)$ for $p$ prime.

Two other ideals are of special note: $(0)=\{0\}$, called the zero ideal, and $(1)=\mathbb{Z}$, called the unit ideal.  In any ring, the zero ideal is just $\{0\}$ and the unit ideal is the whole ring — moreover, the unit ideal is the only one containing the ring’s units.  These are the largest and smallest possible ideals.  We say that an ideal is maximal if it’s not $(1)$ but $(1)$ is the only ideal containing it.  In the integers, it’s clear that if $m|n$, then $(m)\supseteq (n)$.  Thus, the maximal ideals are those generated by numbers without factors — but these are just the prime ideals!  As we’ll see later, maximal ideals are prime in every ring, though the converse doesn’t always hold.

This concludes the “number-theoretic” approach to ideal theory, and hopefully a nice introduction to very basic number theory.  The other approach is the “ring-theoretic” one, which I’ll do next: we’ll show why ideals in rings are like normal subgroups in groups.