Factorization in Integral Domains I

Throughout these notes, R denotes an integral domain unless other-

wise noted.

1 Unique factorization domains and principal ideal

domains
Definition 1.1. For r, s ∈ R, we say that r divides s (written r|s) if there
exists a t ∈ R such that s = tr. An element u ∈ R is a unit if it has
a multiplicative inverse, i.e. if there exists an element v ∈ R such that
uv = 1. The (multiplicative) group of units is denoted R∗ . If r, s ∈ R, then
r and s are associates if there exists a unit u ∈ R∗ such that r = us. In
this case, s = u−1 r, and indeed the relation that r and s are associates is an
equivalence relation (HW). Another easy result is (this was on the midterm):
Lemma 1.2. For an integral domain R, if r, s ∈ R, then r and s are
associates ⇐⇒ (r) = (s).
Proof. =⇒ : If r = us, then r ∈ (s), hence (r) ⊆ (s). Since s = u−1 r,
s ∈ (r), and hence (s) ⊆ (r). Thus (r) = (s).
⇐= : If r = 0, then (r) = (0) = {0}, so if (s) = (r), then s ∈ {0}, hence
s = 0. Thus r = s = 0, and in particular r and s are associates, since for
example s = 1 · r. If r 6= 0, then (s) = (r) =⇒ s ∈ (r) =⇒ s = tr for
some t ∈ R. Likewise r ∈ (s), so r = us for some u ∈ R. Thus

r = us = utr.

By assumption, r 6= 0, and since R is an integral domain, we can cancel r.

Thus 1 = ut. So u is a unit and r = us, so that r and s are associates.

Example 1.3. 1) R = Z. The units Z∗ = ±1. Two integers n and m are

associates ⇐⇒ m = ±n.
2) R = F [x], F a field. The units in F [x] are: (F [x])∗ = F ∗ , the set of
constant nonzero polynomials. Hence, if F is infinite, there are an infinite

1
number of units. Two polynomials f and g are associates ⇐⇒ there exists
a c ∈ F ∗ with g = cf .
3) R = Z[i], the Gaussian integers. The units (Z[i])∗ = {±1, ±i}. Two
elements α, β √∈ Z[i] are associates ⇐⇒ α = ±β or α = ±iβ. √
4) R = Z[ 2]. As we √have seen on the homework, 1 + 2 is a unit of
infinite order.√In fact, (Z[ 2])∗ ∼
= Z × (Z/2Z). √
5) R = Z[ −2]. An easy calculation shows that (Z[ −2])∗ = {±1}.
We say that r ∈ R is irreducible if r 6= 0, r is not a unit, and, for all
s ∈ R, if s divides r then either s is a unit or s is an associate of r. In other
words, if r = st for some t ∈ R, then one of s or t is a unit (and hence the
other is an associate of r). If r ∈ R with r 6= 0 and r is not a unit, then r is
reducible if it is not irreducible.
Definition 1.4. Let r, s ∈ R, not both 0. A greatest common divisor (gcd)
of r and s is an element d ∈ R such that d|r, d|s, and if e ∈ R and e|r, e|s,
then e|d.
Lemma 1.5. Let r, s ∈ R, not both 0. If a gcd of r and s exists, it is unique
up to a unit (i.e. any two gcd’s of r and s are associates).
Proof. If d and d0 are both a gcd of r and s, then by definition d|d0 and d0 |d.
Hence there exist u, v ∈ R such that d0 = ud and d = vd0 . Thus d = uvd.
Since d|r and d|s and at least one of r, s is nonzero, d 6= 0. Hence uv = 1,
so that u and v are units. Thus d and d0 are associates.

Definition 1.6. Let r, s ∈ R, not both 0. The elements r and s are relatively
prime if 1 is a gcd of r and s; equivalently, if d ∈ R and d|r, d|s, then d is a
unit.
Lemma 1.7. Let r, s ∈ R, with r irreducible.Then a gcd of r and s exists,
and is either a unit or an associate of r. Hence, if r does not divide s, then
r and s are relatively prime.
Proof. Suppose that r divides s. Then r is a gcd of r and s, since r divides
both r and s and any e which divides r and s is either a unit or an associate
of r, hence divides r. If r does not divide s, then any e which divides r and
s cannot be an associate of r, hence must be a unit. It follows that 1 is a
gcd of r and s, and hence r and s are relatively prime.

Definition 1.8. R is a unique factorization domain (UFD) if

(i) for every r ∈ R not 0 or a unit, there exist irreducibles p1 , . . . , pn ∈ R
such that r = p1 · · · pn , and

2
 (ii) if pi , 1 ≤ i ≤ n and qj , 1 ≤ j ≤ m are irreducibles such that p1 · · · pn =
q1 · · · qm , then n = m and, after reordering, pi and qi are associates.

Note that two separate issues are involved: (i) the existence of some
factorization of r into irreducibles and (ii) the uniqueness of a factorization.
As we shall see, these two questions are in general unrelated, in the sense
that one can hold but not the other.
Given an element r in a UFD, not 0 or a unit, it is often more natural to
factor r by grouping together all of the associated irreducibles (after making
some choices). Hence, such an r can always be written as

r = upa11 · · · pann ,

where u is a unit, the pi are irreducibles, ai > 0, and, for i 6= j, pi and pj

