Factorization--Unique and Otherwise

## Factorization--Unique and Otherwise

Unique factorization of integers into primes is a fundamental result, and one which goes back to Euclid. The question of to what degree this result generalizes has been one of intense, and continuing, interest in mathematics.

In order to discuss this question, we must make some careful definitions. We let R denote an integral domain.

Definition 1. An element u of R is a unit if it divides 1 (i.e., if there is an element v of R with uv = 1).

Definition 2. An element p of R is prime if p is not a unit, and, whenever p divides a product ab of elements of R, then p divides a or b.

Definition 3. An element s of R is irreducible if s is not a unit, and, whenever ab = s, then a or b is a unit.

Definition 4. Two elements r and r' of R are associates if r' = ur for some unit u.

To see these definitions in the case R = Z, the ordinary integers, the units are 1 and -1, the primes are 2, -2, 3, -3, 5, -5, ..., the irreducibles are the same as the primes, and the primes 2 and -2 are associates, as are 3 and -3, etc.

With these definitions, we can state:

Theorem (The Fundamental Theorem of Arithmetic) Every non-zero integer has an essentially unique factorization into irreducibles.

To be precise, this states that every integer n can be written as a product

n = us1s2···sk
with u a unit and s1, s2, ..., sk irreducibles, and, if in addition
n = vt1t2···tl
with v a unit and t1, t2, ..., tl irreducibles, then k = l, and, after possible rearrangement, s1 and t1 are associates, s2 and t2 are associates, ..., and sk and tk are associates.

Thus, for example, in the integers Z, we have the factorizations 60 = 1·2·5·3·2 = 1·2·2·3·5 = 1·2·2·(-3)·(-5) = 1·(-2)·(-2)·3·5 = (-1)·(-2)·2·3·5 = (-1)·2·(-2)·(-3)·(-5) = ..., but these are all essentially the same.

We wish to investigate the extent to which the Fundamental Theorem of Arithmetic generalizes, and so it is convenient to give a name to the situation when it does.

Definition An integral domain R is a unique factorization domain (UFD) if the conclusion of the Fundamental Theorem of Arithmetic holds for R, i.e., if every non-zero element of R has an essentially unique factorization into irreducibles.

Now we can give an important example of a UFD:

Theorem The ring R = Q[x], i.e., the ring of polynomials in one variable x, with coefficients in the rational numbers Q, is a UFD.

Thus R is the set of all polynomials
R = {a0 + a1x + a2x2 + a3x3 + ... + anxn},
where a0, a1, a2, a3, ... , an are rational numbers, and unique factorization does hold in R..

(In this ring R, the units are the rational numbers, as for any rational number r, r·(1/r) = 1. The irreducibles are those polynomials of positive degree that cannot be factored into products of polynomials of positive degrees in R, for example, the polynomials x, x2 + 1, x2 - 2. The primes are the same as the irreducibles.)

On the other hand, we can modify R to obtain an example S of a ring which is not a UFD, as follows:

Example Let S = Q[x2,x3], i.e.,

S = {a0 + a2x2 + a3x3 + ... + anxn},
where a0, a1, a2, a3, ... , an are rational numbers.

In other words, S consists of all polynomials in R without an x term.

Then unique factorization does not hold is S, as we can see from the following example:

x6 = x2x2x2 = x3x3.

Note that both x2 and x3 are irreducible, as neither can be factored in S, and they are certainly not associates. Thus we have two essentially distinct factorizations of x6. Note also that neither of x2 and x3 is a prime, as x2 divides x3x3 without dividing either factor, and x3 divides x2x4 without dividing either factor. It is a general theorem that in a UFD, primes and irreducibles are the same, while in a non-UFD, every prime is an irreducible, but an irreducible need not be prime.

Now S is a perfectly good ring, but you may object that this example is somehow unnatural, that S was "cooked up" to make unique factorization fail. You may ask if there are any "natural" examples, and the answer is yes. They are provided by rings of integers in quadratic fields. To discuss these we need some explanation first.

Let D be a square-free integer other than 1 . Then Q[sqrt(D)] is the field consisting of all numbers of the form a + b·sqrt(D), where a and b are rational numbers. Note that this is indeed a field.
For addition we have: (a + b·sqrt(D)) + (c + d·sqrt(D)) = (a+c) + (b+d)·sqrt(D).
For multiplication we have: (a + b·sqrt(D)) · (c + d·sqrt(D)) = (ac+bdD) + (ad+bc)·sqrt(D).
For division we have: (a + b·sqrt(D)) / (c + d·sqrt(D)) = ((a + b·sqrt(D)) / (c + d·sqrt(D))) · ((c - d·sqrt(D)) / (c - d·sqrt(D))) = ((ac-bdD)/(c2-d2D) + (bc-adD)/(c2-d2D))sqrt(D).

We now let R = O(sqrt(D)), the ring of algebraic integers in Q[sqrt(D)]. By definition, an algebraic integer in Q[sqrt(D)] is any element of this field which is a root of a monic polynomial with integer coefficients (i.e., a root of some polynomial with the highest power of x having coefficient 1 and all of the other coefficients being ordinary integers). It turns out that:

R = O(sqrt(D)) = {a + b·sqrt(D) with a and b integers} if D leaves a remainder of 2 or 3 when divided by 4, while

R = O(sqrt(D)) = {a + b·sqrt(D) with a and b both integers or both half-integers} if D leaves a remainder of 1 when divided by 4.

If D = -1 (so R is the so-called "Gaussian integers"), then R is a UFD.

On the other hand, if D = -5, then R is not a UFD. Here are two distinct factorizations of 6 into irreducibles:

6 = 2·3 = (1 + sqrt(-5))·(1 - sqrt(-5)).

The following is a very deep theorem:

Theorem There are exactly nine negative values of D for which O(sqrt(D)) is a UFD.
They are D = - 1, -2, -3, -7, -11, -19, -43, -67, -163.

On the other hand, it is not known whether or not there are infinitely many positive values of D for which O(sqrt(D)) is a UFD.

-- Steven Weintraub

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.