Skip to main content

Section 6.2 Unique Factorization Domains

Let \(R\) be a commutative ring, and let \(a\) and \(b\) be elements in \(R\text{.}\) We say that \(a\) divides \(b\text{,}\) and write \(a \mid b\text{,}\) if there exists an element \(c \in R\) such that \(b = ac\text{.}\) A unit in \(R\) is an element that has a multiplicative inverse. Two elements \(a\) and \(b\) in \(R\) are said to be associates if there exists a unit \(u\) in \(R\) such that \(a = ub\text{.}\)

Let \(D\) be an integral domain. A nonzero element \(p \in D\) that is not a unit is said to be irreducible provided that whenever \(p = ab\text{,}\) either \(a\) or \(b\) is a unit. Furthermore, \(p\) is prime if whenever \(p \mid ab\) either \(p \mid a\) or \(p \mid b\text{.}\) Any prime element is irreducible.

Example 6.5.

Consider the ring of integers \(R = \mathbb Z\text{.}\) Then the units in \(\mathbb Z\) are just the elements \(1\) and \(-1\text{,}\) so an irreducible element \(p \in \mathbb Z\) is one whose only divisors are \(\pm 1\) and \(\pm p\text{.}\) In other words, \(p\) is either a prime integer or the negative of a prime integer.

Example 6.6.

It is important to notice that prime and irreducible elements do not always coincide. Let \(R\) be the subring of \({\mathbb Q}[x, y]\) generated by \(x^2\text{,}\) \(y^2\text{,}\) and \(xy\text{.}\) Each of these elements is irreducible in \(R\text{;}\) however, \(xy\) is not prime, since \(xy\) divides \(x^2 y^2\) but does not divide either \(x^2\) or \(y^2\text{.}\)

Suppose that \(a,b \in D\) and \(p\) divides \(ab\text{.}\) We want to show that \(p\) divides \(a\) or \(b\text{.}\) Assume that \(p\) doesn't divide \(a\text{.}\) Since \(p\) is irreducible, its only divisors are associates of \(p\) or units, and so a gcd of \(p\) and \(a\) must be a unit. By Theorem 6.4, there exist \(s, t \in D\) such that \(sp + ta\) is a unit. Multiplying by the inverse of this unit, we can assume that \(sp + ta = 1\text{.}\) Therefore, \(spb + tab = b\text{.}\) By assumption, \(p\) divides \(ab\text{,}\) and it clearly divides \(spb\text{,}\) so \(p\) divides \(b\text{,}\) which is what we wanted to show.

The Fundamental Theorem of Arithmetic states that every nonzero integer \(n \neq 0\) can be factored into a product of prime integers \(\pm p_1 \cdots p_k\text{,}\) where the \(p_i\)'s are not necessarily distinct. We also know that such factorizations are unique up to the order of the \(p_i\)'s. The question arises of whether or not such factorizations are possible in other rings. With the integers, we don't want to factor just into irreducible elements, which would allow both prime integers and their negatives, because that would give too many different ways to factor. Similarly, we factored polynomials over a field not just into irreducibles, but into monic irreducible polynomials.