are not associates, and such a product is essentially unique in the following
sense: if also
r = vq1b1 · · · qm
bm
,
where v is a unit, the qj are irreducibles, bj > 0, and, for k 6= `, qk and q`
are not associates, then n = m and, after reordering, pi and qi are associates
and ai = bi .

Definition 1.9. R is a principal ideal domain (PID) if every ideal I of R is

principal, i.e. for every ideal I of R, there exists r ∈ R such that I = (r).

Example 1.10. The rings Z and F [x], where F is a field, are PID’s.

We shall prove later: A principal ideal domain is a unique factorization

domain. However, there are many examples of UFD’s which are not PID’s.
For example, if n ≥ 2, then the polynomial ring F [x1 , . . . , xn ] is a UFD but
not a PID. Likewise, Z[x] is a UFD but not a PID, as is Z[x1 , . . . , xn ] for all
n ≥ 1.

Proposition 1.11. If R is a UFD, then the gcd of two elements r, s ∈ R,

not both 0, exists.

Proof. If say r = 0, then the gcd of r and s exists and is s. If r is a unit,

then the gcd of r and s exists and is a unit. So we may clearly assume that
r is neither 0 nor a unit, and likewise that s is neither 0 nor a unit. Then we
can factor both r and s as in the comments after the definition of a UFD.
In fact, it is clear that we can write

r = upa11 · · · pakk , s = vpb11 · · · pbkk

3
where u and v are units, the pi are irreducibles, ai , bi ≥ 0, and, for i 6= j, pi
and pj are not associates. (Here, we set ai = 0 if pi is not a factor of r, and
similarly for bi .) Then set
d = pc11 · · · pckk ,
where ci = min{ai , bi }. We claim that d is a gcd of r and s. Clearly d|r
and d|s. If now e|r and e|s and q is an irreducible factor of e, then q is
an associate of pi for some i, and so we can assume that q = pi . If mi is
the largest integer such that pm mi mi
i |e, then since pi |r and pi |s, mi ≤ ai and
i

mi ≤ bi . Hence mi ≤ ci . It then follows by taking the factorization of e into

powers of the pi times a unit that e|d. Hence d is a gcd of r and s.

Lemma 1.12. If R is a UFD and p, r, s ∈ R are such that p is an irreducible

and p|rs, then either p|r or p|s. More generally, if t and r are relatively
prime and t|rs then t|s.
Proof. To see the first statement, write rs = pt and factor r, s, t into irre-
ducibles. Then p must be an associate of some irreducible factor of either
r or s, hence p divides either r or s. The second statement can be proved
along similar but slightly more complicated lines.

As a consequence, we have:
Proposition 1.13. Let R be a UFD and let r ∈ R, where r 6= 0. Then (r)
is a prime ideal ⇐⇒ r is irreducible.
Proof. =⇒ : If (r) is a prime ideal, then r is not a unit, and r 6= 0 by
assumption. If r = st, then one of s, t ∈ (r), say s ∈ (r), hence s = ru.
Then r = rut so that ut = 1 and t is a unit. Hence r is irreducible. (Note:
this part did not use the fact that R was a UFD, and holds in every integral
domain.)
⇐= : If r is irreducible, then it is not a unit and hence (r) 6= R. Suppose
that st ∈ (r). Then r|st. By the remark above, either r|s or r|t, i.e. either
s ∈ (r) or t ∈ (r). Hence (r) is prime.

Remark 1.14. (i) In case R is not a UFD, there will in general exist irre-
ducibles r such that (r) is not a prime ideal.
(ii) In general, suppose that R is an integral domain and that r ∈ R, r 6= 0.
If (r) is a prime ideal, then for all s, t ∈ R, if r divides st, then either r
divides s or r divides t.
We turn now to the study of a PID, with a view toward showing even-
tually that a PID is a UFD.

4
Theorem 1.15. Let R be a PID, and let r, s ∈ R, not both 0. Then a gcd
d of r and s exists. Moreover, d is a linear combination of r and s: there
exist a, b ∈ R such that d = ar + bs.

Note: For a general UFD, the gcd of two elements r and s will not in
general be a linear combination of r and s. For example, in F [x, y], the
elements x and y are relatively prime, hence their gcd is 1, but 1 is not a
linear combination of x and y, since if f = xa + yb is any linear combination
of x and y, where a, b ∈ F [x, y], then ev0,0 (f ) = f (0, 0) = 0, but ev0,0 (1) = 1.

Proof. This argument is very similar to the corresponding argument for F [x],
or for Z. Given r, s ∈ R, not both 0, consider the ideal

(r, s) = {ar + bs : a, b ∈ R} = (r) + (s).

Then (r, s) is easily checked to be an ideal, hence there exists a d ∈ R

with (r, s) = (d). By construction d = ar + bs for some r, s ∈ R. Since
r = 1 · r + 0 · s ∈ (r, s) = (d), this says that d|r. Similarly d|s. Finally, if e|r
and e|s, then e|(ar + bs) = d.

Corollary 1.16. If R is a PID, r, s ∈ R are relatively prime and r|st, then

r|t.

Proof. Write 1 = ar+bs for some a, b ∈ R. Then t = tar+tbs = r(at)+b(st).

By assumption r|st and clearly r|r(at). Hence r|t.

Corollary 1.17. If R is a PID, and r ∈ R is an irreducible, then for all

s, t ∈ R, if r|st, then either r|s or r|t.

Proof. By Lemma 1.7, if r does not divide s, then r and s are relatively
prime. Then, by the previous corollary, r|t. Hence either r|s or r|t.

