Exploration 4: Factorization

December 4, 2023.

Questions:

When is a factorization unique?

To factor an element is to consider it as a product of other elements in the ring. For instance, in the ring of integers $\ZZ$ , the integer $6$ typically factors into $2\cdot 3$ . By multiplying both factors by the unit $-1$ , we obtain $-2\cdot -3$ as another valid factorization. Are these the only factorizations of $6$ (up to reordering)?

No — we also have $1\cdot 6$ and $-1\cdot -6$ . general, factorizations like $a=1a$ , or $a=u(u^{-1}a)$ (where $u$ is a unit) are trivial factorizations, because such factorizations exist in any ring and are therefore not interesting. So when we talk about factorizations we generally mean nontrivial factorizations, i.e. factorizations into nonzero non-units.

When an nonzero, non-unit element cannot be factored further because all of its factorizations are trivial, we call it an irreducible element, or simply an irreducible. Otherwise, the element is reducible.

Another way to define an irreducible element is the following:

Theorem: If an irreducible

a

factors into

bc

, then either

b

c

is a unit.

The fact that $a$ is irreducible means any factorization $bc$ is trivial, so either $b$ or $c$ is a unit.

In this section, we explore whether factorization terminates.

Let $a$ be a reducible element. If we repeatedly perform nontrivial factorizations on $a$ , we’d first obtain $a=bc$ . Then nontrivial factorizations of $b$ and $c$ gives us $a=(de)(fg)$ . Ideally this process terminates once there are no more nontrivial factorizations possible, i.e. all our factors are irreducibles. But does this process ever terminate?

$\begin{aligned} a_1&=a_2b_2&\text{ assume }a_2\text{ is reducible}\\ &=(a_3b_3)b_2&\text{ assume }a_3\text{ is reducible}\\ &=((a_4b_4)b_3)b_2&\text{ assume }a_4\text{ is reducible}\\ &=\ldots \end{aligned}$

With every step we shave off some nonzero non-unit factor $b_i$ . But nothing says that $a_i$ eventually becomes irreducible, and nothing says that this process must terminate. In fact, even if the ring is finite, it’s possible to find an infinite amount of factors $b_i$ that you can shave off from a given element $a_1$ . We’ll actually see an example of that later.

When we’re in an integral domain, there is a better way to characterize this process that avoids introducing extraneous variables like $b_i$ . We use a chain of inclusions of principal ideals — the above can be summarized as $(a_1)\subsetneq(a_2)\subsetneq(a_3)\subsetneq(a_4)\subsetneq\ldots$ The expression $(a_1)\subsetneq(a_2)$ says two things:

$(a_1)$ , being a subset of $(a_2)$ , implies $a_2\mid a_1$ , equivalent to our $a_1=a_2b_2$ above.
$(a_1)$ , being a proper subset of $(a_2)$ , means this $a_1=a_2b_2$ cannot be a trivial factorization, because in an integral domain $a_1,a_2$ differ by a unit $b_2$ if and only if $(a_1)=(a_2)$ .

Therefore the existence of this “ascending chain” of principal ideals expresses the existence of a sequence of nontrivial factorizations, exactly what we were expressing before with $a_i$ and $b_i$ . Then in order to ensure that the process of factoring $a_1$ terminates, we must guarantee that every such chain starting from $(a_1)$ is finite.

Expanding this guarantee to all elements in the ring results in a condition called the ascending chain condition on principal ideals (ACCP): the guarantee that there exists no infinite strictly ascending chain of principal ideals in the ring. If an integral domain satisfies the ACCP, then factorization always terminates, leaving you with a product of irreducibles.

Theorem: If a ring

R

satisfies the ACCP, then so does its polynomial ring

R[x]

Let $(f_1)\subsetneq(f_2)\subsetneq\ldots$ be an ascending chain of principal ideals in $R$ . WTS this chain is finite.
As mentioned previously, this is just a fancy way of saying $f_{i-1}=f_iq$ where $q$ is not a unit. For polynomial rings, where nonzero non-units are the non-constant polynomials, this means that $f_i$ divides $f_{i-1}$ in a way that decreases the degree of $f_{i-1}$ .
Since degree is finite and is strictly decreasing as you go up the chain, the chain must include an ideal generated by a polynomial of degree $0$ , i.e. a constant polynomial $c\in R$ .
But since $R$ satisfies ACCP, there cannot be an infinite ascending chain of ideals starting from $c$ , and therefore the inclusion of $(c)$ in the chain implies it is finite. Therefore $R[x]$ satisfies the ACCP.

