Unique and nonunique factorization

It's easier to study algebraic numbers as part of a larger structure than on their own. So we define a number field to be the smallest set containing $\mathbb{Q}$ plus some finite set $\alpha_1, \dots, \alpha_n$ of algebraic numbers, which is also closed under addition, subtraction, multiplication and division. We'll usually denote this number field $\mathbb{Q}(\alpha_1, \dots, \alpha_n)$. We define a ring of integers to be the set of algebraic integers in a number field. WARNING: it's not always obvious what the ring of integers in a number field is. Take the example $\mathbb{Q}(\sqrt{D})$ ($D$ positive or negative). If $D \equiv 1 \pmod{4}$, then $(1 + \sqrt{-D})/2$ is an algebraic integer; more generally, the integers in the number field are $(a + b\sqrt{-D})/2$ for $a,b$ rational integers of the same parity. If $D \equiv 2, 3 \pmod{4}$, then the only integers in the number field are the obvious ones $a + b \sqrt{-D}$ for $a,b$ rational integers. One nice property about the rational integers is unique factorization. Is unique factorization true for other rings of integers? Sometimes yes, sometimes no. To make that precise, we'll need some more definitions. define a unit to be an algebraic integer whose reciprocal is also an algebraic integer. (For example, roots of unity are units, but there are other units too; we'll see some later.) We call an element $\alpha$ of a ring of integers irreducible if whenever you write $\alpha = \beta \gamma$ as the product of two elements of the ring, one of $\beta$ or $\gamma$ is a unit. (I didn't say ``prime'' because I'm saving that word for later). We say a ring of integers has unique factorization if whenever an element of a ring of integers is expressed as a product of irreducible elements, that expression is unique up to changing the order and multiplying by units. For example, the Gaussian integers have unique factorization, because they admit an analogue of the Euclidean division algorithm.

Theorem 2   Given Gaussian integers $p$ and $q$ with $q \neq 0$, there exist Gaussian integers $r$ and $s$ with $p = qr+s$ and $\vert s\vert < \vert q\vert$.

Proof. Draw the square with vertices $0, q, iq, (1+i)q$. Then $p$ is congruent to a Gaussian integer $z$ inside (or on the boundary of) the square. Also, the open discs of radius $\vert q\vert$ centered at $0, q, iq, (1+i)q$ cover the square completely, so $z$ is within $\vert q\vert$ of one corner of the square, say $w$. Now take $s=z-w$; then $\vert s\vert < \vert q\vert$ and $s \equiv p \pmod{q}$, so we can set $r = (p-s)/q$ and we're done. $\qedsymbol$

Corollary 1   Every (rational) prime congruent to 1 modulo 4 is the sum of two squares; moreover, this expression is unique up to order and signs.

Proof. If $p \equiv 1 \pmod{4}$, then there exist $x$ and $y$ such that $x^2+y^2$ is divisible by $p$ but not by $p^2$. Apply the Euclidean algorithm in the Gaussian integers (left for you to write down!) to $x+iy$ and $p$; the result will be a Gaussian integer $r+si$ with $r^2+s^2=p$. Uniqueness is also left to you. $\qedsymbol$

EXERCISE: Find some other rings of integers which have unique factorization. (For starters, try $\mathbb{Z}[\sqrt{-2}]$ and $\mathbb{Z}[(1+\sqrt{-3})/2]$. On the other hand, consider this example in $\mathbb{Z}[\sqrt{-5}]$:

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

None of 2, 3, or $1 \pm \sqrt{-5}$ can be written as a nontrivial product of two elements of $\mathbb{Z}[\sqrt{-5}]$, so this ring doesn't have unique factorization. What to do? Kummer realized that one could find an algebraic integer in a bigger ring that would allow you to break up such problem factorizations. (For example, if we toss in $\sqrt{2}$, then it divides both $1+\sqrt{-5}$ and $2$.) However, it turns out that it's a little better to work not with these ``ideal numbers'', as Kummer called them, but with the collection of their multiples. Definition: an ideal in a ring of integers $R$ is a subset $S$ such that

1. for $x,y \in S$, $x+y \in S$;
2. if $x \in S$ and $r \in r$, then $xr \in S$.

Example: If $R = \mathbb{Z}$, then an ideal is an arithmetic progression containing 0. More general example: the principal ideal generated by $r \in R$ consists of all multiples of $r$. But not all ideals have this form! Because of the way an ideal is defined, we can work ``modulo'' an ideal, that is, it makes sense to write $a \equiv b \pmod{I}$ because this equivalence respects addition and multiplication. If $I$ is nonzero, then the number of equivalence classes modulo $I$ is finite; we call this number the norm of the ideal. An ideal $I$ is prime if $xy \in I$ implies $x \in I$ or $y \in I$. For example, if $R = \mathbb{Z}$ and $I = (n)$, then $I$ is prime if and only if $n$ is prime. In general, if $I$ has prime norm, it is a prime ideal, but the converse is not true; we only know that $I$ has prime power norm. For example, the ideal $(3)$ in $\mathbb{Z}[i]$ is prime, but its norm is 9. The arithmetic on $\mathbb{Z}[i]/(3)$ is not the same as on $\mathbb{Z}/(9)$, though! The main distinction is that in $\mathbb{Z}[i]/(3)$, everything not congruent to 0 mod $(3)$ has a multiplicative inverse. (Thus $\mathbb{Z}[i]/(3)$ is an example of a finite field.) The big theorem about prime ideals is the recovery of unique factorization.

Theorem 3   Every nonzero ideal in a ring of integers has a unique prime factorization.

Corollary 2   If every ideal of a ring of integers $R$ is principal, then $R$ has unique factorization. (Note: the converse is also true.)

Two ideals $I$ and $J$ in the ring of integers $R$ of a number field $K$ are equivalent if there exists $k \in K$ such that $kI = J$. (Note that $k$ need not lie in $R$. If you prefer a definition within $R$: $I$ and $J$ are equivalent if there exist nonzero $i,j \in R$ such that $iI = jJ$.) This equivalence is respected by multiplication.

Theorem 4 (Minkowski)   The number of equivalence classes of ideals in a ring of integers is finite.

This number is called the class number of the number field.

Theorem 5 (Gauss)   For $n > 3$ not divisible by 4, the number of primitive (having no common factor) triples $(x,y,z)$ of integers such that $x^2+y^2+z^2=n$ is equal to 12 times the class number of $\mathbb{Q}(\sqrt{-n})$ if $n \equiv 1, 2 \pmod{4}$, or 24 times the class number of $\mathbb{Q}(\sqrt{-n})$ if $n \equiv 3 \pmod{4}$.

Note: Gauss didn't express this theorem in terms of number fields, but in terms of binary quadratic forms $ax^2+bxy+cy^2$ whose discriminant $b^2-4ac$ equals $-4n$, if $n \equiv 1, 2 \pmod{4}$, or $-n$, if $n \equiv 3 \pmod{4}$. Two forms are equivalent if you can get from one to the other by making a variable substitution of the form $u = px+qy, v=rx+sy$ where $p,q,r,s$ are integers with $ps-qr=1$. EXERCISE: Prove that the number of equivalence classes of forms equals the class number of $\mathbb{Q}(\sqrt{-n})$.