The following proves the uniqueness half of the assertion that a PID is
a UFD:

Corollary 1.18. If R is a PID, then uniqueness of factorization holds in

R: if pi , 1 ≤ i ≤ n and qj , 1 ≤ j ≤ m are irreducibles such that p1 · · · pn =
q1 · · · qm , then n = m and, after reordering, pi and qj are associates.

Proof. This is proved in exactly the same way as the argument we gave for
F [x] (or, in Modern Algebra I, for Z).

Theorem 1.19. A PID is a UFD.

5
Proof. We have already seen that, if an irreducible factorization exists, it
is unique up to order and associates. Thus the remaining point is to show
that, if R is a PID, then every element r ∈ R, not 0 or a unit, admits some
factorization into a product of irreducibles. The proof will be in several
steps.
Lemma 1.20. Let R be an integral domain with the property that, if

(r1 ) ⊆ (r2 ) ⊆ · · · ⊆ (rn ) ⊆ (rn+1 ) ⊆ · · ·

is an increasing sequence of principal ideals, then the sequence is eventually

constant, i.e. there exists an N such that, for all n ≥ N , (rn ) = (rN ). Then
every nonzero r ∈ R which is not a unit factors into a product of irreducibles.
We can paraphrase the hypothesis of the lemma by saying that R satisfies
the ascending chain condition (a.c.c) on principal ideals.

Proof of the lemma. Suppose by contradiction that r ∈ R is an element,

not zero or a unit, which does not factor into a product of irreducibles. In
particular, r itself is not irreducible, so that r = r1 s1 where neither r1 nor s1
is a unit. Thus (r) is properly contained in (r1 ) and in (s1 ), by Lemma 1.2.
Clearly, we can assume that at least one of r1 , s1 , say r1 , does not factor
into irreducibles (if both so factor, so does the product). By applying the
above to r1 , we see that (r1 ) is strictly contained in a principal ideal (r2 ),
where r2 does not factor into a product of irreducibles. Continuing in this
way, we can produce a strictly increasing infinite chain of principal ideals
(r1 ) ⊂ (r2 ) ⊂ · · · , i.e. each (ri+1 ) properly contains the previous ideal (ri ),
contradicting the hypothesis on R.

To complete the proof of the theorem that a PID is a UFD, it suffices

to show that a PID R satisfies the hypotheses of the above lemma. First
suppose that (r1 ) ⊆ (r2 ) ⊆
S · · · is an increasing sequence of ideals of R. It
is easy to check that I = i (ri ) is again an ideal. More generally, we have
the following:
Claim 1.21. Let R be a ring, not necessarily an integral domain,S and let
I1 ⊆ I2 ⊆ · · · be an increasing sequence of ideals of R. If I = n In , then I
is an ideal of R.

Proof. It suffices to show that I is nonempty, closed under addition and has
the absorbing property. Since In ⊆ I for all n and In 6= ∅, I 6= ∅. Given
a, b ∈ I, there exists a j such that a ∈ Ij and there exists a k such that
b ∈ Ik . Setting ` = max{j, k}, we have a ∈ Ij ⊆ I` and b ∈ Ik ⊆ I` . Hence

6
a, b ∈ I` , and since I` is an ideal, a + b ∈ I` ⊆ I. Thus I is closed under
addition. Similarly, if a ∈ I, then a ∈ Ij for some j. Hence, for all r ∈ R,
ra ∈ Ij ⊆ I. Thus I is an ideal.

Returning to the proof of the theorem, given the S increasing sequence of

ideals (r1 ) ⊆ (r2 ) ⊆ · · · , the claim implies that I = i (ri ) is again an ideal of
R. Since R is a PID, I = (r) for some r ∈S R. Necessarily r ∈ (rN ) for some
N . But then (r) ⊆ (rN ) ⊆ (rN +1 ) · · · ⊆ i (ri ) = (r). Thus all inclusions
are equalities, and (rn ) = (rN ) for all n ≥ N , i.e. the sequence is eventually
constant. Hence R satisfies the hypotheses of the previous lemma, so that
every r ∈ R, not 0 or a unit, factors into a product of irreducibles.

The ascending chain condition and the arguments we have just given are
so fundamental that we generalize them as follows:

Proposition 1.22. For a ring R, not necessarily an integral domain, the

following two conditions are equivalent:

(i) Every ideal I of R is finitely generated: if I is an ideal of R, then

I = (r1 , . . . , rn ) for some ri ∈ R.

(ii) Every increasing sequence of ideals is eventually constant, in other

words if
I1 ⊆ I2 ⊆ · · · ⊆ In ⊆ In+1 ⊆ · · · ,
where the In are ideals of R, then there exists an N ∈ N such that for
all k ≥ N , Ik = IN .

If the ring R satisfies either of the equivalent conditions above, then R is

called a Noetherian ring.

S (i) =⇒ (ii): given an increasing sequence of ideals I1 ⊆ I2 ⊆ · · · , let

