2Rings
IB Groups, Rings and Modules
2.4 Factorization in integral domains
We now move on to tackle the problem of factorization in rings. For sanity,
we suppose throughout the section that
R
is an integral domain. We start by
making loads of definitions.
Definition (Unit). An element
a ∈ R
is a unit if there is a
b ∈ R
such that
ab = 1
R
. Equivalently, if the ideal (a) = R.
Definition (Division). For elements
a, b ∈ R
, we say
a
divides
b
, written
a | b
,
if there is a c ∈ R such that b = ac. Equivalently, if (b) ⊆ (a).
Definition (Associates). We say
a, b ∈ R
are associates if
a
=
bc
for some unit
c. Equivalently, if (a) = (b). Equivalently, if a | b and b | a.
In the integers, this can only happen if
a
and
b
differ by a sign, but in more
interesting rings, more interesting things can happen.
When considering division in rings, we often consider two associates to be
“the same”. For example, in Z, we can factorize 6 as
6 = 2 · 3 = (−2) · (−3),
but this does not violate unique factorization, since 2 and
−
2 are associates (and
so are 3 and −3), and we consider these two factorizations to be “the same”.
Definition (Irreducible). We say
a ∈ R
is irreducible if
a 6
= 0,
a
is not a unit,
and if a = xy, then x or y is a unit.
For integers, being irreducible is the same as being a prime number. However,
“prime” means something different in general rings.
Definition (Prime). We say
a ∈ R
is prime if
a
is non-zero, not a unit, and
whenever a | xy, either a | x or a | y.
It is important to note all these properties depend on the ring, not just the
element itself.
Example. 2 ∈ Z is a prime, but 2 ∈ Q is not (since it is a unit).
Similarly, the polynomial 2
X ∈ Q
[
X
] is irreducible (since 2 is a unit), but
2X ∈ Z[X] not irreducible.
We have two things called prime, so they had better be related.
Lemma. A principal ideal (
r
) is a prime ideal in
R
if and only if
r
= 0 or
r
is
prime.
Proof.
(
⇒
) Let (
r
) be a prime ideal. If
r
= 0, then done. Otherwise, as prime
ideals are proper, i.e. not the whole ring,
r
is not a unit. Now suppose
r | a · b
.
Then
a ·b ∈
(
r
). But (
r
) is prime. So
a ∈
(
r
) or
b ∈
(
r
). So
r | a
or
r | b
. So
r
is
prime.
(
⇐
) If
r
= 0, then (0) =
{
0
} C R
, which is prime since
R
is an integral
domain. Otherwise, let
r 6
= 0 be prime. Suppose
a · b ∈
(
r
). This means
r | a · b
.
So r | a or r | b. So a ∈ (r) and b ∈ (r). So (r) is prime.
Note that in
Z
, prime numbers exactly match the irreducibles, but prime
numbers are also prime (surprise!). In general, it is not true that irreducibles
are the same as primes. However, one direction is always true.
Lemma. Let r ∈ R be prime. Then it is irreducible.
Proof.
Let
r ∈ R
be prime, and suppose
r
=
ab
. Since
r | r
=
ab
, and
r
is
prime, we must have
r | a
or
r | b
. wlog,
r | a
. So
a
=
rc
for some
c ∈ R
. So
r
=
ab
=
rcb
. Since we are in an integral domain, we must have 1 =
cb
. So
b
is
a unit.
We now do a long interesting example.
Example. Let
R = Z[
√
−5] = {a + b
√
−5 : a, b ∈ Z} ≤ C.
By definition, it is a subring of a field. So it is an integral domain. What are
the units of the ring? There is a nice trick we can use, when things are lying
inside C. Consider the function
N : R → Z
≥0
given by
N(a + b
√
−5) 7→ a
2
+ 5b
2
.
It is convenient to think of this as
z 7→ z¯z
=
|z|
2
. This satisfies
N
(
z · w
) =
N
(
z
)
N
(
w
). This is a desirable thing to have for a ring, since it immediately
implies all units have norm 1 — if
r ·s
= 1, then 1 =
N
(1) =
N
(
rs
) =
N
(
r
)
N
(
s
).
So N (r) = N(s) = 1.
So to find the units, we need to solve
a
2
+ 5
b
2
= 1, for
a
and
b
units. The
only solutions are
±
1. So only
±
1
∈ R
can be units, and these obviously are
units. So these are all the units.
Next, we claim 2
∈ R
is irreducible. We again use the norm. Suppose 2 =
ab
.
Then 4 =
N
(2) =
N
(
a
)
N
(
b
). Now note that nothing has norm 2.
a
2
+ 5
b
2
can
never be 2 for integers
a, b ∈ Z
. So we must have, wlog,
N
(
a
) = 4
, N
(
b
) = 1.
So
b
must be a unit. Similarly, we see that 3
,
1 +
√
−5,
1
−
√
−5
are irreducible
(since there is also no element of norm 3).
We have four irreducible elements in this ring. Are they prime? No! Note
that
(1 +
√
−5)(1 −
√
−5) = 6 = 2 · 3.
We now claim 2 does not divide 1 +
√
−5 or 1 −
√
−5. So 2 is not prime.
To show this, suppose 2
|
1 +
√
−5
. Then
N
(2)
| N
(1 +
√
−5
). But
N
(2) = 4
and
N
(1 +
√
−5
) = 6, and 4
-
6. Similarly,
N
(1
−
√
−5
) = 6 as well. So
2 - 1 ±
√
−5.
There are several life lessons here. First is that primes and irreducibles are
not the same thing in general. We’ve always thought they were the same because
we’ve been living in the fantasy land of the integers. But we need to grow up.
The second one is that factorization into irreducibles is not necessarily unique,
since 2 · 3 = (1 +
√
−5)(1 −
√
−5) are two factorizations into irreducibles.
However, there is one situation when unique factorizations holds. This is
when we have a Euclidean algorithm available.
Definition (Euclidean domain). An integral domain
R
is a Euclidean domain
(ED) if there is a Euclidean function φ : R \ {0} → Z
≥0
such that
(i) φ(a · b) ≥ φ(b) for all a, b 6= 0
(ii) If a, b ∈ R, with b 6= 0, then there are q, r ∈ R such that
a = b · q + r,
and either r = 0 or φ(r) < φ(b).
What are examples? Every time in this course where we said “Euclidean
algorithm”, we have an example.
Example. Z is a Euclidean domain with φ(n) = |n|.
Example. For any field F, F[X] is a Euclidean domain with
φ(f) = deg(f).
Example. The Gaussian integers
R
=
Z
[
i
]
≤ C
is a Euclidean domain with
φ(z) = N (z) = |z|
2
. We now check this:
(i) We have φ(zw) = φ(z)φ(w) ≥ φ(z), since φ(w) is a positive integer.
(ii) Given a, b ∈ Z[i], b 6= 0. We consider the complex number
a
b
∈ C.
Consider the following complex plane, where the red dots are points in
Z[i].
Re
Im
a
b
By looking at the picture, we know that there is some
q ∈ Z
[
i
] such that
a
b
− q
< 1. So we can write
a
b
= q + c
with |c| < 1. Then we have
a = b · q + b · c
|{z}
r
.
We know
r
=
a − bq ∈ Z
[
i
], and
φ
(
r
) =
N
(
bc
) =
N
(
b
)
N
(
c
)
< N
(
b
) =
φ
(
b
).
So done.
This is not just true for the Gaussian integers. All we really needed was that
R ≤ C
, and for any
x ∈ C
, there is some point in
R
that is not more than 1 away
from x. If we draw some more pictures, we will see this is not true for Z[
√
−5].
Before we move on to prove unique factorization, we first derive something
we’ve previously mentioned. Recall we showed that every ideal in
Z
is principal,
and we proved this by the Euclidean algorithm. So we might expect this to be
true in an arbitrary Euclidean domain.
Definition (Principal ideal domain). A ring
R
is a principal ideal domain (PID)
if it is an integral domain, and every ideal is a principal ideal, i.e. for all
I C R
,
there is some a such that I = (a).
Example. Z is a principal ideal domain.
Proposition. Let
R
be a Euclidean domain. Then
R
is a principal ideal domain.
We have already proved this, just that we did it for a particular Euclidean
domain Z. Nonetheless, we shall do it again.
Proof.
Let
R
have a Euclidean function
φ
:
R \ {
0
} → Z
≥0
. We let
I C R
be a
non-zero ideal, and let
b ∈ I \ {
0
}
be an element with
φ
(
b
) minimal. Then for
any a ∈ I, we write
a = bq + r,
with
r
= 0 or
φ
(
r
)
< φ
(
b
). However, any such
r
must be in
I
since
r
=
a −bq ∈ I
.
So we cannot have
φ
(
r
)
< φ
(
b
). So we must have
r
= 0. So
a
=
bq
. So
a ∈
(
b
).
Since this is true for all
a ∈ I
, we must have
I ⊆
(
b
). On the other hand, since
b ∈ I, we must have (b) ⊆ I. So we must have I = (b).
This is exactly, word by word, the same proof as we gave for the integers,
except we replaced the absolute value with φ.
Example.
Z
is a Euclidean domain, and hence a principal ideal domain. Also,
for any field F, F[X] is a Euclidean domain, hence a principal ideal domain.
Also, Z[i] is a Euclidean domain, and hence a principal ideal domain.
What is a non-example of principal ideal domains? In
Z
[
X
], the ideal
(2
, X
)
C Z
[
X
] is not a principal ideal. Suppose it were. Then (2
, X
) = (
f
). Since
2
∈
(2
, X
) = (
f
), we know 2
∈
(
f
) , i.e. 2 =
f · g
for some
g
. So
f
has degree
zero, and hence constant. So f = ±1 or ±2.
If
f
=
±
1, since
±
1 are units, then (
f
) =
Z
[
X
]. But (2
, X
)
6
=
Z
[
X
], since,
say, 1
6∈
(2
, X
). If
f
=
±
2, then since
X ∈
(2
, X
) = (
f
), we must have
±
2
| X
,
but this is clearly false. So (2, X) cannot be a principal ideal.
Example. Let
A ∈ M
n×n
(
F
) be an
n × n
matrix over a field
F
. We consider
the following set
I = {f ∈ F[X] : f(A) = 0}.
This is an ideal — if
f, g ∈ I
, then (
f
+
g
)(
A
) =
f
(
A
) +
g
(
A
) = 0. Similarly, if
f ∈ I and h ∈ F[X], then (fg)(A) = f(A)g(A) = 0.
But we know
F
[
X
] is a principal ideal domain. So there must be some
m ∈ F[X] such that I = (m) for some m.
Suppose
f ∈ F
[
X
] such that
f
(
A
) = 0, i.e.
f ∈ I
. Then
m | f
. So
m
is
a polynomial that divides all polynomials that kill
A
, i.e.
m
is the minimal
polynomial of A.
We have just proved that all matrices have minimal polynomials, and that
the minimal polynomial divides all other polynomials that kill
A
. Also, the
minimal polynomial is unique up to multiplication of units.
Let’s get further into number theory-like things. For a general ring, we
cannot factorize things into irreducibles uniquely. However, in some rings, this
is possible.
Definition (Unique factorization domain). An integral domain
R
is a unique
factorization domain (UFD) if
(i) Every non-unit may be written as a product of irreducibles;
(ii)
If
p
1
p
2
···p
n
=
q
1
···q
m
with
p
i
, q
j
irreducibles, then
n
=
m
, and they can
be reordered such that p
i
is an associate of q
i
.
This is a really nice property, and here we can do things we are familiar with
in number theory. So how do we know if something is a unique factorization
domain?
Our goal is to show that all principal ideal domains are unique factorization
domains. To do so, we are going to prove several lemmas that give us some
really nice properties of principal ideal domains.
Recall we saw that every prime is an irreducible, but in
Z
[
√
−5
], there are
some irreducibles that are not prime. However, this cannot happen in principal
ideal domains.
Lemma. Let
R
be a principal ideal domain. If
p ∈ R
is irreducible, then it is
prime.
Note that this is also true for general unique factorization domains, which
we can prove directly by unique factorization.
Proof.
Let
p ∈ R
be irreducible, and suppose
p | a · b
. Also, suppose
p - a
. We
need to show p | b.
Consider the ideal (
p, a
)
C R
. Since
R
is a principal ideal domain, there is
some d ∈ R such that (p, a) = (d). So d | p and d | a.
Since
d | p
, there is some
q
1
such that
p
=
q
1
d
. As
p
is irreducible, either
q
1
or d is a unit.
If
q
1
is a unit, then
d
=
q
−1
1
p
, and this divides
a
. So
a
=
q
−1
1
px
for some
x
.
This is a contradiction, since p - a.
Therefore
d
is a unit. So (
p, a
) = (
d
) =
R
. In particular, 1
R
∈
(
p, a
). So
suppose 1
R
=
rp
+
sa
, for some
r, s ∈ R
. We now take the whole thing and
multiply by b. Then we get
b = rpb + sab.
We observe that
ab
is divisible by
p
, and so is
p
. So
b
is divisible by
p
. So
done.
This is similar to the argument for integers. For integers, we would say if
p - a
,
then
p
and
a
are coprime. Therefore there are some
r, s
such that 1 =
rp
+
sa
.
Then we continue the proof as above. Hence what we did in the middle is to do
something similar to showing p and a are “coprime”.
Another nice property of principal ideal domains is the following:
Lemma. Let
R
be a principal ideal domain. Let
I
1
⊆ I
2
⊆ I
3
⊆ ···
be a chain
of ideals. Then there is some N ∈ N such that I
n
= I
n+1
for some n ≥ N .
So in a principal ideal domain, we cannot have an infinite chain of bigger
and bigger ideals.
Definition (Ascending chain condition). A ring satisfies the ascending chain
condition (ACC) if there is no infinite strictly increasing chain of ideals.
Definition (Noetherian ring). A ring that satisfies the ascending chain condition
is known as a Noetherian ring.
So we are proving that every principal ideal domain is Noetherian.
Proof.
The obvious thing to do when we have an infinite chain of ideals is to
take the union of them. We let
I =
∞
[
n≥1
I
n
,
which is again an ideal. Since
R
is a principal ideal domain,
I
= (
a
) for some
a ∈ R. We know a ∈ I =
S
∞
n=0
I
n
. So a ∈ I
N
for some N. Then we have
(a) ⊆ I
N
⊆ I = (a)
So we must have I
N
= I. So I
n
= I
N
= I for all n ≥ N.
Notice it is not important that
I
is generated by one element. If, for some
reason, we know
I
is generated by finitely many elements, then the same argument
work. So if every ideal is finitely generated, then the ring must be Noetherian.
It turns out this is an if-and-only-if — if you are Noetherian, then every ideal is
finitely generated. We will prove this later on in the course.
Finally, we have done the setup, and we can prove the proposition promised.
Proposition. Let
R
be a principal ideal domain. Then
R
is a unique factoriza-
tion domain.
Proof. We first need to show any (non-unit) r ∈ R is a product of irreducibles.
Suppose
r ∈ R
cannot be factored as a product of irreducibles. Then it is
certainly not irreducible. So we can write
r
=
r
1
s
1
, with
r
1
, s
1
both non-units.
Since
r
cannot be factored as a product of irreducibles, wlog
r
1
cannot be
factored as a product of irreducibles (if both can, then
r
would be a product of
irreducibles). So we can write
r
1
=
r
2
s
2
, with
r
2
, s
2
not units. Again, wlog
r
2
cannot be factored as a product of irreducibles. We continue this way.
By assumption, the process does not end, and then we have the following
chain of ideals:
(r) ⊆ (r
1
) ⊆ (r
2
) ⊆ ··· ⊆ (r
n
) ⊆ ···
But then we have an ascending chain of ideals. By the ascending chain condition,
these are all eventually equal, i.e. there is some
n
such that (
r
n
) = (
r
n+1
) =
(
r
n+2
) =
···
. In particular, since (
r
n
) = (
r
n+1
), and
r
n
=
r
n+1
s
n+1
, then
s
n+1
is a unit. But this is a contradiction, since
s
n+1
is not a unit. So
r
must be a
product of irreducibles.
To show uniqueness, we let
p
1
p
2
···p
n
=
q
1
q
2
···q
m
, with
p
i
, q
i
irreducible.
So in particular
p
1
| q
1
···q
m
. Since
p
1
is irreducible, it is prime. So
p
1
divides
some
q
i
. We reorder and suppose
p
1
| q
1
. So
q
1
=
p
1
·a
for some
a
. But since
q
1
is irreducible,
a
must be a unit. So
p
1
, q
1
are associates. Since
R
is a principal
ideal domain, hence integral domain, we can cancel p
1
to obtain
p
2
p
3
···p
n
= (aq
2
)q
3
···q
m
.
We now rename aq
2
as q
2
, so that we in fact have
p
2
p
3
···p
n
= q
2
q
3
···q
m
.
We can then continue to show that
p
i
and
q
i
are associates for all
i
. This also
shows that
n
=
m
, or else if
n
=
m
+
k
, saw, then
p
k+1
···p
n
= 1, which is a
contradiction.
We can now use this to define other familiar notions from number theory.
Definition (Greatest common divisor).
d
is a greatest common divisor (gcd) of
a
1
, a
2
, ··· , a
n
if
d | a
i
for all
i
, and if any other
d
0
satisfies
d
0
| a
i
for all
i
, then
d
0
| d.
Note that the gcd of a set of numbers, if exists, is not unique. It is only
well-defined up to a unit.
This is a definition that says what it means to be a greatest common divisor.
However, it does not always have to exist.
Lemma. Let
R
be a unique factorization domain. Then greatest common
divisors exists, and is unique up to associates.
Proof.
We construct the greatest common divisor using the good-old way of
prime factorization.
We let
p
1
, p
2
, ··· , p
m
be a list of all irreducible factors of
a
i
, such that no
two of these are associates of each other. We now write
a
i
= u
i
m
Y
j=1
p
n
ij
j
,
where n
ij
∈ N and u
i
are units. We let
m
j
= min
i
{n
ij
},
and choose
d =
m
Y
j=1
p
m
j
j
.
As, by definition, m
j
≤ n
ij
for all i, we know d | a
i
for all i.
Finally, if d
0
| a
i
for all i, then we let
d
0
= v
m
Y
j=1
p
t
j
j
.
Then we must have
t
j
≤ n
ij
for all
i, j
. So we must have
t
j
≤ m
j
for all
j
. So
d
0
| d.
Uniqueness is immediate since any two greatest common divisors have to
divide each other.