If we are guaranteed that the process of factorization always terminates, then every (nonzero, nonunit) element $a$ can be factored into a product of irreducibles $\prod_i p_i$ (times some unit $u$ ). For this reason, integral domains for which ACCP holds are called factorization domains.

In this section, we briefly examine how zero divisors complicate factorization.

Our assumption above of being in an integral domain is in fact required, because the existence of zero divisors loses the guarantee that factorization terminates if the ring satisfies the ACCP.

The easiest example of this is when you have a nontrivial idempotent $e$ , a special zero divisor. In that case, we have $e=e\cdot e=e\cdot e\cdot e=e\cdot e\cdot e\cdot e=\ldots$ implying that $e$ factors into an infinite copies of itself, never reaching an irreducible element. Therefore the existence of a nontrivial idempotent shows that not every nonzero nonunit can be factored into a product of irreducibles, even if the ring satisfies the ACCP.

This makes integral domains, which have no zero divisors, particularly suited for nontrivial factorizations. Here’s one property that showcases this fact:

We can use this to prove a useful fact about irreducibles in an integral domain:

Corollary: In an integral domain, two elements

a,b

that differ by an element differ by a unique element

c

If $a=bc$ for some $c$ that is not unique, then there are at least two distinct factorizations $a=bc=bd$ , which isn’t possible in an integral domain as we just proved. Therefore $c$ is unique.

Corollary: In an integral domain, if two irreducible elements

a,b

differ by an element, then they differ by a unique unit

c

This is the above theorem combined with the fact that if $a=bc$ for some $c$ , then irreducibles only have trivial factorizations, and thus $c$ can only be a unnit.

In this section, we explore what is required to make factorizations unique.

Recall the fundamental theorem of arithmetic: “every integer greater than $1$ can be factored into a unique product of prime numbers.”

This statement mirrors the guarantee provided by factorization domains: every element can be factored into irreducibles. But is this factorization unique? In other words, does the fundamental theorem of arithmetic extend to all factorization domains? Let’s see:

Therefore: in a factorization domain, if every irreducible

p

dividing some product

\prod_i p_i

must divide one of the factors

p_i

, then factorization is unique (up to units).

Let $R$ be an factorization domain, i.e. an integral domain that satisfies the ACCP. Then every nonzero non-unit element $a\in R$ can be written as a product of irreducible elements $p_i$ (and a unit $u$ ): $a=u\prod_{i=1}^np_i$
Recall that in an integral domain, an irreducible element $b$ dividing a product $a$ implies that $a,b$ differ by a unique factor $c$ . That means if $a$ has two nontrivial factorizations that share a factor $p_1$ , then $a=p_1b$ , so they differ by a unique element $b$ . If this $b$ also has two nontrivial factorizations that share a factor $p_2$ , then $b=p_2c$ , so they differ by a unique element $c$ , and so on.
Thus if we enforce the property that every two factorizations of the same element must share a factor, then eventually this process stops at $1=1$ , where every factor $p_i$ must be unique, implying that factorizations are unique.

Note that in a factorization domain, every two factorizations $a=bc=bd$ share a factor $b$ iff they share some irreducible factor $p$ , so given $p$ , we have $a=pn$ for some unique $n$ . Then: $\begin{aligned} a&=pn\\ \iff bc&=pn\\ \end{aligned}$ Since $p$ is irreducible, it must be a factor of $b$ or of $c$ . Then the other factors ( $c$ or $b$ respectively) divide $n$ , so either $n=cc'$ or $n=bb'$ . $\begin{aligned} \iff bc=p(cc')&\quad\text{ or }\quad bc=p(bb')\\ \iff b=pc'&\quad\text{ or }\quad c=pb'\\ \iff p\mid b&\quad\text{ or }\quad p\mid c \end{aligned}$ So our original condition that two factorizations share a factor $b$ is equivalent to saying that if an irreducible factor $p$ divides a factorization $bc$ , then either $p$ divides $b$ or $p$ divides $c$ . $p\mid bc\implies p\mid b\text{ or }p\mid c$ When this condition holds for an element $p$ for all factorizations, we say that $p$ is prime.