Proof.
I = n In . Then by the claim above, I is an ideal, and hence I = (r1 , . . . , rn )
for some ri ∈ R. Thus ri ∈ Ini for some ni . If N = maxi ni , then ri ∈ IN
for every i. Hence, for all k ≥ N , I = (r1 , . . . , rn ) ⊆ IN ⊆ Ik ⊆ I. It follows
that Ik = IN = I for all k ≥ N .
(ii) =⇒ (i): Let I be an ideal of R and choose an arbitrary r1 ∈ I (for
example, r1 could be 0). Set I1 = (r1 ). If I = I1 , stop. Otherwise there
exists an r2 ∈ I − I1 . Set I2 = (r1 , r2 ), and note that I2 strictly contains
I1 . If I = I2 , stop, otherwise there exists an r3 ∈ I − I2 . Inductively
suppose that we have found Ik = (r1 , . . . , rk ) with Ik ⊆ I. If I = Ik we are
done, otherwise there exists rk+1 ∈ I − Ik and we set Ik+1 = (r1 , . . . , rk+1 ).
So if I is not finitely generated, we have constructed a strictly increasing

7
sequence I1 ⊂ I2 ⊂ · · · , contradicting the assumption on R. Thus I is
finitely generated.

Example 1.23. Clearly, a PID satisfies (i) and hence a PID is Noetherian.
But there are many examples of Noetherian rings which are not PIDs. For
example, the Hilbert basis theorem states that, if R is Noetherian, then
so is R[x1 , . . . , xn ]. Thus Z[x1 , . . . , xn ] and F [x1 , . . . , xn ] are Noetherian
(where F is a field). It is also easy to see that R Noetherian =⇒ R/I is
Noetherian for every ideal I ⊆ R. Thus rings of the form Z[x1 , . . . , xn ]/I and
F [x1 , . . . , xn ]/I, which are the important rings arising in algebraic geometry
and number theory, are Noetherian.

By analyzing the proofs of the the above results, one can show:

Theorem 1.24. Suppose that R is a Noetherian integral domain. Then

every element r ∈ R, not 0 or a unit, factors into a product of irreducibles.
Moreover, the following are equivalent:

(i) R is a UFD.

(ii) If r ∈ R is irreducible, then (r) is a prime ideal.

2 Euclidean domains
We turn now to finding new examples of PID’s.

Definition 2.1. Let R be an integral domain. A Euclidean norm on R is a

function n : R − {0} → Z satisfying:

(i) For all r ∈ R − {0}, n(r) ≥ 0.

(ii) For all a, b ∈ R with a 6= 0, there exist q, r ∈ R with b = aq + r and

either r = 0 or n(r) < n(a).

An integral domain R such that there exists a Euclidean norm on R is

called a Euclidean domain.

Example 2.2. (1) R = Z, n(a) = |a|; (2) R = F [x], F a field, and n(f ) =
deg f , defined for f 6= 0; (3) R = F is a field, and n(a) = 0 for all a ∈
F − {0}. Here (3) is an easy exercise, and, for (1) and (2), Condition (i)
of the definition is clear and (ii) is the statement of long division in Z or in
F [x].

8
Remark 2.3. In the definition of a Euclidean norm, we do not require that
the q, r ∈ R are unique. In fact, uniqueness even fails in Z with the usual
norm if we allow q and r to be negative. For example, with a = 3, b = 11,
we can write 11 = 3 · 3 + 2 = 3 · 4 + (−1).

Proposition 2.4. If R is a Euclidean domain, then R is a PID.

Proof. This argument should be very familiar. Let I be an ideal of R. If

I = {0}, then I = (0) is principal. Otherwise, consider the nonempty set A
of nonnegative integers {n(r) : r ∈ I − {0}}. By the well-ordering principle,
there exists an a ∈ I − {0} such that n(a) is a smallest element of A. We
claim that I = (a). Clearly (a) ⊆ I since a ∈ I. Conversely, if b ∈ I, then
there exist q, r ∈ R such that b = aq + r with either r = 0 or n(r) < n(a).
As b, aq ∈ I, r = b − aq ∈ I. Hence n(r) < n(a) is impossible by the choice
of a, so that r = 0 and b = aq ∈ (a). Thus (a) ⊆ I and hence (a) = I.

Some remarks on submultiplicative Euclidean norms: We describe

some additional assumptions we can make for Euclidean norms (since many
authors add these to the definition).

Definition 2.5. The Euclidean norm n is submultiplicative if in addition

n satisfies: For all a, b ∈ R − {0}, n(a) ≤ n(ab). It is multiplicative if n
satisfies: For all a, b ∈ R − {0}, n(ab) = n(a)n(b). For R = Z, n(a) = |a|, or
R = F a field, and n(a) = 0 for all a ∈ F − {0}, n is multiplicative, whereas
deg : F [x] → Z is submultiplicative but not multiplicative.

Remark 2.6. In fact, a multiplicative norm is always submultiplicative.

If n is multiplicative and n(a) > 0 for all a ∈ R − {0}, then n is clearly
submultiplicative. Suppose that n(a) = 0 for some a. Then 1 = aq + r with
either n(r) < n(a) or r = 0. Since n(r) < 0 is impossible, r = 0, hence
1 = aq and a is a unit. For every b ∈ R − {0}, n(b) = n(a)n(a−1 b) = 0, and
then the above argument shows that n(b) = 0 as well. Thus n is identically
zero, and hence is submultiplicative in this case as well. Note that, if n is
multiplicative and n(a) = 0 for some a ∈ R − {0}, then n is identically 0
and R is a field.

Lemma 2.7. Let R be an integral domain and let n be a submultiplicative

Euclidean norm on R. For all b ∈ R − {0}, exactly one of the following
holds:

(i) b is not a unit, n(b) > n(1), and n(a) < n(ab) for all a ∈ R − {0}.

