## Failure of unique factorization

For previous posts in this series, see here.

In this installment we’re going to look at a detailed example and discuss some fine points of factorization of algebraic integers. This will be a bit long and pedantic. However, all the reasoning is elementary, except for a small amount of Galois theory, which you can review here.

Let’s look at an example where unique factorization fails. First, we need to introduce a concept that makes it easy to prove some results about factorization (and has many more applications as well). Suppose we have an algebraic number α∈F and F⊇ℚ is a Galois extension. (Such an extension always exists: it is a splitting field of an irreducible polynomial f(x) such that f(α)=0, but we don’t necessarily assume F is the smallest such extension.) Let G=G(F/ℚ) be the Galois group.

To review a concept, which has been introduced before, we define the norm of α with respect to the extension F⊇ℚ to be the product of all numbers σ(α) as σ ranges over elements of G. (More generally, the norm works also for Galois extensions of base fields that contain ℚ.) Symbolically, the norm is:

NF/ℚ(α) = ∏σ∈G σ(α)

Note that “the” norm depends on the specific extension F/ℚ, and so the extension is indicated in the subscript.

For instance, let F=ℚ(√-5). F/ℚ is Galois, because it is the splitting field of the irreducible polynomial f(x) = x2+5 = 0. Any α∈F can be written as a+b√-5 for a,b∈ℚ. An element σ∈G can be specified by how it acts on a typical such element. Of course, since [F:ℚ]=2, G has only two elements: 1 (the identity) and σ, so σ is determined by how it acts on √-5. σ(√-5) has to be a root of f(x)=0 different from √-5, so it must be -√-5. It follows that σ(a+b√-5)=a-b√-5 for a,b∈ℚ, because σ is a field automorphism of F that leaves all elements of ℚ fixed. This should remind you of complex conjugation, because that is in fact the nontrivial automorphism of the group G(ℚ(i)/ℚ).

In the simple case at hand, we can give a simple formula for the norm:

NF/ℚ(a+b√-5) = (a+b√-5)(a-b√-5) = a2 + 5b2

(In the field ℚ(i), the norm of a complex number is the square of the modulus, i. e. |a+bi|2 = a2 + b2, so norm in the sense used here is closely related to the complex “norm”.)

The norm symbol has some fairly obvious properties. From the way it is defined as a product, the norm is a group homomorphism from the multiplicative group of F to the multiplicative group of ℚ. It is also a homomorphism of the multiplicative semigroups of the rings of integers OF and ℤ, which means that the value of the norm of an algebraic integer is always an integer in the base field (in this case the integers ℤ of ℚ). This is because each σ∈G is a field automorphism which satisfies σ(αβ)=σ(α)σ(β) for all α,β∈F. In other words,

NF/ℚ(αβ) = NF/ℚ(α) NF/ℚ(β)

Furthermore, NF/ℚ(ε)=±1 if and only if ε is an invertible element of OF, i. e. a unit. (Since ±1 are the units of ℤ.)

Let’s first determine the ring of integers OF. Let α=a+b√-5 be a general element of F, with a,b∈ℚ. If in fact α is an algebraic integer, then so is its conjugate α*=a-b√-5. Further, the sum α+α*=2a is in ℚ, and is also an algebraic integer, since the algebraic integers of an extension form a ring. But the only algebraic integers in ℚ are in fact in ℤ, so 2a∈ℤ. Similarly, 2b=(α-α*)/√-5 is an algebraic integer in ℚ, hence an element of ℤ, so 2b∈ℤ. The norm of both α and α* is a2+5b2, which is in ℤ. Multiplying the last expression by 4 shows (2a)2+(2b)25∈4ℤ. Since 5≡1 (mod 4), (2a)2+(2b)2≡0 (mod 4). This is impossible unless both 2a and 2b are even integers (just check the separate cases). Hence both a and b are in ℤ. The conclusion is that OF = {a+b√-5 | a,b∈ℤ}.

A slight elaboration of this argument shows that in any quadratic field ℚ(√d) where d∈ℤ is square-free, algebraic integers have the form OF = {a+b√d | a,b∈ℤ} unless d≡1 (mod 4), in which case OF = {(a+b√d)/2 | a,b∈ℤ, a≡b (mod 2)}. In other words, the naive guess that algebraic integers of ℚ(√d) just have the form a+b√d for a,b∈ℤ isn’t entirely correct, but it is wrong only for d≡1 (mod 4), and then only by a little bit.

