Factorization in Integral Domains

The building blocks of the integers are the prime numbers. If \(F\) is a field, then irreducible polynomials in \(F[x]\) play a role that is very similar to that of the prime numbers in the ring of integers. Given an arbitrary integral domain, we are led to the following series of definitions.

Let \(R\) be a commutative ring with identity, and let \(a\) and \(b\) be elements in \(R\). We say that \(a\) divides \(b\), and write \(a \mid b\), if there exists an element \(c \in R\) such that \(b = ac\). 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\).

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\), either \(a\) or \(b\) is a unit. Furthermore, \(p\) is prime if whenever \(p \mid ab\) either \(p \mid a\) or \(p \mid b\).

Example

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

The Fundamental Theorem of Arithmetic states that every positive integer \(n \gt 1\) can be factored into a product of prime numbers \(p_1 \cdots p_k\), 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. We can easily extend this result to the integers. The question arises of whether or not such factorizations are possible in other rings. Generalizing this definition, we say an integral domain \(D\) is a unique factorization domain, or UFD, if \(D\) satisfies the following criteria.

Let \(a \in D\) such that \(a \neq 0\) and \(a\) is not a unit. Then \(a\) can be written as the product of irreducible elements in \(D\).
Let \(a = p_1 \cdots p_r = q_1 \cdots q_s\), where the \(p_i\)'s and the \(q_i\)'s are irreducible. Then \(r=s\) and there is a \(\pi \in S_r\) such that \(p_i\) and \(q_{\pi(j)}\) are associates for \(j = 1, \ldots, r\).

Example

The integers are a unique factorization domain by the Fundamental Theorem of Arithmetic.

Example

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 (, ). Let \(z = a + b \sqrt{3}\, i\) and define \(\nu : {\mathbb Z}[ \sqrt{3}\, i ] \rightarrow {\mathbb N} \cup \{ 0 \}\) by \(\nu( z) = |z|^2 = a^2 + 3 b^2\). It is clear that \(\nu(z) \geq 0\) with equality when \(z = 0\). Also, from our knowledge of complex numbers we know that \(\nu(z w) = \nu(z) \nu(w)\). It is easy to show that if \(\nu(z) = 1\), then \(z\) is a unit, and that the only units of \({\mathbb Z}[ \sqrt{3}\, i ]\) are \(1\) and \(-1\).

We claim that \(4\) has two distinct factorizations into irreducible elements: \[\begin{aligned}\end{aligned}\]. We must show that each of these factors is an irreducible element in \({\mathbb Z}[ \sqrt{3}\, i ]\). 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\). 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. Since \(2\) is not a unit multiple of either \(1 - \sqrt{3}\, i\) or \(1 + \sqrt{3}\, i\), \(4\) has at least two distinct factorizations into irreducible elements.

Principal Ideal Domains

Let \(R\) be a commutative ring with identity. Recall that a principal ideal generated by \(a \in R\) is an ideal of the form \(\langle a \rangle = \{ ra : r \in R \}\). An integral domain in which every ideal is principal is called a principal ideal domain, or PID.

Lemma

Let \(D\) be an integral domain and let \(a, b \in D\). Then

\(a \mid b\) if and only if \(\langle b \rangle \subset \langle a \rangle\).
\(a\) and \(b\) are associates if and only if \(\langle b \rangle = \langle a \rangle\).
\(a\) is a unit in \(D\) if and only if \(\langle a \rangle = D\).

Proof

(1) Suppose that \(a \mid b\). Then \(b = ax\) for some \(x \in D\). Hence, for every \(r\) in \(D\), \(br =(ax)r = a(xr)\) and \(\langle b \rangle \subset \langle a \rangle\). Conversely, suppose that \(\langle b \rangle \subset \langle a \rangle\). Then \(b \in \langle a \rangle\). Consequently, \(b =a x\) for some \(x \in D\). Thus, \(a \mid b\).

(2) Since \(a\) and \(b\) are associates, there exists a unit \(u\) such that \(a = u b\). Therefore, \(b \mid a\) and \(\langle a \rangle \subset \langle b \rangle\). Similarly, \(\langle b \rangle \subset \langle a \rangle\). It follows that \(\langle a \rangle = \langle b \rangle\). Conversely, suppose that \(\langle a \rangle = \langle b \rangle\). By part (1), \(a \mid b\) and \(b \mid a\). Then \(a = bx\) and \(b = ay\) for some \(x, y \in D\). Therefore, \(a = bx = ayx\). Since \(D\) is an integral domain, \(x y = 1\); that is, \(x\) and \(y\) are units and \(a\) and \(b\) are associates.

(3) An element \(a \in D\) is a unit if and only if \(a\) is an associate of \(1\). However, \(a\) is an associate of \(1\) if and only if \(\langle a \rangle = \langle 1 \rangle = D\).

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Euclidean Domains

We have repeatedly used the division algorithm when proving results about either \({\mathbb Z}\) or \(F[x]\), where \(F\) is a field. We should now ask when a division algorithm is available for an integral domain.