9
 (ii) b is a unit, n(b) = n(1), and n(a) = n(ab) for all a ∈ R − {0}.

Proof. We always have n(a) ≤ n(ab), and begin by showing that n(a) =
n(ab) ⇐⇒ b is a unit. First, if b is a unit, then n(a) ≤ n(ab) and
n(ab) ≤ n(abb−1 ) = n(a), so that n(a) = n(ab). Taking a = 1, we see that
n(b) = n(1). Conversely, suppose that n(a) = n(ab) for some a ∈ R − {0}.
Applying long division of ab into a, we se that a = (ab)q + r, with either
r = 0 or n(r) < n(ab) = n(a). We claim that r must be 0, since otherwise
r = a − abq = a(1 − bq) with 1 − bq 6= 0, and hence

n(a) ≤ n(a(1 − bq)) = n(r) < n(a),

a contradiction. Thus r = 0, so that a = abq and thus bq = 1, i.e. b is a

unit.

Corollary 2.8. Let R be an integral domain and let n be a submultiplicative

Euclidean norm on R. If r ∈ R − {0} and r = ab with neither a nor b a
unit, then n(a) < n(r) and n(b) < n(r).

For a Euclidean domain with a submultiplicative Euclidean norm, we can

give a direct argument for the existence of a factorization into irreducibles
(which we proved in Theorem 1.19 by a somewhat complicated argument):

Proposition 2.9. If R is a Euclidean domain with a submultiplicative Eu-

clidean norm n nd r ∈ R is not 0 or a unit, then r is a product of irreducibles.

Proof. Given r, not 0 or a unit, if r is irreducible we are done. Otherwise,

r = r1 r2 , with neither r1 nor r2 a unit. Hence n(ri ) < n(r), i = 1, 2. If ri is
irreducible for i = 1, 2, we are done. Otherwise at least one of r1 , r2 factors
into factors: say r1 = ab, with n(a) < n(r1 ) < n(r) and n(b) < n(r1 ) < n(r).
Clearly this process cannot continue indefinitely.
A more formal way to give this argument is as follows: if there exists an
r ∈ R, not 0 or a unit, which is not a product of irreducibles, then there
exists an r such that n(r) is minimal among all such, i.e. if s ∈ R is not 0,
a unit, or a product of irreducibles, then n(r) ≤ n(s), by the well-ordering
principle. But such an r cannot be irreducible (since a single irreducible is
by convention a product of one irreducible). So r = r1 r2 , with neither r1
nor r2 a unit, and so n(ri ) < n(r), i = 1, 2. But at least one of r1 and r2
is not a product of irreducibles, since if both r1 and r2 were a product of
irreducibles, then r1 r2 = r would also be a product of irreducibles. Say r1 is
not a product of irreducibles. Then by the choice of r, n(r) ≤ n(r1 ). This
contradicts n(r1 ) < n(r). Hence no such r can exist.

10
The Euclidean algorithm in a Euclidean domain: Let R be a Eu-
clidean domain with Euclidean norm n. Begin with a, b ∈ R, with b 6= 0.
Write a = bq1 + r1 , with q1 , r1 ∈ R, and either r1 = 0 or n(r1 ) < n(b).
Note that r1 = a + b(−q1 ) is a linear combination of a and b. If r1 = 0,
stop, otherwise repeat this process with b and r1 instead of a and b, so that
b = r1 q2 + r2 , with r2 = 0 or n(r2 ) < n(b) If r2 = 0, stop, otherwise repeat
again to find r1 , . . . , rk with n(r1 ) > n(r2 ) > n(r3 ) > · · · > n(rk ) ≥ 0,
with rk−1 = rk qk+1 + rk+1 . Since the integers n(ri ) decrease, and they are
all nonnegative, eventually this procedure must stop with an rn such that
rn+1 = 0, and hence rn−1 = rn qn+1 . The procedure looks as follows:

a = bq1 + r1
b = r1 q2 + r2
r1 = r2 q3 + r3
..
.
rn−2 = rn−1 qn + rn
rn−1 = rn qn+1 .

Then rn is a gcd of a, b and tracing back through the steps shows how to
write it as a linear combination of a and b.

3 Factorization in the Gaussian integers

We now consider factorization in the Gaussian integers

Z[i] = {a + bi : a, b ∈ Z}.

We shall show that Z[i] is a new example of a Euclidean domain, hence Z[i]
is a PID and a UFD. As a result, we shall describe which positive integers
are a sum of two integer squares.
Consider the function N : Z[i] → Z defined by N (α) = αᾱ, where if
α = a + bi, then ᾱ = a − bi (i.e. N (a + bi) = a2 + b2 ). Since α = α, clearly
N (α) = N (ᾱ). Note that, given n ∈ Z, n = N (α) for some α ∈ Z[i] ⇐⇒ n
is a sum of two integer squares.

Lemma 3.1. The function N satisfies:

(a) N (α) ≥ 0 for all α ∈ Z[i], and N (α) = 0 ⇐⇒ α = 0.

11
 (b) For all α, β ∈ Z[i], N (αβ) = N (α)N (β) (N is multiplicative). Hence,
if n1 and n2 are two integers which are each a sum of two integer
squares, then n1 n2 is a sum of two integer squares.

(c) N (α) = 1 ⇐⇒ α is a unit.

(d) There is an extension of N to a function Q(i) → Q, which we continue

to denote by N , defined by N (α) = αᾱ, and it satisfies (a) and (b).

