Introduction

Recall the Venn diagram illustrating special kinds of integral domains.

I want to look at integral domains in general, but integral domains that are not unique factorization domains (UFDs) in particular. I’m interested in the outer ring of that diagram.

That is, I’m interested in factoring numbers in integral domains… so we have to investigate divsion, and so this post will begin with a fairly cursory look at the properties of division. Then we will introduce the crucial ideas of units and associates. (In the integers, ±1 are units and ±n, for any fixed n, are associates.)

Then we will talk about the properties of being prime and of being irreducible… they coincide in the integers – in fact, they coincide in any unique factorization domain – but in a very real sense, unique factorization fails precisely when these concepts do not coincide. (To be precise, in any domain in which factorization into irreducibles is possible – and there are domains in which it is not – the factorization is unique if and only if being prime and being irreducible are equivalent.)

Then I will finally talk about quadratic integer rings. I could almost have pretended that the only thing I was interested in was numbers of the form

$a + b \sqrt{D}$ for integers a and b

… except that I have already shown you one more general integral domain, namely

$a + b \frac{1+\sqrt{-19}}{2}$ for integers a and b

… so you’re already aware of the more general case. I shouldn’t just forget about it.

But I might have anyway, except that another of the more general cases has a property worth mentioning. Nevertheless, you could skip the section about the more general case.

Finally, I will do the work required to prove that the decomposition

$21 = 3\cdot 7 = (1+2\sqrt{-5})(1-2\sqrt{-5})$

does in fact write 21 as the product of irreducibles in 2 different ways. In other words, $Z[\sqrt{-5}]\$ is not a unique factorization domain.

Let me tell you up front that the major tool in the proof is something called a norm… it transfers computations in $Z[\sqrt{D}]\$ to computations in integers… and it has two crucial properties: one, the norm of a product is the product of the norms; and, two, the norm of a number is ±1 if and only if the number is a unit.

Recall that if a and b are two nonzero elements of a ring R such that

ab = 0

then a and b are called divisors of zero. Strictly speaking, a is a left zero divisor and b is a right zero divisor. In a noncommutative ring, we need not simultaneously have ba = 0, so the distinction between left and right is sometimes important. In a commutative ring, of course, any left divisor of zero is also a right divisor of zero, and any right divisor of zero is a left divisor of zero.

We see these in the rings Zn, for n composite (i.e. in the integers mod n). For example, in Z4, 2*2 = 0 mod 4 says that 2 is a divisor of zero, and in the ring Z6, 2*3 = 0 mod 6 says that 2 and 3 are zero divisors.

There is an important fact about zero divisors: we have cancellation laws whenever we’re not dealing with divisors of zero.

Theorem on cancellation in rings:
If a is not zero or a left divisor of zero, then

ax = ay implies x = y.

If b is not zero or a right divisor of zero, then

xb = yb implies x = y.

Recall that an integral domain is a commutative ring with unity 1 ≠ 0 and containing no divisors of zero. As a corllary of the theorem on cancellation in rings, we have

Theorem on cancellation in integral domains:
if a is not zero, then

ax = ay implies x = y

and

xb = yb implies x = y.

Any integral domain has many of the properties of the integers – but what I want to look at is a property of the integers which is not shared by all integral domains.

That property is called, generally, unique factorization. In the case of the integers, it is called the fundamental theorem of arithmetic: that any integer can be written essentially uniquely as a product of primes.

Let’s get started.

Division, Units, and Associates

Let R be a ring with unity 1 ≠ 0. An element u in R is a unit of R if it has a multiplicative inverse. Using this new terminlogy, we may say that if every nonzero element of R is a unit, then R is a division ring (skew field); and a commutative division ring is a field. We could say and write that an element u is called a unit if $\exists v\$ such that

uv = vu = 1.

(By specifying both, we’re allowing for the possibility that the ring is not commutative. Maybe I should have restricted myself to integral domains – which must be commutative – but some of the definitions make sense for rings with unity.)

