Failure of Unique Prime Factorization

In an earlier entry I discussed Unique Prime Factorization and the ancient Greeks. Some systems very similar to the integers have unique prime factorization while others do not. Let's look at some of those systems.

Consider the Gaussian integers, normally denoted Z[i]. Z[i] is the set of all complex numbers of the form a+bi where a and b are integers and is the square root of negative one. It is not that hard to see that Z[i] is closed under both addition and multiplication. That is, if I take two elements in Z[i] and take their product or sum then the result is also in Z[i]. Furthermore, every element in Z[i] has an additive inverse, that is a number to which I can add to it to get 0. For any a+bi this is just -a-bi. Multiplication and addition are both associative and commutative, and multiplication distributes over addition. Thus, Z[i] is very similar to Z, the set of integers. Sets which satisfy these properties are called rings and are generally symbolized with bold letters. It turns out that rings are the natural setting to look for unique prime factorization.

At first glance, it might seem that the Gaussian integers do not have unique prime factorization. For example, (1+2i)(1-2i)=5=(2-i)(2+i). However, this can be easily corrected. What we have done is something sneaky called multiplying by a unit. In the integers we can do this also. (-3)(-5)=3*5. This isn't because unique prime factorization breaks down. We can always multiply terms by some product of numbers that equal 1. In the case in Z, we used -1 and -1. In the case with (1+2i)(1-2i) we used i and -i. Numbers in a ring which divide 1 are called units. Thus, for example if we were in R, the set of real numbers, every non-zero number is a unit since for any x, we can multiply it by 1/x to get 1. In the integers, the only units are 1 and -1. It turns out that the Gaussian integers have a total of 4 units, -1,1, i and -i. Factorization in the Gaussian integers is unique up to multiplication by units just as factorization in the integers is unique up to multiplication by units.

In the early part of the 19th century it was taken for granted that all well-behaved rings had unique prime factorization. However, this turns out to be false. The standard counterexample is A, the set of numbers of the form a+bk where k is the square root of -5. Like the Gaussian integers, A forms a ring. Unlike the Gaussian integers, A does not have unique prime factorization. We have 2*3=6 and (1+k)(1-k)=1-k+k+k^2=1+5=6. 2,3, 1+k and 1-k cannot be broken down further in any useful way. Thus unique prime factorization fails. The failure of unique prime factorization turns out to be deeply linked with a number of serious issues. In particular, the lack of unique prime factorization in general rings was the major reason that mathematicians in the 19th century were unable to prove Fermat's Last Theorem.

Although A is the standard example of unique prime factorization failing, it isn't a very satisfying example. It isn't clear why unique prime factorization is failing and it isn't clear that if one were looking for an example ring where unique prime factorization fails that one would construct A. There is a slightly more abstract ring that does the job a bit better. Consider the ring B = R[a,b,c,d]/(ab-cd). What we mean by this ring is to take all the products and sums of four formal symbols, a,b,c,d and all real numbers. Thus we would have for example 2a+b as an element. By /(ab-cd) we mean to treat ab-cd as zero. Thus, we do arithmetic formally on this set of four symbols, but we may whenever we see ab or cd replace it by the other. Now, this set is a ring. And it clearly fails at unique prime factorization. Just look at ab and cd. They are different prime factorizations for ab. Unlike with A, there's no difficulty involved in showing that the numbers in question are somehow genuinely behaving like primes. It is immediately obvious from the construction that there is no way of representing a,b,c, or d as an interesting product of terms.

It isn't clear to me why this example isn't used more often. Although it is more abstract than A, the failure of unique factorization is much clearer.