Proof. (a) Clear. (b) N (αβ) = (αβ)(αβ) = (αβ)(ᾱβ̄) = αᾱβ β̄ = N (α)N (β).
(c) While this follows from (c) of Lemma 2.7, we can see this either directly
(N (α) = 1 ⇐⇒ α = ±1 or α = ±i) or as follows: if N (α) = 1, then αᾱ = 1
and hence α is a unit with α−1 = ᾱ. Conversely, if α is a unit, then αβ = 1
for some β ∈ Z[i], hence N (αβ) = 1 = N (α)N (β). Thus N (α) is a positive
integer dividing 1, so N (α) = 1. (d) Clear.

Proposition 3.2. In the integral domain Z[i], the function N (α) = αᾱ is
a multiplicative Euclidean norm.

Proof. Given α, β ∈ Z[i] with α 6= 0, we must show that we can find ξ, ρ ∈

Z[i] with β = αξ + ρ and ρ = 0 or N (ρ) < N (α). Consider the quotient
β/α ∈ Q[i]. Write β/α = r + si with r, s ∈ Q. Then there exist integers
n, m ∈ Z with |r − n| ≤ 12 and |s − m| ≤ 21 . Set ξ = n + mi and γ = β/α − ξ.
Then β = αξ + αγ = αξ + ρ, say, where ρ = αγ. Since ρ = β − αξ, ρ ∈ Z[i].
Moreover,
 2  2
2 2 1 1 1 1 1
N (γ) = N (β/α−ξ) = (r −n) +(s−m) ≤ + = + = < 1.
2 2 4 4 2
Then β = αξ + ρ with either ρ = 0 or

N (ρ) = N (αγ) = N (α)N (γ) < N (α).

Hence N is a Euclidean norm, and it is multiplicative by (b) of Lemma 3.1.

Corollary 3.3. Z[i] is a PID and a UFD.

Now that we know that Z[i] is a UFD, we can try to describe all of the
irreducibles in Z[i] and relate the answer to the problem of deciding when a
prime number p is a sum of two squares. The first step is:

Lemma 3.4. (i) If N (α) = p, where p is a prime number, then α is

irreducible.

12
 (ii) If p is a prime number, then p is not irreducible in Z[i] ⇐⇒ p = N (α)
for some α ∈ Z[i] ⇐⇒ p is a sum of two integer squares. In this case,
if α divides p and α is not a unit or an associate of p, then p = N (α)
and hence α is irreducible.

Proof. (i) If α = βγ, then p = N (α) = N (βγ) = N (β)N (γ), and so one of
N (β), N (γ) is 1. Hence either β or γ is a unit, so that α is irreducible.
(ii) If p is not irreducible, then p = αβ where neither α nor β is a
unit, hence N (α) and N (β) are both greater than 1. Then p2 = N (p) =
N (α)N (β), so that N (α) = N (β) = p, and α is irreducible by (i). Con-
versely, if p = N (α), then p = αᾱ with N (α) = N (ᾱ) = p, so that neither α
nor ᾱ is a unit. Hence p is not irreducible in Z[i].

Lemma 3.5. If π is an irreducible element of Z[i], then there exists a prime

number p such that π divides p in Z[i]. If the prime number p is also ir-
reducible in Z[i], then π and p are associates, so that π = ±p or ±ip. If
the prime number p is not irreducible in Z[i], then p = N (π) and every
irreducible factor of p is either an associate of π or an associate of π̄.

Proof. Consider N (π) ∈ Z. Since π is not a unit, N (π) > 1, and hence N (π)
is a product of prime numbers p1 · · · pr (not necessarily distinct). Since Z[i]
is a UFD and π is an irreducible dividing the product p1 · · · pr , there must
exist an i such that π divides pi , and we take p = pi . If p is also irreducible,
then π and p are associates, and hence π = ±p or ±ip. If p is not irreducible,
then we have seen that p = αᾱ for some α ∈ Z[i], where both α and ᾱ are
irreducible. Hence π divides p = αᾱ. It follows that π divides either α or ᾱ,
say π divides α, and hence that π is an associate of α since α is irreducible.
Since units have norm 1, it follows that N (π) = N (α) = p.

Note that 2 is not irreducible in Z[i], and in fact 2 = N (1 + i). The

irreducible factors of 2 are ±1 ± i, and they are all associates, since −1 − i =
(−1)(1 + i), 1 − i = (−i)(1 + i), and −1 + i = (i)(1 + i). Up to a unit, 2
is a square since 2 = (−i)(1 + i)2 (but it is not an actual square in Z[i]).
For other primes p of the form N (α) = αᾱ, this does not happen: For
any Gaussian integer α = a + bi, the associates of α are ±(a + bi) and
±i(a + bi) = ±(−b + ai). Hence, if a, b 6= 0, ᾱ = a − bi is an associate of
α ⇐⇒ a = ±b. If moreover α is irreducible, then since a|(a ± ai), a = ±1
and p = 2.
We may now describe the irreducibles in Z[i] as follows:

Theorem 3.6. The irreducible elements in Z[i] are:

13
 (i) 1 + i and its associates ±1 ± i;

(ii) Ordinary prime numbers p ∈ Z ⊆ Z[i] congruent to 3 mod 4 and their

associates ±p, ±ip;

(iii) Gaussian integers α = a + bi such that N (α) = a2 + b2 = p, where p