At this point, there is one delicate issue of nomenclature we must deal with. You will recall that a prime p∈ℤ is customarily defined as a (nonzero, nonunit) number which has no divisors other than units (±1) and ±p. We also proved that if p has this property, and if p divides a product mn, then either p divides m or p divides n (or maybe it divides both). In ℤ we can use this property to define p as a prime, since if the property is true of p then the more familiar condition that p has no nontrivial divisors is also true. This is because if p has this property, then the only divisors of p can be ±1 and ±p. (This follows from order properties of ℤ, because all divisors of a number n, except for ±n, have absolute values less than |n|.)

So these two properties of a nonzero p∈ℤ are equivalent. However, as we are about to see, the properties are not equivalent in other rings of integers. Nevertheless, we will find it convenient to use a generalization of the definition that p is prime if and only if p|mn implies p|m or p|m. So we will need a new term for the property of nonzero p that it is not a unit and not divisible by any other number except a unit times p. For this property we will use the term irreducible (like an irreducible polynomial). (And when this is the case, we say that p has only “trivial” factors, hence a nonunit p is defined to be irreducible if and only if all its factors are trivial, or equivalently if and only if it has no nontrivial factors.) We will make a similar distinction of “prime” and “irreducible” for integers α of other rings of integers.

Finally we can get back to factorization in F=ℚ(√-5). Observe that 21=3⋅7=(1+2√-5)(1-2√-5). We claim, first, that both 3 and 7 are irreducible in OF. Consider 3 first. If α=a+b√-5 were a nontrivial integral divisor of 3 – i. e. neither α nor 3/α is a unit – then we would have NF/ℚ(α) = a2+5b2 divides NF/ℚ(3) = 9. (Note, by the way, that for this extension, the norm is always nonnegative.) So NF/ℚ(α) must be either 3 or 9, since α isn’t a unit. Obviously the equation a2+5b2=3 has no solutions for a,b∈ℤ. So NF/ℚ(α) isn’t 3, hence it must be 9. Then NF/ℚ(3/α)=1, and 3/α is a unit, contrary to assumption. So 3 is irreducible. 7 is also irreducible, by a similar argument. The same kind of argument shows that 1±2√-5 must be irreducible, since both conjugates have norm 21, and any non-unit α that divided either would have a norm equal to 3 or 7, which we just observed is impossible. And we cannot have 1±2√-5 dividing either 3 or 7 (or vice versa), since 21∤9 and 21∤49.

What we’ve just shown is that 21 has two factorizations into irreducible numbers of Oℚ(√-5), and the factorizations are not equivalent, since the irreducible numbers in one factorization aren’t unit multiples of either irreducible number in the other factorization. This shows that factorization of elements of the ring Oℚ(√-5) into irreducible numbers isn’t unique.

This example shows that a number which has no non-trivial factors (e. g. 3 or 7) can divide a product (e. g. 21) of two other numbers (e. g. 1±2√-5) without dividing either one of the factors of the product. So an irreducible number is not “prime” in the sense that if it divides a product, it must divide at least one of the factors. This latter property is actually more useful in practice, so we want to use the term “prime” for it. Therefore, a distinction is made in a general ring of integers: a (nonzero, nonunit) number which has no non-trivial factors is said to be irreducible. (Equivalently, if α=βγ then either β or γ must be a unit.) On the other hand, the term prime is reserved for (nonzero, nonunit) numbers α which have the property α|βγ implies α|β or α|γ.

Now, in any ring of integers of an algebraic number field, a prime integer (in the new sense) must also be irreducible. This is because if α is not irreducible, then by definition we can write α=βγ, where neither factor is a unit. But if α is prime it must divide one of its factors. Say α divides β. Then β=αδ. Hence 1=δγ. That is, γ is a unit, contrary to assumption, and so α has only trivial factors, so it’s irreducible. Thus the set of prime integers is a subset of the set of irreducible integers.

However, in the example we just examined where F=ℚ(√-5), where we do not have unique factorization, then some irreducible numbers are not prime. E. g. 1+2√-5 is irreducible (as we showed), but it is not prime, because it divides 21, but does not divide either 3 or 7. Therefore it’s possible for the set of prime integers to be a proper subset of the set of irreducible integers, i. e. a strictly smaller subset.

This raises some interesting questions. Recall that the cases we are interested in are the rings of algebraic numbers. By definition, these are the rings of integers A=OF of a finite extension F/ℚ.