The integers have two units: 1 and -1. In fact, every ring with 1 ≠ 0 has these two units. (Well, they need not be distinct. In Z2, $1 \equiv -1\ mod\ 2\$.

We have the following two properties.

Theorem on units and zero divisors:
In a commutative ring, no unit is a zero divisor.

Theorem on the multiplicative group of units:
In a commutative ring, the set of units forms a multiplicative group.

(In particular, any power of a unit is a unit.)

Let R be a ring and let a,b $\in R\$. if there exists c $\in R\$ such that

b = ac,

then a divides b (or a is a factor of b, or a is a divisor of b), denoted by a | b. In this terminlogy, a unit is any divisor of 1. (The following nice summary came from Dean’s “Classical Abstract Algebra”, Harper & Row, 1990.)

Theorem on the elementary properties of division…

if a ≠ 0, then a | 0

if R is a commutative ring then
1. a | b implies a | bc and a | -b.
2. a | b and b | c implies a | c.
3. a | b and a | c implies a | (b+c)

if, in addition, R has 1 then
4. u a unit in R implies $u | a\ \forall a \in R\$.

if, in addition, R is an integral domain, then
5. a | b and b | a implies b = au, u a unit
6. a | b implies $\exists! c\$ such that b = ac & we write c = b / a.

(4) says that in a commutative ring with unity, a unit divides everything. (All integers are divisible by ±1.)

(6) says that the quotient b/a is unique. Oh, that exclamation mark after $\exists\$ is read “a unique”.

I will elaborate on and prove (5) almost immediately. It offers an alternative characterization of a unit.

Two elements a,b $\in D\$ are associates if

a = bu,

where u is a unit in D. In the integers, we have pairs of associates: a and -a for any integer a. The property of being associates is an equivalence relation on D.

There is an alternative definition – an equivalent characterization – of associates… a and b are associates if each divides the other:

a | b and b | a imply a and b differ by a unit: a = be, so that
such a and b are associates.

(That’s (5) above.)

In the integers, a and -a are associates, and indeed a | -a and -a | a.

How would we prove the equivalence? First, suppose that a and b are associates… by definition, then, there exists a unit u such that

a = u b.

That, however, says that b divides a. On the other hand, since u is a unit, there exists v such that

v u = 1,

so we pick up

a = u b

and multiply by v…

v a = v u b = b

i.e. v a = b

which says that a divides b.

This we have shown that our definition of associates implies the equivalent property, that any two associates divide each other. Now let’s go the other way. Suppose a | b and b | a. Then there exist c and d such that

b = ac
a = bd
then
a = bd = (ac)d = a(cd)

and by cancellation (which requires an integral domain)

1 = cd,

which says that both c and d are units. In particular, c is a unit, so

b = ac

says that a and b are associates.

Thus we have shown that the equivalent property implies the definition. We may now use either property as the characteristic property of associates.

Next, I want to look at two properties of prime numbers. In a UFD, they are equivalent; but otherwise they are not.

prime and irreducible

A nonzero non-unit element p $\in D\$ is irreducible if in any factorization p = ab either a or b is a unit. It is just a matter of terminology to rephrase that as: the only divisors of p are associates of p and units. We could also rephrase that as: a nonzero non-unit element b is irreducible if a | b implies that a is a unit or an associate of b.

We know this perfectly well – I hope! – in the integers. 2 is prime because its only factorizaions are

2 = 1*2, in which 1 is a unit

and
2 = (-1)(-2), in which -1 is a unit and -2 is an associate.

I could remark that an associate of an irreducible is itself irreducible.

A nonzero element p is prime if p | ab implies that either p | a or p | b.

Theorem that prime implies irreducible:
any prime in an integral domain is irreducible.

I will eventually show you that in $Z[\sqrt{-5}]\$, 3 is irreducible but not prime. Actually, part of it is simple enough. We know that 3 divides 21… but we also can compute that

$21 = (1+2\sqrt{-5})(1-2\sqrt{-5})\$,

and 3 does not divide either $(1+2\sqrt{-5})\$ or $(1-2\sqrt{-5})\$ – that is, we have a | bc (3 | $(1+2\sqrt{-5})(1-2\sqrt{-5}))\$, but have neither a | b nor a | c, so a (in this case 3) is not prime. It’s more work to show that 3 is irreducible, but we will.

Furthermore, the argument that 3 is not prime extends to any case of multiple factorizations into irreducibles. Any irreducible in one factorization divides the product of the irreducibles in the other factorization, but does not divide the other irreducibles. This is why “prime not equivalent to irreducible” corresponds to “not-UFD”, provided a factorization into irreducibles is even possible – as I said before, it need not be possible.

An integral domain D is a unique factorization domain (UFD) if the following two conditions are satisfied:

1. every element of D that is neither 0 nor a unit can be factored into a product of a finite number of irreducibles.
2. If $p_1 ... p_r\$ and $q_1 ... q_s\$ are two factorizations of the same element, then r = s and the $q_i\$ can be renumbered so that $p_i\$ and $q_i\$ are associates.

The first condition says that elements of D can be factored; the second condition says that the factorization is unique up to order and associates. Think

6 = 2*3 = (-2)(-3) = 3*2 = (-3)*(-2),

where we can scramble the order and substitute associates for 2 and 3, but the decomposition is unique if we treat different orders and associates as essentially equivalent – which is what the theorem says.

Then our counter-example will eventually show that 21 is not a unit… we already know that it can be factored… we don’t officially know that 3, 7, and $(1+2\sqrt{-5})\$ and $(1-2\sqrt{-5})\$ are irreducible… but once we do, then we will know that Z[-5] is not a UFD. We will have factored 21 two ways using irreducibles.

the easy (incomplete) case

Now let’s talk about numbers of the form

$a + b \sqrt{D}\$,

where D is an integer. We denote them by Z[D].

It’s perfectly OK for D to be negative… but there is one restriction on D. We assume that D has no squares as factors. For example, numbers of the form

$a + b \sqrt{4}$

become

a + 2b, i.e. ordinary integers, so Z[4] is just Z itself. On the other hand, numbers of the form

$a + b \sqrt{8}$

become

$a + 2 b \sqrt{2}\$.

That looks to me like a smaller set than $a + b \sqrt{2}]\$…. I’ll make more sense of the restriction on D in the next section. Anyway, the usual terminology is to say that we require D to be square-free.