is a prime number congruent to 1 mod 4. Moreover, for every prime
number p congruent to 1 mod 4, there exists an α = a + bi such that
N (α) = a2 + b2 = p.

Proof. Let π be an irreducible in Z[i]. We have seen that either π is an

associate of a prime p which is irreducible in Z[i], or N (π) = p is a prime
number and that the irreducible factors of p are exactly the associates of π
or π̄. Moreover, 2 is not irreducible and the only irreducibles dividing 2 are
1+i and its associates. If p is an odd prime, p is not irreducible in Z[i] ⇐⇒
p = a2 + b2 , where a, b ∈ Z. Since p is odd, a and b cannot be both odd or
both even, so one of them, say a, is odd and the other, say b, is even. Then
a2 ≡ 1 mod 4 and b2 ≡ 0 mod 4, so that p = a2 + b2 ≡ 1 mod 4. In other
words, if p is an odd prime which is not irreducible in Z[i], then p ≡ 1 mod 4.
Hence, if p is an odd prime with p ≡ 3 mod 4, then p is irreducible in Z[i]
and its irreducible factors are its associates ±p, ±ip.
Thus we will be done if we show that every odd prime number congruent
to 1 mod 4 is not irreducible in Z[i], for then the remaining irreducibles of
Z[i] will be the nontrivial factors of p for such primes p, which are necessarily
irreducible and of norm p. To see this statement, we use the following:
Lemma 3.7. If p ≡ 1 mod 4, then there exists a k ∈ Z such that k 2 ≡
−1 mod p.

Proof. The assumption p ≡ 1 mod 4 is exactly the statement that 4|p − 1.

Now we know that (Z/pZ)∗ is a cyclic group of order p−1. By known results
on cyclic groups, there exists an element k of (Z/pZ)∗ of order 4. In other
words, k 4 = 1 in (Z/pZ)∗ but k 2 6= 1 in (Z/pZ)∗ . Since k 2 is then a root
of the polynomial x2 − 1 = (x + 1)(x − 1) in the field Z/pZ, we must have
k 2 = ±1, and since by assumption k 2 6= 1, k 2 = −1. This says that there is
an integer k such that k 2 ≡ −1 mod p.

To complete the proof of the theorem, if p ≡ 1 mod 4, then we shall show

that p is not irreducible in Z[i]. Let k ∈ Z be such that k 2 ≡ −1 mod p, so
that p divides k 2 + 1. In Z[i], we can factor k 2 + 1 = (k + i)(k − i). If p were

14
an irreducible, then since p divides k 2 + 1 = (k + i)(k − i), p would divide
one of the factors k ± i. But
k±i k 1
= ± i.
p p p

Since ±1/p is not an integer, the quotient (k ± i)/p does not lie in Z[i].
Hence p does not divide either factor k ± i of k 2 + 1, and so cannot be an
irreducible.

It follows that the prime numbers which are sums of two integer squares
are exactly the primes 2 and the odd primes ≡ 1 mod 4. The following
describes all positive integers which are sums of two integer squares:

Corollary 3.8. Let n ∈ N, n > 1, and write n = pa11 · · · par r , where the pi
are distinct prime numbers and ai ∈ N. Then n is a sum of two integer
squares if and only, for every prime factor pi of n such that pi ≡ 3 mod 4,
ai is even.

Proof. ⇐= : If n is as described, then every prime factor pi of n which is

either 2 or ≡ 1 mod p is a sum of two squares, hence so is pai i for an arbitrary
positive power ai . If pi ≡ 3 mod 4, then, if ai is even, pai i is also a square
since it is an even power. Thus n = pa11 · · · par r is a sum of two squares since
it is a product of factors, each of which is a sum of two squares.
=⇒ : Suppose that n is a sum of two squares. Then n = N (α) for
some α ∈ Z[i], not 0 or a unit. Factor α into a product of irreducibles:
α = uπ1b1 · · · πsbs , where u is a unit, the bi are positive integers, and πi is not
an associate . If πi is not an associate of a prime pi ≡ 3 mod 4, then N (πi ) is
either 2 or a prime ≡ 1 mod 4. If πi is an associate of a prime pi ≡ 3 mod 4,
then N (πi ) = p2i and thus N (πibi ) = p2b i
i . Hence

n = N (α) = (N (π1 ))b1 · · · (N (πs ))bs

is a product of prime powers with the property that all of the primes ≡
3 mod 4 occur to even powers. It follows that the prime factorization of n
is as claimed.

4 Examples where unique factorization fails

One can try to extend the above arguments
√ to more general classes of rings.
One natural ring to consider is Z[ −d], where d ∈ N. We usually assume
that d has no squared prime factors, in other words that either d = 1 or

15
 √ √
· · · pk is a product of distinct primes,
d = p1 √ √ since −a2 e = a −e. Note
that Z[ −d] is a subring of the field Q( −d),√which is called an imaginary
quadratic field. Similarly, we could look at Z[ √ d], where d ∈ N, d > 1, and
d has
√ no squared prime factors. In this case Z[ d] is a subring of the field
Q( d), which is called a real quadratic field. √
There √ is a natural
√ multiplicative function N : Z[ −d] → Z defined by, if
α = a + b −d ∈ Z[ −d],

N (α) = αᾱ = a2 + db2 .

Just as in the case d = 1, N is multiplicative,

