
Arithmetic in a Principal Ideal Domain
We have seen that Z is a unique factorization domain and also a principal ideal domain. On the other hand, Z[] is not a unique factorization domain and not a principal ideal domain. Our main result in this section will be the following theorem.
Theorem 1: Let R be a principal ideal domain. Then R is a unique factorization domain.
Let us begin by developing the theory of divisibility in an integral domain. Throughout this section, let R be an integral domain. If a,b R, then we say that a divides b (denoted ab) if b = xa for some x R. If a does not divide b, we write a b. The elementary facts about divisibility are summarized in the following result:
Lemma 2: Let a,b,c R. Then:
(1) ab, bc ac.
(2) ab abc for all c R.
(3) ab, ac ab+c.
(4) ab, ac abx + cy for all x,y R.
(5) Let b 0. Then ab, ba a and b are associates.
Proof:
(1) b = xa, c = yb c =(xy)a ac.
(2) b = xa bc = (xc)a abc.
(3) b = xa, c = ya b + c = (x + y)aab + c.
(4) By (ii) and (iii), abx, acy abx + cy.
(5) b = xa, a = yb b = (xy)b b(1xy) = 0 1xy = 0 since b0 and since R is an integral domain xy = 1 x is a unit of R a a b are associates since b = xa.
It is possible to formulate the notion of divisibility in terms of ideals. For if ab, then b = xa b (a) by (a) for all y R (b) (a). Conversely, if (b) (a), then b (a), so that b = xa and ab. Thus we have
(1)
ab if and only if (b) (a).
Lemma 3: Let a,b R. Then a and b are associates if and only if (a) = (b).
Proof: If a and b are associates, a = b, where is a unit of R. Therefore, b = ^{1}a, so that ba and ab. Thus by (1),
(a) (b), (b) (a).
(a) = (b).
Suppose that (a) = (b). Then by (1), we have ab and ba, so that a and b are associates by Lemma 2,part(5).
Definition 4: Let a,b R. A greatest common divisor (g.c.d) of a and b is an element c of R having the following properties:
(1) ca, cb.
(2) If d R is such that da and db, then dc.
In the case R = Z, Definition 4 is essentially the same as the definition of g.c.d. that was given in the section on integers. There is one small difference, however. Earlier, we required that a g.c.d. be positive. In a general ring, the notion of positivity makes no sense, and therefore we cannot include the condition of positivity in Definition 4. Therefore, if a = 3, b = 6, then (a,b) = 3 using the earlier definition, whereas both 3 and 3 are g.c.d's in the sense of Definition 4. Note that 3 and 3 are associates. This is not an accident.
Lemma 5: Let a,b R, and let c and c' be two g.c.d.'s of a and b. Then c and c' are associates.
Proof: Since ca and cb, and since c' is a g.c.d. condition (2) of Definition 4 implies that cc'. Reversing the roles of c and c', we see that c'c. If c = 0, then c' = 0 and the lemma holds. If c0, then Lemma 2, part (5) implies that c and c' are associates.
Thus, we see that if c_{0} is a g.c.d. of a and b, then all g.c.d's of a and b are of the form c_{0}, where is a unit of R.
Definition 6: Let a,b R. We say that a and b are relatively prime, denoted (a,b) = 1, if 1 is a g.c.d of a and b.
In an arbitrary integral domain R, it is not usually true that every pair of elements a,b R have a g.c.d. However, if R is a PID, then no pathologies occur and g.c.d's exist.
Proposition 7: Let R be a principal ideal domain and let a,b R, a and b not both 0. Then a and b have a g.c.d in R.
Proof: Let I = (a,b). Since R is a PID, I = (c) for some c R. Moreover, since a and b are not both 0, I(0), so that c 0. Let us show that c is a g.c.d. of a and b. Since a,b I, we see that a = cx, b = cyca, cb (1). Suppose d R such that da and db. Since I = (a,b) = {ax + by  x,y R}, we have c = ax + by for some x,y R. But then by Lemma 2 part (4), we have dax+by dc.
Corollary 8: Let R be a PID, and let a,b R, a, b not both 0. Then every g.c.d of a and b can be written in the form ax + by for some x,y R. In particular, if a and p are relatively prime, then there exist x,y R such that ax + by = 1.
In the case of integers, we proved that if p is prime and a and b are integers such that pab, then either pa or pb. Let us generalize this result to a PID.
Theorem 9: Let R be a principal ideal domain and let a,b R. Let be an irreducible element of R such that ab. Then either a or b.
Proof: Let us assume that does not divide a. We must then show that b. Since is irreducible, 0 and thus and a must have a g.c.d by Proposition 7. But  so that is either an associate of or a unit of R. In the former case, a since a. And this contradicts our assumption. Therefore, is a unit of R and ^{1} is a g.c.d of and a, since ^{1} is a unit of R. But then by Corollary 8, there exist x,y R such that
x + ay = 1.
Thus we see that (bx) + (ab)y = b. However  and ab. so that by Lemma 2, part(4), we see that bx + aby so that b.
Corollary 10: Let R be a PID, a_{1},...,a_{n} R, and irreducible element of R. If a_{1}··· a_{n}, then a_{i} for some i.
We now come the the proof of Theorem 1. Our proof will be divided into two parts. First we will show that if x R^{x}, x U_{R}, then x can be written as a product of irreducible elements. Second, we will show that the expression of x a product of irreducible elements is unique up to order and multiplication of the irreducible elements by units.
Theorem 11: Let x R^{x}, x U_{R}. Then x can be written as a product of irreducible elements.
Proof: Let us reason by contradiction. Assume that x cannot be written a product of irreducible elements. In particular, x is not irreducible, so that we may write
x = a _{1}b _{1}, a _{1},b _{2} not units.
Either a_{1} of b_{1} cannot be written as irreducible elements. For otherwise, x could be so written. Thus suppose that a_{1} is not a product of irreducible elements. Since x = a_{1}b_{1}, we see that a_{1}x and thus (a_{1}) (x) by (1). Moreover, since b_{1} is not a unit, (a_{1})(x) by Lemma 3. Thus, (x) is not properly contained in (a_{1}). Let us denote this fact by (a_{1}) (x). Note that a_{1} R^{x}, a_{1} U_{R}, and a_{1} cannot be written as a product of irreducible elements. Thus we can apply the same reasoning to a_{1} as we did to x to find a_{2} R^{x}, a_{2} U_{R}, a_{2} not equal to a product of irreducible elements, and (a_{2}) (a_{1}). Let us proceed in this way and construct a_{3},a_{4}, a_{5},.... We eventually arrive at the following chain of ideals
(2)
(a _{0}) (a _{1}) (a _{2}) ...,
where a_{0} = x. Set
(3)
I = (a _{i}).
Let us prove that I is an ideal of R. Let a,b I. Then a (a_{i}), b (a_{j}) for some i and j. Let j > i. Then (a_{i}) (a_{j}) and a,b (a_{j}). But since (a_{j}) is an ideal a±b (a_{j}), so that a±b I. Thus I is an additive subgroup of R. A similar argument shows that I is closed with respect to multiplication by elements of R. This shows that I is an ideal of R. Since R is a PID, I = (a) for some a R. Now a I, so that a (a_{k}) for some k. Therefore, (a) (a_{k}). However, (a_{k}) I = (a), so that (a) = (a_{k}). In particular, (a_{k+1}) (a_{k}) by (3). But this is a contradiction to (2), which asserts that (a_{k}) (a_{k+1}).
Theorem 12: Let x R^{x}, x U_{R} and let
x = _{1}... _{s} = _{1}... _{t}
be two expressions of x as a product of irreducible elements. Then s = t and by renumbering _{1},...,_{s}, we can guarantee that _{i} and _{i} are associates (1 < i < s).
Proof: If s = 1, then x is irreducible and the assertion is clear. Assume that s > 1 and let us proceed by induction on s. Since _{1}x, we see that _{1}..._{t}. Therefore, by Corollary 10, _{1}_{i} for some i (1 < i < t). by renumbering _{1},...,_{t}, we may assume that i = 1, so that _{1}_{1}. But since _{1} is irreducible and _{1} is not a unit we see that _{1} and _{1} are associates, say _{1} = _{1}, U_{R}. Therefore,
_{1}... _{s} = _{1}_{2}... _{t},
_{1}( _{2}... _{s} _{2}... _{t}) = 0,
Set _{2}' = _{2}, _{3}' = _{3},,...,_{t}' = _{t}. Then _{i}' and _{i} are associates and _{2}..._{s} = _{2}..._{t}' are two decompositions of _{2}..._{s} into irreducible factors. Therefore by the induction hypothesis, s  1 = t  1 and after renumbering _{2}'..._{t}', we can guarantee _{i} and _{i}' are associates (2 < i < s). But then s = t and _{i} and _{i} are associates (1 < i < s). Thus the induction step is established.
We showed in the previous section that if F is a field and X is an indeterminate over F, then F[X] is a PID. Therefore by Theorem 1, we see that F[X] is a UFD. Let us see exactly what this says: The units of F[X] are just the nonzero constant polynomials. Therefore f F[X] is a nonzero, nonconstant polynomial, then f can be written in the form
(4)
f = f_{1}...f_{t},
where f_{i} F[X] is an irreducible polynomial. Moreover, the decomposition (4) is unique up to a rearrangement and multiplication of the f_{i} by constants. Let f = a_{n}X^{n} + a_{n1}X^{n1} + ... + a_{0}, a_{n} 0> Then a_{n} is called the leading coefficient of f. If f has a leading coefficient 1, then we say that f is monic. It is clear that a nonzero polynomial g = b_{m}X^{m} + ... + b_{0}, b_{m}0 can be written as the product of a constant and a monic polynomial:
g = b_{m}(X^{m} + b_{m}^{1}b_{m1}X^{m1}+...+b_{m}^{1}b_{0}).
Therefore we can write
(5)
f = af_{1}^{*}...f_{t}^{*},
where a is a constant and f_{i}^{*} is monic and irreducible. By comparing leading coefficients on both sides of (5), we see that a = a_{n}.
Proposition 13: Let F be a field, X an indeterminate over F, f a nonzero, nonconstant polynomial in F[X], a the leading coefficient of f. Then f can be written in the form
f = af_{1}^{*}...f_{t}^{*},
where f_{i}^{*} is an irreducible, monic polynomial. Moreover, this decomposition is unique up to the order of the f_{i}^{*}.
Proof: All that must be proved is the uniqueness. Let
f = af_{1}^{*}...f_{t}^{*} = ag_{1}^{*}...g_{s}^{*},
be two decompositions of f, where f_{i}^{*} and g_{i}^{*} are irreducible and monic. Since F[X] is a UFD, we have s = t and may renumber f_{1}^{*},...f_{t}^{*} so that f_{i}^{*} and g_{i}^{*} are associates (1 < i < s). But since f_{i}^{*} and g_{i}^{*} are both monic, f_{i}^{*} = g_{i}^{*}.