Oh, I should point out that one of the first, if not the first, such sets of numbers was the Gaussian integers, which are the case D = -1:

Z[-1] = {a + i b} = {$a + b \sqrt{-1}\$}.

Now there is a very handy tool, introduced, I’m sure, by Gauss. For the set of numbers Z[D], we define a norm N as

$N(a+b \sqrt{D}) = (a + b \sqrt{D})(a-b \sqrt{D}) = a^2 - b^2 D\$.

I’ll call it the quadratic norm.

More generally, any function N from an integral domain R into the non-negative integers with N(0) = 0 is called a norm on the integral domain. if N(a) > 0 for a ≠ 0, it is called a positive norm.

Note that for D > 0, the quadratic norm N is not a positive norm. But is does satisfy both

• N(0) = 0
• $N(\alpha)\$ is an integer.

It also has some additional properties. It is a multiplicative norm:

$N(\alpha \beta) = N(\alpha) N(\beta)\$;

and we also have the

theorem on unit norms:

$\alpha\$ is a unit iff $N(\alpha)\$ = ±1;

and we also have the
theorem on prime norms:

if $N(\alpha)\$ is ± a prime (in Z) then $\alpha\$ is irreducible.

This idea of a norm is extremely powerful, because we get to do computations in Z, which we understand thoroghly, rather than in $Z[\sqrt{D}]\$ which we don’t yet.

Let’s try proving that last assertion. Suppose that we have $\alpha \in Z[D]\$ and that

$N(\alpha) = p\$, a prime.

Suppose further that $\alpha\$ can be factored as $\alpha = \beta\gamma\$. If we can show that one of $\beta \text{ or } \gamma\$ is a unit, then $\alpha\$ is irreducible. Well,

$N(\alpha) = N(\beta\gamma) = N(\beta) N(\gamma) = p\$