In an arbitrary integram domain \(D\text{,}\) we say that a set \(S\) is a set of distinguished irreducibles if every element of \(S\) is irreducible and every irreducible in \(D\) is an associate of a unique element of \(S\text{.}\) We say an integral domain \(D\) is a unique factorization domain, or UFD, if there exists a set \(S\) of distinguished irreducibles in \(D\) satisfying the following criteria:

  1. Let \(a \in D\) be non-zero. Then \(a\) can be written as a product \(a = u p_1 \cdots p_r\text{,}\) where \(r \geq 0\text{,}\) \(u\) is a unit, and \(p_1, \ldots, p_r \in S\text{.}\)

  2. Let \(a = u p_1 \cdots p_r = u' q_1 \cdots q_s\text{,}\) where \(u\) and \(u'\) are units and \(p_i\)'s and the \(q_i\)'s are in \(P\text{.}\) Then \(u=u'\text{,}\) \(r=s\) and there is a one-to-one and onto function

    \begin{equation*} \pi \colon \{1,\ldots,r\} \rightarrow \{1,\ldots, r\} \end{equation*}

    such that \(p_j = q_{\pi(j)}\) for \(j = 1, \ldots, r\text{.}\)

Example 6.8.

The integers are a unique factorization domain by taking \(S\) to be the set of positive primes by the Fundamental Theorem of Arithmetic.

Example 6.9.

The ring of polynomials \(F[x]\text{,}\) over a field \(F\) is a unique factorization domain by Theorem 5.14, with \(S\) as the set of monic irreducible polynomials.

The following lemma shows that a ring can be a UFD for many different choices of the set of irreducibles.

Let \(a\) be any nonzero element of \(D\text{,}\) and then since \(D\) is a UFD with distinguished irreducibles, there exists a factorization \(a=up_1\cdots p_r\) with \(u\) a unit and \(p_1, \ldots,p_r \in S\text{.}\) Since \(S'\) is also distinguished set of irreducibles, each \(p_i\) is an associate of a \(p_i' \in S'\text{,}\) meaning that \(p_i = u_i p_i'\text{,}\) where \(u_i\) is a unit. Thus,

\begin{equation*} a = up_1 \cdots p_r = u (u_1 p_1') \cdots (u_r p_r') = (u u_1 \cdots u_r)p_1' \cdots p_r', \end{equation*}

which shows that \(a\) has a factorization as a unit times a product of elements of \(S'\text{.}\) This is the first part of the definition of a UFD with \(S'\) as the distinguished irreducibles.

Now suppose that \(a \in D\) is nonzero and \(a \in D\) can be factored as \(a=up_1' \cdots p_r'=v q_1' \cdots q_s'\text{,}\) where \(u\) and \(v\) are units and \(p_1',\ldots,p_r',q_1',\ldots,q_s'\) are elements of \(S'\text{.}\) Then, each \(p_i'\) and each \(q_j'\) is an associate of an element of \(S\text{,}\) so say that \(p_i' = u_ip_i\) and \(q_j' = v_jq_j\text{,}\) where \(u_1,\ldots,u_r,v_1,\ldots,v_s\) are units and \(p_1,\ldots,p_r,q_1,\ldots,q_s\) are in \(S\text{.}\) Then, after rearranging, similar to the previous case,

\begin{equation*} a = (uu_1\cdots u_r)p_1\cdots p_r = (v v_1\cdots v_s)q_1 \cdots q_s\text{.} \end{equation*}

By unique factorization, we have that \(r=s\) and there is a one-to-one and onto function \(\pi\) such that \(p_j = q_{\pi(j)}\text{.}\) Then, \(p_j'\) and \(q_{\pi(j)}'\) are both associates of \(p_j\text{,}\) but, since \(S'\) is a distinguished set of irreducibles, \(p_j'\) and \(q_{\pi(j)}'\) must be equal. In other words, \(p_1', \ldots,p_r'\) is a rearrangement of \(q_1', \ldots, q_r'\text{.}\) Also, since \(D\) is an integral domain, \(u\) must equal \(v\text{.}\) This completes the uniqueness part of \(D\) being a UFD with \(S'\) as the set of distinguished irreducibles.

Example 6.11.

Not every integral domain is a unique factorization domain. The subring \({\mathbb Z}[ \sqrt{3}\, i ] = \{ a + b \sqrt{3}\, i\}\) of the complex numbers is an integral domain (Exercise 4.5.5, Chapter 4). Let \(z = a + b \sqrt{3}\, i\) and define \(\nu \colon {\mathbb Z}[ \sqrt{3}\, i ] \rightarrow {\mathbb N} \cup \{ 0 \}\) by \(\nu( z) = |z|^2 = a^2 + 3 b^2\text{.}\) It is clear that \(\nu(z) \geq 0\) with equality when \(z = 0\text{.}\) Also, from our knowledge of complex numbers we know that \(\nu(z w) = \nu(z) \nu(w)\text{.}\) It is easy to show that if \(\nu(z) = 1\text{,}\) then \(z\) is a unit, and that the only units of \({\mathbb Z}[ \sqrt{3}\, i ]\) are 1 and \(-1\text{.}\)

We claim that \(2\text{,}\) \(1+\sqrt{3}\,i\text{,}\) and \(1-\sqrt{3}\,i\) are all irreducible. If 2 is not irreducible, then \(2 = z w\) for elements \(z, w\) in \({\mathbb Z}[ \sqrt{3}\, i ]\) where \(\nu( z) = \nu(w) = 2\text{.}\) However, there does not exist an element in \(z\) in \({\mathbb Z}[\sqrt{3}\, i ]\) such that \(\nu(z) = 2\) because the equation \(a^2 + 3 b^2 = 2\) has no integer solutions. Therefore, 2 must be irreducible. A similar argument shows that both \(1 - \sqrt{3}\, i\) and \(1 + \sqrt{3}\, i\) are irreducible. Moreover, \(2\text{,}\) \(1+\sqrt{3}\,i\text{,}\) and \(1-\sqrt{3}\,i\) are not associates of each other, so by Lemma 6.10, if \({\mathbb Z}[\sqrt{3}\,i]\) is a UFD, we can assume that all three irreducibles are in \(P\text{.}\) However, we have two distinct factorizations into elements of \(P\text{:}\)

\begin{equation*} 4 = 2 \cdot 2 = (1 - \sqrt{3}\, i) (1 + \sqrt{3}\, i). \end{equation*}

Therefore, \({\mathbb Z}[\sqrt{3}\,i]\) is not a UFD.

We first suppose that \(D\) is a unique factorization domain. By the first item in the definition of a UFD, every non-zero element \(x\) of \(D\) can be factored as \(x=up_1\cdots p_r\text{.}\) If \(x\) is not a unit, then \(r\) must be at least \(1\text{,}\) so \(x = (up_1) \cdots p_r\) is a factorization of \(x\) into irreducibles.

Now suppose that \(p\) is an irreducible element of a UFD \(D\) and we want to show that \(p\) is prime. Suppose that \(p\) divides \(ab\text{,}\) say \(pc = ab\text{.}\) From definition of a distinguished set of irreducibles, there is an associate of \(p\) in \(S\text{,}\) meaning that \(p = u_1 p'\) for \(u_1\) a unit and \(p' \in S\text{.}\) From the existence part of the definition of a UFD, we can factor \(a = u_2 q_1 \cdots q_n\text{,}\) \(b = u_3 r_1 \cdots r_m\text{,}\) and \(c = u_4 s_1 \cdots s_k,\) where \(u_1, u_2, u_3\) are units and \(q_1,\ldots,q_n,r_1,\ldots,r_m,s_1, \ldots, s_k\) are in \(S\text{.}\) Thus, \((u_1 p') (u_4 s_1 \cdots s_k) = (u_2 q_1 \cdots q_n)(u_3 r_1 \cdots r_m)\text{,}\) and by rearranging and regrouping the factors, we have that

\begin{equation*} (u_1 u_4) p' s_1 \cdots s_k = (u_2 u_3) q_1 \cdots q_n s_1 \cdots s_k\text{.} \end{equation*}

By the uniqueness part of the definition of a UFD, \(p'\) is equal to one of \(q_1, \ldots, q_n, r_1, \ldots, r_m\text{.}\) If \(p'\) equals one of one of \(q_1, \ldots, q_n\text{,}\) then \(p'\) divides \(a\) and since \(p' = u^{-1}p\text{,}\) \(p\) also divides \(a\text{.}\) If \(p'\) is equals one of \(r_q, \ldots, r_m\text{,}\) then \(p'\) divides \(b\text{,}\) and, so, similarly, \(p\) divides \(b\text{.}\) Since \(p\) divides either \(a\) or \(b\text{,}\) then \(p\) is prime.

To show the converse, we suppose that every non-unit in \(D\) has a factorization into irreducibles, and every irreducible element of \(D\) is prime. Let \(S\) be any set consisting of one representative from each equivalence class of irreducibles up to associates, which will be our distinguished class of irreducibles. Any unit satisfies existence part of a UFD with \(r=0\text{.}\) Let \(x \in D\) be a non-unit. By assumption, \(x\) can be written as a product of irreducibles \(x=p_1 \cdots p_n\text{.}\) Since each \(p_i\) is an associate of an irreducible in \(S\text{,}\) we can write \(p_i = u_i q_i\text{,}\) where \(u_i\) is a unit and \(q_i \in S\text{.}\) Thus, \(x=(u_1 \cdots u_n)q_1 \cdots q_n\text{,}\) which is a product of a unit and elements of \(S\text{,}\) as in the definition of a UFD.

Let \(a = u p_1 \cdots p_r = u' q_1 \cdots q_s\) be two different factorizations of an element \(a \in D\) with \(u\) and \(u'\) units and \(p_1, \ldots, p_r,q_1,\ldots, q_s \in S\text{.}\) We use induction on \(r\text{.}\) If \(r = 0\text{,}\) then \(u = u' q_1 \cdots q_s\text{,}\) but since irreducible elements can't divide a unit, then \(s = 0\) as well. Now suppose that \(r > 0\text{.}\) By assumption, the irreducible \(p_1\) is prime, and it can't divide \(u'\text{,}\) so \(p_1\) must divide \(q_i\) for some \(i\text{.}\) If we write \(q_i = b p_1\text{,}\) then, since \(q_i\) is irreducible, \(b\) must be a unit, so \(p_1\) and \(q_i\) are associates, and since both are in \(S\text{,}\) then \(p_1 = q_i\text{.}\) Now, by dividing by \(p_1=q_i\text{,}\) we have \(u p_2 \cdots p_r = u' q_1 \cdots q_{i-1} q_{i+1} \cdots q_s\text{.}\) By our inductive hypothesis, \(r-1 = s-1\text{,}\) and, after reordering, \(p_2, \ldots, p_r\) are associates of \(q_1,\ldots, q_{i-1}, q_{i+1}, \ldots q_s\text{.}\) Therefore, \(r = s\text{,}\) an, after reordering \(p_1, \ldots, p_r\) are associates of \(q_1, \ldots, q_s\text{.}\)

Any irreducible element is prime by Proposition 6.7 and we leave it as an exercise to prove that any non-unit in a Euclidean domain can be factored into irreducibles.

Suppose that \(a = bc\) and factor \(b\) and \(c\) as \(b=v q_1 \cdots q_k\) and \(c = w q_{k+1} \cdots q_{m}\) where \(v\) and \(w\) are units and \(q_1,\ldots,q_m\) are in \(P\text{.}\) Then, \(bc=vwq_1 \cdots q_m\text{,}\) so, by unique factorization, \(n=m\) and there exists a bijective function \(\pi \colon \{1, \ldots, n\} \rightarrow \{1, \ldots, n\}\) such that \(q_i=p_{\pi(i)}\text{.}\) Let \(I = \pi(\{1, \ldots, k\})\) and then:

\begin{equation*} b = v q_1 \cdots q_k = v p_{\pi(1)} \cdots p_{\pi(k)} = v \prod_{i \in I} p_i\text{,} \end{equation*}

which is what we wanted to show.

Clearly, \(d\) is a divisor of both \(a\) and \(b\) and so \(d\) is a common divisor of \(a\) and \(b\text{.}\)

Now suppose that \(d'\) is a common divisor of \(a\) and \(b\text{.}\) By Lemma 6.14, \(d' = u \prod_{i \in I}p_i = u' \prod_{j \in J} q_i\) for some subsets \(I \subset \{1, \ldots, n\}\) and \(J \subset \{1, \ldots, m\}\text{.}\) By unique factorization, there exists a bijective function \(\sigma\colon I \rightarrow J\) such that \(p_i\) equals \(q_{\sigma(i)}\text{.}\) If \(i \in I\) is greater than \(s\text{,}\) then \(p_i\) is not equal to \(q_j\) for any \(j\gt s\text{.}\) Therefore, for each \(k \in I\) such that \(p_k=p_i\text{,}\) \(\sigma(k)\) must be less than or equal to \(s\text{,}\) and we can replace each \(k \in I\) such that \(p_k=p_i\) with \(\sigma(k)\) because \(p_{\sigma(k)}=q_{\sigma(k)}=p_k=p_i\text{.}\) We repeat this replacement for each \(i \in I\) such that \(i\gt s\text{.}\) Then, we see that \(d' = u\prod_{i \in I}p_i\) is a divisor of \(d = p_1 \cdots p_s\text{.}\) Since any common divisor of \(a\) and \(b\) is a divisor of \(d\text{,}\) \(d\) is a greatest common divisor of \(a\) and \(b\text{.}\)