√ i.e. N (αβ) = N (α)N (β), and
N extends to a function from√Q( −d) to Q which is a homomorphism of
multiplicative groups from Q( −d)∗ to Q∗ . Adapting the arguments in the
preceding section for Z[i], it is not hard to show:
√
Proposition 4.1. In the integral domain Z[ −2], the function N (α) = αᾱ
is a multiplicative Euclidean norm.
√
However, this fails for every d >√2: If d > 2, the norm N : Z[ −d] → Z
fails to be Euclidean, and in fact Z[ −d] is not a UFD.
√
Example
√ 4.2. The integral domain Z[ −3] is not a UFD. In fact, in
Z[ −3], √ √
4 = 2 · 2 = (1 + −3)(1 − −3).
√
We will show that √ 2 and 1 ± −3 are all irreducible, and that 2 is not an
associate√ of 1 ± −3. First, arguing as for Z[i], it is easy to check that
α√ ∈ Z[ −3] is a unit ⇐⇒ N (α) = 1. Now suppose that 2 factors in
Z[ −3]: say 2 = αβ. Then N (α)N (β) = N (2) = 4. If neither α nor β is
a unit, then
√ N (α) > 1 and N (β) > 1,2 hence N (α) = N (β) = 2. But if say
α = a + b −3 with a, b ∈ Z, then a + 3b = 2, hence b = 0√and a2 = 2,
2

which is impossible. Thus 2 is irreducible, √ and since N (1 ± −3) = 4 as

well,√a similar argument shows that 1 ± −3 is irreducible. Finally, 2√and
1 + √−3 are not associates,
√ since if they were,
√ then 2 √ would divide 1 + −3
in Z[√ −3]. But (1 + −3)/2 = 1/2 √ + (1/2) −3 ∈/
√ Z[ −3]. Likewise, 2 and
1 − −3 are not associates in Z[ −3]. Hence Z[ −3] is not a UFD.
√
This example is slightly misleading, because Z[ −3] is a subring of a
somewhat 2πi/3 =
1 1
√ more natural ring which is in fact a UFD: Let ω = e
− 2 + 2 −3 be a cube root of unity. Note that ω is a root of the monic
polynomial x2 +x+1, since ω is a root of x3 −1 and√ x3 −1 = (x−1)(x2 +x+1).
3 2 −1
Note that, since ω = 1, ω = ω = ω̄. Hence −3 = ω − ω 2 ∈ Z[ω], so

16
 √
that Z[ −3] is a subring of Z[ω]. More generally, we say that an α ∈ C
is an algebraic integer if α is a root of a monic polynomial with integer
coefficients, i.e. f (α) = 0, where f ∈ Z[x] is monic. (It is easy to see that
every algebraic number is a root of a polynomial f ∈ Z[x], but f is not
necessarily monic.) Them if E ≤ C is an algebraic extension of Q, one
can show that the set of algebraic integers in E is a subring of E whose
quotient field is E, and this ring plays the role of the subring Z of Q. For
E = Q(i),√ for example, the subring of algebraic integers is just Z[i], but for
E = Q( −3), the subring of algebraic integers is Z[ω]. In this particular
example, Z[ω] is in fact a PID and hence a UFD. In fact, one can use this
to give a fairly straightforward solution of Fermat’s Last Theorem for the
case p = 3: The only solutions in integers to the equation x3 + y 3 = x3 are
the trivial solutions, where one of x, y, z is 0.
However, unique√ factorization still turns out to be a rare occurrence.
For example,
√ Z[ −5] turns out to be the full subring of algebraic integers
in Q( −5), but it is easy to check that
√ √
6 = 2 · 3 = (1 + −5)(1 − −5)

gives a factorization of 6√ into a product of irreducibles in two essentially

different ways. Hence Z[ −5] is not a UFD, and hence it is not a PID.
More generally, a famous theorem due to Heegner-Stark says that there
is a finite (and relatively short) list of imaginary quadratic fields whose rings
of integers are UFD’s. It turns out that, for such a ring, being a UFD is
equivalent to being a PID. However, not every such PID is Euclidean. Hence,
the implications R Euclidean =⇒ R is a PID =⇒ R is a UFD are all
strict, in the sense that none of them is an ⇐⇒ statement. In other words,
there exist rings R which are a UFD but which are not a PID and there
exist rings R which are a PID but which are not Euclidean.
Much of the√above discussion carries over to real quadratic √ fields. For
example, for Z[ 2], we have a multiplicative function N : Z[ 2] → Z defined
by √
N (a + b 2) = |a2 − 2b2 |.
One can check that, at least in this case, N is a Euclidean norm. For general
real quadratic fields, one can define an analogous multiplicative function N ,
which will usually not however be a Euclidean norm. It is unknown if there
are finitely or infinitely many real quadratic fields whose rings of integers
are UFD’s.
More general rings along these lines are studied in algebraic number the-
ory. Historically, one major motivation was the attempt to prove Fermat’s

17
Last Theorem (which would be quite straightforward to prove if unique fac-
torization always held in such rings). Ideals were originally introduced in
this special context. If R is a UFD, then r is irreducible ⇐⇒ (r) is prime,
and (r) uniquely determines r up to associates. In general, nonzero prime
ideals can function to a certain extent as a substitute for irreducible ele-
ments. In fact, a basic theorem in algebraic number theory states that, if
R is a ring of algebraic integers (correctly defined), and I is an ideal of R,
with I 6= {0}, R, then I can be uniquely factored into a product of prime
ideals (where ideal products were defined in the HW).

18