so the product $N(\beta) N(\gamma)\$ is a prime number. Then one of $N(\beta) \text{ or } N(\gamma)\$ is a unit… suppose it’s $N(\beta)\$ that is a unit, then so is $\beta\$ and we are done.

I know that not all norms are multiplicative – the degree of a polynomial is a norm on the integral domain Z[x] of polynomials with integer coefficients, but it is usually additive instead of multiplicative.

For any multiplicative norm in general we have the weaker

if $\alpha\$ is a unit, then $N(\alpha)\$ = ±1,

rather than if and only if. But remember that I am using a specific norm, on a specific kind of integral domain.

When in doubt, look at the proof. The only proof I’ve seen that $N(\alpha)\$ = ±1 implies $\alpha\$ is a unit is for the specific norm I’m using (and a slight generalization, next). In the other direction, however, we only need the norm to be multiplicative.

when D is congruent to 1 mod 4

Just as we figure that $Z[\sqrt{2}]\$ contains $Z[\sqrt{8}]\$, there are some more things we should consider as quadratic integer domains.

There are two ways to get to numbers of the form $a + b \sqrt{D}\$. What I have done is to take a and b to be integers, and extend the integers. The alternative is to begin by extending the rationals – that is, to consider

$Q[\sqrt{D}] := a + b \sqrt{D}\$, where a and b are rational instead of merely integer…

and then look for “integers” in $Q[\sqrt{D}]\$. And as soon as we consider $Q[\sqrt{D}]\$ – as soon as a and b are rational – then without loss of generality, D may be assumed square-free. For example, $Q[\sqrt{8}] = Q[\sqrt{2}]\$.

Anyway, if D is congruent to 1 mod 4, something interesting happens…. If $D \equiv 1 mod 4\$, then numbers of the form

$a + b/2 (1+\sqrt{D})$

also form an integral domain. Even better, the quadratic norm of any such number is an integer. That’s one reason for extending the definition.

In fact, I’ve shown you one of these: $Z[(1+\sqrt{-19})/2]\$ is a PID which is not a Euclidean domain. If that were the only example of interest, I might have avoided this whole subject.

But there’s another example I want to show you. But let me start with the Gaussian integers.

If D = -1, then N(a+bi) = $a^2 + b^2\$, the squared length of the complex integer a + bi. Furthermore, the units are ±1 and ± i, which is C4, the cyclic group of order 4. (-1 is of order 2, but i and -i are of order 4.)

For all other D < 0, the only units are ±1, with one exception… and I just have to show you this.

If D = -3, then the units are {$\pm 1 , \pm\rho, \pm\rho^2\$} where

That looks familiar…

Yes, it is a cube root of 1. And it is a unit:

NOTE that this is of the form $a + b/2 (1+\sqrt{-3})\$… with a = -1 and b = 1:

That is, we have $-3 \equiv 1 mod 4\$, so this is another case where we want $(1+\sqrt{D})/2\$. That is, we would have missed two very unusual units if we had restricted ourselves to the smaller integral domain $a + b \sqrt{-3}\$.

There's a little more to this.

We say that a number is algebraic if it is the root of a polynomial having rational coefficients. Equivalently, if it is the root of a polynomial with integer coefficients. (Just clear the denominators.)

We say that a number is an algebraic integer if it is the root of a monic polynomial with integer coefficients. (Recall that a polynomial is monic if its leading term – its highest power – has coefficient 1.) Finally, we say that a number is a quadratic integer if it is the root of a monic quadratic polynomial. $\rho\$, for example, is a quadratic integer because it is a solution of $\rho^2 + \rho + 1 = 0\$.

It can be shown that there are two cases. A quadratic integer is either of the form

$a + b \sqrt{D}\$, where $D \equiv 2 mod 4 \text{ or } D \equiv 3 mod 4\$, and a, b are integers;

$a + b \sqrt{D}\$, where $D \equiv 1 mod 4\$, and both a and b are odd integers.

That latter case can also be written

$a + b/2 (1+\sqrt{D})\$, where a,b are integers, which is our earlier definition whenever $D \equiv 1 mod 4\$.