In any such A, it is always true that we can write any element as a product of a finite number of irreducible integers. The reason is that for any (nonzero, nonunit) α∈A, if α isn’t irreducible, we can write α=βγ, where neither factor is 0 or a unit. Since F/ℚ is a finite extension, we can always compute norms, and we have NF/ℚ(α) = NF/ℚ(β)NF/ℚ(γ). In some extensions a norm can be negative, but we can also stick in the absolute values of each term, and since no term is ±1, each factor on the right hand side is an an integer in ℤ that is strictly smaller in absolute value than |NF/ℚ(α)|. Since all numbers here are finite, this process can’t continue indefinitely. So not only do we get a finite product of irreducible integers, but we in fact get a finite product of finite powers of distinct irreducible integers. However, as the example above showed, this factorization need not be unique.

On the other hand, we can also say that if some algebraic integer α can be expressed as a product of powers of distinct prime integers, then (up to order and unit factors), the expression is unique as to which primes occur in the factorization and the powers of each that occur. To prove this, note first that any prime π which appears in one factorization into powers of primes must appear in the other. Because since π is in one factorization, it divides α, and because it is prime, it must divide at least one factor in any other factorization into powers of distinct primes. That factor must then be a power of π, since π can’t divide a power of a different prime (using the fact that all primes are irreducible). Furthermore, if π occurs at all in some factorization of α, it must occur to eactly the same power in each factorization. Otherwise if the smaller power has exponent n, then we could cancel πn from both factorizations. That would leave the integer α/πn with distinct prime power factorizations, one containing π and the other not, which we just ruled out.

The problem here is that we do not know that every integer α∈A actually has even one factorization into distinct primes. Consequently, if there can be irreducible integers of A that aren’t prime, so the set of prime integers is a proper subset of the set of irreducible integers, we cannot be sure that there is the kind of unique factorization theorem for integers of A that we have for ℤ, regardless of whether we specify “primes” or “irreducibles”. Factorizations into irreducibles can’t be guaranteed to be unique, while factorizations into only powers of primes might not even exist.

However, if the set of primes is the same as the set of irreducibles, then factorizations of any integer of A into irreducibles, and hence primes, are guaranteed to exist, And furthermore, the factorizations must also be unique.

What about converses? Suppose we can guarantee that factorizations of any α∈A into primes must exist. Does that imply prime = irreducible? Yes, for the following simple reason. We have already shown that if a factorization into primes exists, it must be unique. So suppose α is irreducible. If a factorization into primes must exist, then α=πβ for some prime π. But because α is irreducible, β has to be a unit. Any prime times a unit is still a prime, so α itself is a prime, and the set of irreducible elements contains only primes.

Or suppose we can guarantee that factorizations of any α∈A into irreducibles are unique. Does that imply prime = irreducible? Again the answer is yes. For suppose α is irreducible and that for some β and γ we have α|βγ. Since α|βγ there is a δ such that αδ = βγ. Write the right and left hand sides as a product of powers of distinct irreducible numbers, so that (ignoring possible factors which are units) αδ1⋅⋅⋅δm = β1⋅⋅⋅βn (except that if α is among the δi, combine the terms). Then by the assumed uniqueness αk = βj for some j and some power k≥1, and both sides are powers of the same irreducible number α. That number must have been a divisor of either β or γ (or both). In any case, this means α is prime.

What we have now proven is this: If A=OF is the ring of integers of a finite extension F/ℚ, the following conditions are equivalent:

1. The set of irreducible elements of A is the same as the set of prime elements of A (up to unit factors).
2. Every element of A has a unique factorization into powers of irreducible elements (up to unit factors).
3. Every element of A has a unique factorization into powers of prime elements (up to unit factors).

So (as is obvious) if all irreducible elements are prime, the difference in how these are defined is irrelevant. However, if there are irreducible elements that aren’t prime, then factorizations of some integers into powers of irreducibles will not be unique, and some integers will not even have a factorization into powers of primes.

It turns out that there are certain types of rings in which all irreducible elements are prime, so the two concepts are equivalent in such rings. ℤ is one example of such a ring, but it is not the only one. Certainly, if we could guarantee that the integers of some extension of ℚ always had some factorization into primes (in the special sense used here), then as we showed, the factorizations must be unique. In order to investigate this issue further, we need help from the theory of ideals of rings of integers. By placing certain conditions on the types of ideals that the ring can have, we will be able to guarantee that any irreducible integer is prime, so that factorizations of any integers into irreducibles (which always exist) are also factorizations into primes, and therefore that they are unique.

One important type of ring that has this property is called a principal ideal domain, which means that every ideal consists of elements that are multiples of a single element (that isn’t a unit) by some element of the ring. This is in fact the case with ℤ, where all ideals are of the form nℤ for some n. (The ideal is the full ring ℤ itself if n=±1.) But there are other rings of integers that are also principal ideal domaings, and a large part of algebraic number theory is about identifying which rings have this property. We’ll look into this in much more detail, but first we need to explain further why we care about unique factorization.