Theorem: In an integral domain, if

p

is prime, then its only non-unit divisor is

p

Say that $q$ is a non-unit divisor of p, so $p=qr$ for some non-unit $r$ . Then $p\mid p$ implies $p\mid qr$ . By the prime property, either $p\mid q$ or $p\mid r$ .
If $p\mid q$ , then $p,q$ divide each other, meaning $q=p$ and we are done.
If $p\mid r$ , then $r=ps$ for some $s$ , meaning $p=q(ps)$ . Since we’re in an integral domain, we cancel $p$ on both sides to get $1=qs$ , implying that $q$ is a unit.

Thus if every irreducible in an factorization domain $R$ has this property (every irreducible is prime), then the fundamental theorem of arithmetic holds, thus factorization in $R$ is unique. When every irreducible is prime, we call $R$ a unique factorization domain (UFD).

In fact, this property is enough to show the converse of the fundamental theorem:

Theorem: UFDs are exactly the factorization domains in which every irreducible is prime.

( $\to$ $\to$ ): Assuming factorization is unique, we must show that for an irreducible $p$ $p$ , $p\mid ab$ $p ∣ ab$ implies $p\mid a$ $p ∣ a$ or $p\mid b$ $p ∣ b$ .
- If $p\mid ab$ , then we have $pq=ab$ for some $q$ .
- Let the unique factorizations of $a,b,q$ be $u_a\prod_i a_i,u_b\prod_i b_i,u_q\prod_i q_i$ respectively. Then $p\left(u_q\prod_i q_i\right)=\left(u_a\prod_i a_i\right)\left(u_b\prod_i b_i\right)$
- Since factorization is unique, $p$ appearing on the LHS implies it appears on the RHS as well (perhaps after multiplying by a unit). Then it will appear as either a factor $a_i$ or a factor $b_i$ .
- That means either $p\mid a$ or $p\mid b$ , and therefore the arbitrary irreducible $p$ is prime.
( $\from$ ): proved earlier.

In this section, we explore the ideals generated by irreducibles.

Before we get deeper into primes, let’s check out the ideals generated by irreducibles. One reason irreducibles are interesting is because they are exactly the elements that generate maximal principal ideals:

Theorem: In an integral domain, only the irreducible elements generate maximal principal ideals.

$(\to)$ $(\to)$ If $p$ $p$ is irreducible, WTS $(p)$ $(p)$ is a maximal principal ideal.
- $(p)$ is maximal among proper principal ideals if $(p)\subseteq (q)$ for some other proper principal ideal $(q)$ implies $(p)=(q)$ .
- $(p)\subseteq (q)$ means $p=qr$ for some $r$ , which must be a unit because $p$ is irreducible and $q$ (being in a proper ideal $(q)$ ) is not a unit. (proof) So we can write $q=r^{-1}p$ .
- But that means $(q)\subseteq (p)$ . Therefore $(p)=(q)$ and $(p)$ is indeed maximal among proper principal ideals.
$(\from)$ $(\leftarrow)$ If $(p)$ $(p)$ is a maximal principal ideal, then WTS $p$ $p$ is irreducible.
- We just need to show that whenever $p=qr$ , either $q$ or $r$ is a unit.
- If neither are units then we have $(p)=(qr)\subsetneq(q)$ (proof). Again since $q$ is not a unit, $(q)$ is a proper principal ideal. (proof)
- But then $(p)$ is not maximal since it is properly contained in a proper principal ideal, contradiction. Therefore either $q$ or $r$ is a unit, and so $p$ is irreducible.

Corollary: In a PID, irreducible elements are the elements that generate maximal ideals.

Recall that a principal ideal domain (PID) is one where every ideal is a principal ideal. They, too, are UFDs:

Theorem: Every PID is a UFD.