An excellent discussion can be found in Stewart & Tall, "Algebraic Number Theory and Fermat's Last Theorem", 3rd ed., A.K.Peters, 2002. If all you want is the bare statement that the appropriate quadratic integer ring is defined in two different ways depending on D mod 4, that's in Dummit & Foote.

To summarize, there are two ways to decide that $a + b \sqrt{-3}\$ is too restrictive. One, for any number of the form $\alpha = a + b/2 (1+\sqrt{-3})\$, we have that the norm of $\alpha\$ is an integer: $N(\alpha)\$ is an integer.

Two, numbers of the more general form fit the definition of an algbraic (quadratic) integer.

So, quadratic integer rings are a bit more complicated than just $a + b \sqrt{D}\$.

As I was saying, for D < 0, the only units are ±1, except for D = -1 and for D = -3.

Finally, for D > 0, the group of units is infinite. And, unlike the cases D = -1 and D = -3, the set of powers is infinite.

Here, for D = 2, is a unit:

and the norm of any power of u will be ±1, and the powers will be distinct.

Think about that. In the domain $a + b \sqrt{2}\$, the number $1 + \sqrt{2}\$ “acts like” 1.

Let's get back to our real purpose.

Z[-5] is not a UFD

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

We wish to show that all four factors are irreducible, that if any one of them can be factored, its factors are units or associates.

Is 21 a unit? No. It has norm N(21) = 441, which is far from ±1.

Is 3 irreducible? We have shown it's not prime, but irreducibility is a different question. Well, N(3) = 9, which is not prime, so we can't use the theorem on a prime norm. But the same kind of calculation works… we just have to do it twice.

So suppose that 3 can be factored, i.e. that $3 = \alpha \beta\$. Then taking norms, we get

$9 = N(\alpha\ \beta) = N(\alpha) N(\beta)$

and the only possibilities are

$N(\alpha) = 9 \text{ and } N(\beta) = 1$

$N(\alpha) = 1 \text{ and }N(\beta) = 9$

$N(\alpha) = N(\beta) = 3\$.

In the two cases where $N(\alpha) = 1 \text{ or } N(\beta) = 1\$, we conclude that $\alpha\$ (resp. $\beta\$) is a unit… which implies that 3 is irreducible.

In the case $N(\alpha) = N(\beta) = 3\$, we need to look more closely at $\alpha\$. We know that for some a, b we have

$\alpha = a + b \sqrt{-5}$

so

$N(\alpha) = a^2 + 5 b^2 = 3$

but that's impossible, for integers a and b! (It's an ellipse, but 3 is too small for there to be integer solutions.) That means that the two cases where $N(\alpha) = 1\$ or $N(\beta) = 1\$ are the only possible cases, so 3 is irreducible.

And we've already seen that 3 is not prime in $Z[\sqrt{-5}]\$ – precsiely because of the two factorizations of 21…. So we have a memorable counter-example:

In Z[-5], the number 3 is irreducible but not prime.

Let's continue. A similar argument shows that 7 is irreducible, so we have at least one factorization of 21 into a product of irreducibles.

What about the other factorization? We need to show that

$1 + 2 \sqrt{-5}$

is irreducible. It's not a unit because its norm is 21, not ±1.

Well, suppose it can be factored nontrivially:

$1 + 2 \sqrt{-5} = \alpha \beta\$.

Then $N(1 + 2 \sqrt{-5}) = N(\alpha) N(\beta) = 21\$. We must have one of the following cases

$N(\alpha) = 1 \text{ and } N(\beta) = 21\$ – in which case, $\alpha\$ is a unit

$N(\alpha) = 3 \text{ and } N(\beta) = 7\$ – but neither is possible:

The only remote possibilities are b=±1, but then we get

$a^2 = 2$

and we know that $\sqrt{2}\$isn't even rational, never mind an integer.

(and similarly for $\alpha \text { and }\beta\$ interchanged).

Similarly, $1 - 2 \sqrt{-5}\$ is irreducible.

So unique factorization fails in Z[-5], becase 21 can be wriiten in two different ways as a product of irreducibles.

And that's what all this was about. Whew!