“Are you Judith’s project leader?” “The one and only. Project leader, analyst, and programmer, three roles, lots of work, and one biological, carbon-based, bipedal emotional organism that turns roasted beans’ beverage into undocumented code -start praying for the next developer,” I replied, Apocalypse, Anawim, #justtothepoint.
Recall. Let R be a commutative ring with unity and D an integral domain. An integral domain is a commutative ring with a multiplicative identity (1 ≠ 0) with no zero-divisors, that is, ab = 0 ⇒ a = 0 or b = 0.
A unique factorization domain is a ring in which a statement similar to the fundamental theorem of arithmetic holds. Specifically, a UFD is an integral domain in which every non-zero non-unit element can be written as a product of prime or irreducible elements uniquely up to order and multiplication by units. 💡In an integral domain every prime is irreducible.
Definition. We say an integral domain D is a unique factorization domain, UFD for short, if:
Definition. A ring R is said to satisfy the ascending chain condition, ACC for short, if for every set of ideals {I_{j}} such that I_{1} ⊆ I_{2} ⊆ I_{3} ⊆ ··· there exists N ∈ ℕ such that I_{n} = I_{N} for all n ≥ N. In other words, any strictly increasing chain of ideals must be finite.
Definition. A Noetherian domain is an integral domain satisfying the ascending chain condition, that is, any strictly increasing chain of ideals must be finite or, in other words, every ascending or increasing chain of ideals eventually stabilizes.
Lemma. Every principal ideal domain satisfies the ascending chain condition.
Proof.
Suppose D is a PID and {I_{j}} is a set of ideal such that I_{1} ⊆ I_{2} ⊆ I_{3} ⊆ ··· . Let I = $\cup_{j=1}^{∞}I_j$. We claim that this is an ideal.
Theorem. Every principal ideal domain, PID for short, is a unique factorization domain, UFD.
Proof.
Let’s prove factorization. Suppose a ∈ D that is a non-zero non-unit element. We will show that a is a product of irreducibles. We start by showing that a has at least one irreducible factor, that is a could be the product of only one irreducible factor.
Obviously, if a is irreducible, then we are done ∎
Recall. A non zero, non unit element a of an integral domain D is irreducible if when a = bc, then b or c is a unit. In other words, it cannot be written as a non trivial (except units) product of two elements of the ring.
Thus, we may assume that a = a_{1}b_{1} where neither a_{1} or b_{1} are units, and a_{1} is nonzero. If a_{1} is not irreducible, then a_{1} can be expressed as a product a_{1} = a_{2}b_{2} where neither a_{2} nor b_{2} is a unit and a_{2} is nonzero. And so on, and so forth…(Continuing with this process, we can construct an infinite ascending chain of ideals) a_{k} = a_{k+1}b_{k+1} ⇒ a_{1}|a, a_{2}|a_{1}, ···, a_{k+1}|a_{k} ⇒ [a|b ↭ ⟨b⟩ ⊆ ⟨a⟩] ⟨a⟩ ⊂ ⟨a_{1}⟩ ⊂ ⟨a_{2}⟩··· ⊂ ⟨a_{k}⟩··· ⇒ [D satisfies the ACC, this sequence stabilizes] ∃N ∈ ℕ: ⟨a_{N}⟩ = ⟨a_{N+1}⟩ = ⟨a_{N+2}⟩ = ··· ⇒ ⟨a⟩ ⊆ ⟨a_{1}⟩ ⊆ ⟨a_{2}⟩··· ⊆ ⟨a_{N}⟩ = ⟨a_{N+1}⟩ = ⟨a_{N+2}⟩ = ··· ⇒ ∀n ≥ N, ⟨a_{N}⟩ = ⟨a_{n}⟩ ⇒ [a and b are associates -one can be obtained from the other by multiplying by some unit, a = bu, u unit- ↭ ⟨b⟩ = ⟨a⟩] a_{N} and a_{n} are associates ∀n ≥ N ⇒ a = a_{1}b_{1} = a_{2}(b_{1}b_{2}) = ··· = a_{N}(b_{1}b_{2}···b_{N-1}) where a_{N} is an irreducible factor of a (we will rename it as p_{1}). We have already proved that every non-zero non-unit element in D has at least one irreducible factor.
Therefore, given a non-zero, non-unit element a ∈ D ⇒ a = p_{1}x_{1}, p_{1} irreducible and x_{1} is not a unit. If x_{1} is not irreducible, then we can write x_{1} = p_{2}x_{2}, where p_{2} is irreducible and x_{2} is not a unit. We continue this argument and we can obtain as before x_{k} = p_{k+1}x_{k+1}, where p_{k+1} is irreducible ⇒ Therefore, there’s an infinite ascending chain of ideals ⟨x_{1}⟩ ⊂ ⟨x_{2}⟩··· ⊂ ⟨x_{k}⟩··· ⇒ By the same argument as before, there exists r such that ∀n≥r: ⟨x_{n}⟩ = ⟨x_{r}⟩, that is, x_{r} is an irreducible factor, and a = p_{1}x_{1} = p_{1}p_{2}x_{2} = ··· = p_{1}p_{2}···p_{r}x_{r} where x_{r} and p_{i}, ∀i such that 1 ≤ i ≤ r are all irreducibles. Therefore, a has a prime factorization.
Let’s prove that the factorization is unique up to associates and the order in which all these factors appear.
Let’s suppose that an arbitrary element a ∈ D can be factored or written as two products of irreductibles, say a = p_{1}p_{2}···p_{r} = q_{1}q_{2}···q_{s} where the p_{i} and q_{j} are irreducible and we are going to demonstrate the uniqueness by induction on r.
Without loss of generalization, we could assume that r ≤ s.
As p_{1}|q_{1}, and they are both irreducibles, then u_{1}p_{1} = q_{1} where u_{1} is a unit of D, then u_{1}p_{1}p_{2}···p_{r} = u_{1}q_{1}q_{2}···q_{s} =[Commutative ring] q_{1}(u_{1}q_{2})···q_{s} ⇒ [u_{1}p_{1}=q_{1}, PID has cancellation laws] p_{2}···p_{r} = (u_{1}q_{2})···q_{s}
The induction hypothesis tells us that these two factorization are identical up to associates and the order in which the factor appear. Therefore r = s and there is a one-to-one correspondence between the irreducibles of these prime factorizations or in other words, this factorization is identical up to associates and the order in which the factors appear.
Corollary. Let F be a field. Then, F[x] is a unique factorization domain.
Proof. If F is field ⇒ F[x] is a principal ideal domain ⇒[Theorem. Every principal ideal domain, PID for short, is a unique factorization domain, UFD.] F[x] is a unique factorization domain.
Definition. An integral domain is known as a Euclidean domain if there is a mapping or function N (called the measure or the Euclidean function) from the nonzero elements of D to the natural numbers such that
It is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers, ∀a, b ∈ ℤ, b ≠ 0, ∃!q, r ∈ ℤ: a = bq + r, 0 ≤ r < |b|.
∀f(x), g(x) ∈ F[x], g(x) ≠ 0, deg(f(x)·g(x)) = deg(f(x)) + deg(g(x))≥ deg(g(x)). ∀f(x), g(x) ∈ F[x], f(x) ≠ 0, g(x) ≠ 0, ∃q(x), r(x)∈ F[x]: f(x) = g(x)q(x) + r(x), r(x) = 0 or 0 ≤ deg(r(x)) < deg(g(x)).
α, β ∈ Z[i] ⇒ αβ = $αβ\overline{αβ}=αβ\bar{α}\bar{β}=α\bar{α}β\bar{β}$ = N(α)N(β) [N(β) ≥ 1 if β ≠ 0, β ∈ ℤ] ≥ N(α)
α, β ∈ Z[i], β ≠ 0 ⇒ β is invertible in the complex numbers. α = a + bi, β = c + di, β^{-1} = $\frac{c-di}{c^2+d^2}=\frac{\bar{β}}{|β|^2}$
αβ^{-1} = $\frac{(a+bi)(c-di)}{c^2+d^2}=\frac{1}{c^2+d^2}((ac+bd)+(bc-ad)i)=\frac{ac+bd}{c^2+d^2}+\frac{bc-ad}{c^2+d^2}i=(q_1+r_1)+(q_2+r_2)i,~ where \frac{-1}{2}≤r_1,r_2≤\frac{1}{2}$ where q_{1}, q_{2} ∈ ℤ.
Recall that the ceiling is defined as the smallest integer that is larger or equal to x. The floor is defined as the largest integer that is smaller or equal to x, so x is between the floor of x, ⌊x⌋ and the ceiling of x, ⌈x⌉. Therefore, there are always two options, x = ⌊x⌋ + r_{1}, 0 ≤ r_{1} ≤ 1/2 or x = ⌈x⌉ + r_{1}, -1/2 ≤ r_{1} ≤ 0. In other words, ∀x ∈ ℤ, ∃x' ∈ ℤ: x = x' + r, $\frac{-1}{2}≤r≤\frac{1}{2}$
αβ^{-1} = (q_{1} + q_{2}i) + (r_{1} + r_{2}i), let us rename q_{1} + q_{2}i = γ ∈ ℤ[i]. Then, αβ^{-1} = γ + (r_{1} + r_{2}i) ⇒ α = βγ + β(r_{1} + r_{2}i) ⇒ [α and -β, γ ∈ ℤ[i]- βγ ∈ ℤ[i]] β(r_{1} + r_{2}i) ∈ ℤ[i], let’s rename it as ρ, so α = βγ + ρ
N(ρ) =[ρ = β(r_{1} + r_{2}i)] $β\bar{β}(r_1+r_2i)(r_1-r_2i)=N(β)(r_1^2+r_2^2)~ where \frac{-1}{2}≤r_1,r_2≤\frac{1}{2}⇒~0≤r_1^2,r_2^2≤\frac{1}{4}⇒ N(ρ) ≤ \frac{N(β)}{2} < N(β)$. Therefore, ∀α, β ∈ Z[i], β ≠ 0, ∃γ, ρ ∈ Z[i] such that α = βγ + ρ and N(ρ) < N(β) ∎
Exercise. The ring of integers $ℤ[\sqrt{2}]$ = {$a +b\sqrt{2} | a, b ∈ ℤ$} is an Euclidean Domain.
First, it is an integral domain since it is contained in ℝ.
Then, let’s define the map $ℤ[\sqrt{2}]$ → ℕ, ∀a +b$\sqrt{2},N(a +b\sqrt{2})=|a +b\sqrt{2}||a -b\sqrt{2}| =|a^2-2b^2|$
$N(a +b\sqrt{2})N(c +d\sqrt{2})=|(a +b\sqrt{2})(a -b\sqrt{2})||(c +d\sqrt{2})(c -d\sqrt{2})| = |(a +b\sqrt{2})(a -b\sqrt{2})(c +d\sqrt{2})(c -d\sqrt{2})| = |(a +b\sqrt{2})(c +d\sqrt{2})||(a -b\sqrt{2})(c -d\sqrt{2})| = |(ac + 2bd)+(ad + bc)\sqrt{2}||ac + 2bd −(ad+bc)\sqrt{2}| = N(ac+2bd+(ad+bc)\sqrt{2}) = N((a+b\sqrt{2})(c+d\sqrt{2}))$. As a consequence, if $β≠0 ⇒ N(αβ) = N(a +b\sqrt{2})N(c +d\sqrt{2}) = N(α)N(β) ≥[β ≠ 0 ⇒ N(β)>0]~ N(α)$
Let’s α, β ∈ $ℤ[\sqrt{2}], α = a +b\sqrt{2}, β = c +d\sqrt{2}$ where a, b, c, d ∈ ℤ.
αβ^{-1} = $\frac{a +b\sqrt{2}}{c +d\sqrt{2}}=\frac{a +b\sqrt{2}}{c +d\sqrt{2}}\frac{c -d\sqrt{2}}{c -d\sqrt{2}} = \frac{(ac-2bd)+(bc-ad)\sqrt{2}}{c^2-2d^2} = c_1 + c_2\sqrt{2},~ where~ c_1 = \frac{ac-2bd}{c^2-2d^2}, c_2 = \frac{bc-ad}{c^2-2d^2}$.
Let q_{1} and q_{2} be the closest integers to c_{1} and c_{2} respectively, that is, |c_{1} -q_{1}| ≤ ^{1}⁄_{2} and |c_{2} -q_{2}| ≤ ^{1}⁄_{2}. Now, let γ = q_{1} + q_{2}$\sqrt{2} ∈ ℤ[\sqrt{2}], θ = (c_1 -q_1) + (c_2 -q_2)\sqrt{2}, θ = \frac{α}{β}-γ$ ⇒ θβ = α -γβ ∈ ℤ[$\sqrt{2}$] because α, (β, γ∈ ℤ[$\sqrt{2}$] ⇒) γβ ∈ ℤ[$\sqrt{2}$]. Set δ = θβ, we have α = γβ + δ. Claim: N(δ)< N(β).
N(θ) =[Recall that $θ = (c_1 -q_1) + (c_2 -q_2)\sqrt{2}$] |$(c_1-q_1)^2-2(c_2-q_2)^2| ≤ |(c_1-q_1)^2| + |-2(c_2-q_2)^2| = (c_1-q_1)^2 + 2(c_2-q_2)^2 ≤ (\frac{1}{2})^2+2(\frac{1}{2})^2 = \frac{3}{4}$. In particular, N(δ) = N(θβ) = N(θ)N(β) ≤ ^{3}⁄_{4}N(β), that is, N(δ) < N(β).
Theorem. If D is a Euclidean Domain, then it is a principal ideal domain.
Proof.
Suppose I ⊆ D is an ideal. We claim that I is principal, i.e., ∃b ∈ D such that I = ⟨b⟩.
Let b an element of I such that N(b) is minimal amongst all elements from I. We immediately have ⟨b⟩ ⊆ I.
I ⊆ ⟨b⟩? Let a be an arbitrary element of our ideal I, a ∈ I, a ∈ ⟨b⟩? ⇒ [D is a Euclidean Domain] ∃q, r ∈D: a = bq + r with r = 0 or N(r) < N(b). There are “two” options:
Corollary. If D is a Euclidean domain, then it is a unique factorization domain.
Proof. ED ⇒[Previous Theorem. If D is a Euclidean Domain, then it is a principal ideal domain.] PID ⇒[Theorem. Every principal ideal domain, PID for short, is a unique factorization domain, UFD.] UFD.
Suppose for the sake of contradiction ℤ[$\sqrt{-5}$] is a PID (Principal Ideal domain), then I is generated by an element, say I = ⟨a+b$\sqrt{-5}⟩ ⇒ (i)~ 3 = α(a+b\sqrt{-5}),(ii)~ 2 + \sqrt{-5} =β(a+b\sqrt{-5})$ for some α, β ∈ R
It was previously demonstrated that N(xy) = N(x)N(y) and N(x) = 1 ↭ x = ± 1 because -5 ≠ 1 and -5 is not divisible by the square of a prime.
(i) $3 = α(a+b\sqrt{-5}) ⇒ N(3) = 9 = N(α)(a^2+5b^2)$ ⇒[$a^2+5b^2$ is a natural] $a^2+5b^2$ = 1, 3 or 9. Therefore, there are three options:
Therefore, ℤ[$\sqrt{-5}$] is not a PID (Principal Ideal domain) ⇒[Previous Theorem. If D is a Euclidean Domain, then it is a principal ideal domain.] it is not an Euclidean Domain.