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 = us*_{1}s_{2}···s_{k} with

*u* a unit and

*s*_{1}, s_{2}, ..., s_{k} irreducibles, and, if in addition

*n = vt*_{1}t_{2}···t_{l} with

*v* a unit and

*t*_{1}, t_{2}, ..., t_{l} irreducibles, then

*k = l*, and, after possible rearrangement,

*s*_{1} and

*t*_{1} are associates,

*s*_{2} and

*t*_{2} are associates, ..., and

*s*_{k} and

*t*_{k} 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** = *{a*_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ... + a_{n}x^{n}}, where

*a*_{0}, a_{1}, a_{2}, a_{3}, ... , a_{n} 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, x*^{2} + 1, x^{2} - 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***[x*^{2},x^{3}], i.e.,

**S** = *{a*_{0} + a_{2}x^{2} + a_{3}x^{3} + ... + a_{n}x^{n}}, where

*a*_{0}, a_{1}, a_{2}, a_{3}, ... , a_{n} 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:

*x*^{6} = x^{2}x^{2}x^{2} = x^{3}x^{3}. Note that both *x*^{2} and *x*^{3} are irreducible, as neither can be factored *in* **S**, and they are certainly not associates. Thus we have two essentially distinct factorizations of *x*^{6}. Note also that neither of *x*^{2} and *x*^{3} is a prime, as *x*^{2} divides *x*^{3}x^{3} without dividing either factor, and *x*^{3} divides *x*^{2}x^{4} 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)/(c*^{2}-d^{2}D) + (bc-adD)/(c^{2}-d^{2}D))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*