Let \(D\) be an integral domain such that there is a function \(\nu : D \setminus \{0\} \to \mathbb N_0 = \mathbb N \cup \{0\}\) satisfying the following conditions. \(\nu(a)\) Euclidean valuation of \(a\)

If \(a\) and \(b\) are nonzero elements in \(D\), then \(\nu(a) \leq \nu(ab)\).
Let \(a, b \in D\) and suppose that \(b \neq 0\). Then there exist elements \(q, r \in D\) such that \(a = bq + r\) and either \(r = 0\) or \(\nu(r) \lt \nu(b)\).

Then \(D\) is called a Euclidean domain and \(\nu\) is called a Euclidean valuation.

Example

Absolute value on \({\mathbb Z}\) is a Euclidean valuation.

Example

Let \(F\) be a field. Then the degree of a polynomial in \(F[x]\) is a Euclidean valuation.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Factorization in D\lbrack x \rbrack

One of the most important polynomial rings is \({\mathbb Z}[x]\). One of the first questions that come to mind about \({\mathbb Z}[x]\) is whether or not it is a UFD. We will prove a more general statement here. Our first task is to obtain a more general version of Gauss's Lemma ().

Let \(D\) be a unique factorization domain and suppose that \[\begin{aligned}\end{aligned}\] in \(D[x]\). Then the content of \(p(x)\) is the greatest common divisor of \(a_0, \ldots, a_n\). We say that \(p(x)\) is primitive if \(\gcd(a_0, \ldots, a_n ) = 1\).

Example

In \({\mathbb Z}[x]\) the polynomial \(p(x)= 5 x^4 - 3 x^3 + x -4\) is a primitive polynomial since the greatest common divisor of the coefficients is \(1\); however, the polynomial \(q(x) = 4 x^2 - 6 x + 8\) is not primitive since the content of \(q(x)\) is \(2\).

Theorem: Gauss's Lemma

Let \(D\) be a UFD and let \(f(x)\) and \(g(x)\) be primitive polynomials in \(D[x]\). Then \(f(x) g(x)\) is primitive.

Proof

Let \(f(x) = \sum_{i=0}^{m} a_i x^i\) and \(g(x) = \sum_{i=0}^{n} b_i x^i\). Suppose that \(p\) is a prime dividing the coefficients of \(f(x) g(x)\). Let \(r\) be the smallest integer such that \(p \notdivide a_r\) and \(s\) be the smallest integer such that \(p \notdivide b_s\). The coefficient of \(x^{r+s}\) in \(f(x) g(x)\) is \[\begin{aligned}\end{aligned}\]. Since \(p\) divides \(a_0, \ldots, a_{r-1}\) and \(b_0, \ldots, b_{s-1}\), \(p\) divides every term of \(c_{r+s}\) except for the term \(a_r b_s\). However, since \(p \mid c_{r+s}\), either \(p\) divides \(a_r\) or \(p\) divides \(b_s\). But this is impossible.

The following corollaries are direct consequences of .

The theorem that we have just proven has several obvious but important corollaries.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Historical Note

Karl Friedrich Gauss, born in Brunswick, Germany on April 30, 1777, is considered to be one of the greatest mathematicians who ever lived. Gauss was truly a child prodigy. At the age of three he was able to detect errors in the books of his father's business. Gauss entered college at the age of 15. Before the age of 20, Gauss was able to construct a regular \(17\)-sided polygon with a ruler and compass. This was the first new construction of a regular \(n\)-sided polygon since the time of the ancient Greeks. Gauss succeeded in showing that if \(N= 2^{2^n} + 1\) was prime, then it was possible to construct a regular \(N\)-sided polygon.

Gauss obtained his Ph.D. in 1799 under the direction of Pfaff at the University of Helmstedt. In his dissertation he gave the first complete proof of the Fundamental Theorem of Algebra, which states that every polynomial with real coefficients can be factored into linear factors over the complex numbers. The acceptance of complex numbers was brought about by Gauss, who was the first person to use the notation of \(i\) for \(\sqrt{-1}\).

Gauss then turned his attention toward number theory; in 1801, he published his famous book on number theory, Disquisitiones Arithmeticae. Throughout his life Gauss was intrigued with this branch of mathematics. He once wrote, Mathematics is the queen of the sciences, and the theory of numbers is the queen of mathematics.

In 1807, Gauss was appointed director of the Observatory at the University of Göttingen, a position he held until his death. This position required him to study applications of mathematics to the sciences. He succeeded in making contributions to fields such as astronomy, mechanics, optics, geodesy, and magnetism. Along with Wilhelm Weber, he coinvented the first practical electric telegraph some years before a better version was invented by Samuel F. B. Morse.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Symbols used here

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\sqrt{x},\ \sqrt[n]{x}

square root, n-th root
The non-negative number whose square (n-th power) is x.

\pi

pi
Ratio of a circle's circumference to its diameter, 3.14159…

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

A \cup B,\ A \cap B,\ A \setminus B

union, intersection, difference
In either; in both; in A but not B.

i

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

\neq

not equal
The two sides are different.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

Factorization in Integral Domains