WTS PIDs satisfy the ACCP and thus are a factorization domain.
- In a PID, the union of any ascending chain of ideals $(a_1)\subsetneq(a_2)\subsetneq\ldots$ is a principal ideal $(a_n)$ .
- But this union contains every ideal in the chain, meaning all $(a_i)\subseteq(a_n)$ . Importantly, any ideal after $(a_n)$ in the chain must be equal to $(a_n)$ , and therefore any ascending chain of ideals cannot grow infinitely.
- Therefore PIDs satisfy the ACCP.
WTS every irreducible in a PID is prime, so that the PID is a UFD.
- Let $p$ be an irreducible and say $p=ab$ .
- Irreducibles are the elements that generate maximal principal ideals, so in particular, $(p)$ is maximal.
- Assume WLOG that $p\notmid a$ , so that proving $p\mid b$ is enough to show that $p$ is prime.
- Let $(p,a)$ be the ideal generated by $p$ and $a$ .
- If $p\notmid a$ , then $(p)\ne(p,a)$ . In fact, since $(p)$ is maximal and $(p,a)$ is strictly larger than $(p)$ , then $(p,a)$ must be the ideal $(1)$ which is the entire ring.
- In that case, some linear combination of $p$ and $a$ generates $1$ , so we have some $xp+ya=1$ for some $x,y$ . Multiply by $b$ to get $(xp)b+y(ab)=b$ , showing that $xp$ and $ab$ generate $b$ . But $p$ divides $xp$ and $ab$ , therefore $p$ divides any element they generate, including $b$ . Therefore $p$ is prime.

Corollary: Every polynomial ring over a field is a UFD.

Recalling that the integers $\ZZ$ are a PID, we get an interesting result: the integer polynomials form a UFD.

Lemma:

R

is a PID and

p

is prime iff

R/(p)

is a field.

Theorem: If

p

prime in

\ZZ

, then

\ZZ_p[x]

is a UFD.

Corollary:

R

is a PID and

p

is irreducible in

R

iff

R/(p)

is a field.

This is just a restatement of the above, since PIDs are UFDs and irreducibles are prime in UFDs.

In this section, we explore the ideals generated by primes.

Let’s first get a little more intuition of why prime ideals are called prime:

Theorem: Prime elements

p

generate prime principal ideals

(p)

We need to show that $ab\in (p)$ implies either $a\in (p)$ or $b\in (p)$ . $\begin{aligned} ab&\in (p)\\ ab&=kp&\text{ for some }k\\ p&\mid ab\\ p\mid a\quad~&\text{or }\quad p\mid b&\text{ because }p\text{ is prime}\\ a=k_1p\quad~&\text{or }\quad b=k_2p&\text{ for some }k_1,k_2\\ a\in(p)\quad~&\text{or }\quad b\in(p) \end{aligned}$ Therefore, $(p)$ is a prime ideal.

The converse holds in integral domains, with a similar proof.

Theorem: In an integral domain, all principal prime ideals

(p)

are generated by primes

p

Given $(p)$ is a prime ideal, we need to show that $p\mid ab$ implies $p\mid a$ or $p\mid b$ . $\begin{aligned} p&\mid ab\\ ab&=kp&\text{ for some }k\\ ab&\in (p)&\text{ since }kp\in (p)\\ a\in (p)\quad~&\text{or }\quad b\in (p)&\text{ because }(p)\text{ is a prime ideal}\\ a=k_1p\quad~&\text{or }\quad b=k_2p&\text{ for some }k_1,k_2\\ p\mid a\quad~&\text{or }\quad p\mid b \end{aligned}$

Corollary: In an integral domain, the principal prime ideals are exactly the ideals generated by primes.

Corollary:

p

is prime iff

R/(p)

is an integral domain.

We know that if every irreducible is prime, then we must be in a UFD. But when is every prime irreducible?

Theorem: Every prime is irreducible exactly when the ring is an integral domain.

If a prime $p$ is reducible to $p=ab$ , then $p\mid a$ or $p\mid b$ . WLOG assume $p\mid a$ , so $a=kp$ for some $k$ . Then: $\begin{aligned} p&=ab\\ p&=kpb\\ p-kpb&=0\\ p(1-kb)&=0\\ 1-kb&=0&\text{ since we're in an integral domain}\\ 1&=kb \end{aligned}$ implies that $b$ is a unit, and since $p=ab$ implies $b$ is a unit, $p$ is irreducible.

< Back to category Exploration 4: Factorization (permalink)
Exploration 3: Polynomials Exploration 5: Irreducibility