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 a|b) 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) a|b, b|c a|c.

(2) a|b a|bc for all c R.

(3) a|b, a|c a|b+c.

(4) a|b, a|c a|bx + cy for all x,y R.

(5) Let b 0. Then a|b, b|a a and b are associates.

Proof:

(1) b = xa, c = yb c =(xy)a a|c.

(2) b = xa bc = (xc)a a|bc.

(3) b = xa, c = ya b + c = (x + y)aa|b + c.

(4) By (ii) and (iii), a|bx, a|cy a|bx + cy.

(5) b = xa, a = yb b = (xy)b b(1-xy) = 0 1-xy = 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 a|b, 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 a|b. Thus we have

a|b 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 = ^-1a, so that b|a and a|b. Thus by (1),

(a) (b),     (b) (a).

(a) = (b).

Suppose that (a) = (b). Then by (1), we have a|b and b|a, 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) c|a, c|b.

(2) If d R is such that d|a and d|b, then d|c.

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 c|a and c|b, and since c' is a g.c.d. condition (2) of Definition 4 implies that c|c'. 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₀ is a g.c.d. of a and b, then all g.c.d's of a and b are of the form c₀, 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 = cyc|a, c|b (1). Suppose d R such that d|a and d|b. 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 d|ax+by d|c.

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 p|ab, then either p|a or p|b. 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₁,...,a_n R, and irreducible element of R. If |a₁··· 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₁b₁,     a₁,b₂ not units.

Either a₁ of b₁ cannot be written as irreducible elements. For otherwise, x could be so written. Thus suppose that a₁ is not a product of irreducible elements. Since x = a₁b₁, we see that a₁|x and thus (a₁) (x) by (1). Moreover, since b₁ is not a unit, (a₁)(x) by Lemma 3. Thus, (x) is not properly contained in (a₁). Let us denote this fact by (a₁) (x). Note that a₁ R^x, a₁ U_R, and a₁ cannot be written as a product of irreducible elements. Thus we can apply the same reasoning to a₁ as we did to x to find a₂ R^x, a₂ U_R, a₂ not equal to a product of irreducible elements, and (a₂) (a₁). Let us proceed in this way and construct a₃,a₄, a₅,.... We eventually arrive at the following chain of ideals

(2)

(a₀) (a₁) (a₂) ...,

where a₀ = 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 = ₁..._s = ₁..._t

be two expressions of x as a product of irreducible elements. Then s = t and by renumbering ₁,...,_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 ₁|x, we see that |₁..._t. Therefore, by Corollary 10, ₁|_i for some i (1 < i < t). by renumbering ₁,...,_t, we may assume that i = 1, so that ₁|₁. But since ₁ is irreducible and ₁ is not a unit we see that ₁ and ₁ are associates, say ₁ = ₁, U_R. Therefore,

₁..._s = ₁₂..._t,

₁(₂..._s-₂..._t) = 0,

₂..._s = ₂..._t since R is an integral domain.

Set ₂' = ₂, ₃' = ₃,,...,_t' = _t. Then _i' and _i are associates and ₂..._s = ₂..._t' are two decompositions of ₂..._s into irreducible factors. Therefore by the induction hypothesis, s - 1 = t - 1 and after renumbering ₂'..._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₁...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_nXⁿ + a_n-1X^n-1 + ... + a₀, 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_mX^m + ... + b₀, b_m0 can be written as the product of a constant and a monic polynomial:

g = b_m(X^m + b_m^-1b_m-1X^m-1+...+b_m^-1b₀).

Therefore we can write

(5)

f = af₁^*...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₁^*...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₁^*...f_t^* = ag₁^*...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₁^*,...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^*.