Unique Factorization

Sps. there exists an integer $N$ such that it is the smallest positive integer that cannot be expressed as the product of primes. It follows that $N$ cannot be prime itself, so there must exist $1 \lt m, n \lt N$ such that $N = mn.$ Notice that because $m, n \in \mathbb{Z}^{+}$ and strictly smaller than $N,$ $m, n$ must each be a product of primes. Contradiction. If $m, n$ are products of primes, then $N = mn$ must be as well.

Consider all integers of the form $a - xb$ where $x \in \mathbb{Z}.$ Let $r = a - qb$ be the least nonnegative element in this set. We claim that $0 \leq r \lt b.$ If not, $r = a - qb \geq b$ and so $0 \leq a - (q + 1)b \lt r.$ Then $r$ is not the minimal nonnegative element, contradiction.

Assume wlog. that $a$ and $b$ are not both zero, so that there are positive elements in $(a, b).$

($\Rightarrow$) Let $d$ be the smallest positive element in $(a, b).$ Clearly, $(d) \subseteq (a, b).$

($\Leftarrow$) Sps. that $c \in (a, b).$ By Lemma 2, there exists integers $q$ and $r$ such that $c = qd + r$ with $0 \leq r \lt d.$ Since both $c, d \in (a, b)$ it follows that $r = c - qd \in (a, b).$ And $0 \leq r \lt d$ implies $r = 0.$ Therefore, $c = qd \in (d).$

Since $a \in (d)$ and $b \in (d),$ we see that $d | a$ and $d | b.$ Sps. $c$ is a common divisor. Then $c$ divides every number of the form $ax + by,$ particularly $c | d.$

Since $a,$ $b$ coprime, there exists integers $r$ and $s$ such that $ra + sb = 1.$ Therefore, $rac + sbc = c.$ Since $a$ divides the left hand side, we get that $a | c.$

The divisors of $p$ are $\pm 1$ and $\pm p.$ Then $(p, b) \in \{1, p\}$ i.e. either $p, b$ coprime or $p | b,$ in which case we are done. Otherwise, if $(p, b) = 1,$ then by proposition 1 we get that $p | c.$

Let $\alpha = \text{ord}_p a$ and $\beta = \text{ord}_p b.$ Then $a = p^{\alpha}c$ and $b = p^{\beta}d,$ where $p \nmid c$ and $p \nmid d.$ Then $ab = p^{\alpha + \beta}cd$ and $p \nmid cd$ by corollary 1. Therefore, $\text{ord}_p ab = \alpha + \beta = \text{ord}_p a + \text{ord}_p b.$

It is clear that polynomials with degree $1$ are irreductible. Assuming that all polynomials with degree-bound $n$ are the product of irreductible polynomials, and that $\deg f = n.$ If $f$ is irreductible, we are done. Otherwise, $f = gh,$ where $q \leq \deg g, \deg h \lt n.$ By the induction hypothesis $g$ and $h$ are themselves products of irreductible polynomials. Therefore, $f$ is also the product of irreductible polynomials as $f = gh.$

If $g | f,$ then $h = f / g$ and $r = 0.$ Otherwise, let $r = f - hg$ be the polynomial of least degree among all polynomials of the form $f - lg$ with $l \in k[ x ].$ If $\deg r \geq \deg g,$ then let the leading term of $r$ be $ax^d$ and that of $g$ be $bx^m.$ Then $r - ab^{-l}x^{d-m}g = f - (h + ab^{-l}d^{d - m})g$ has degree less than $r.$ Contradiction.

Sps. $d \in (f, g)$ and it is an element of least degree.

($\Rightarrow$) Clearly, $(d) \subseteq (f, g).$

($\Leftarrow$) Let $c \in (f, g).$ If $d \nmid c,$ then there exists polynomials $h, r$ such that $c = hd + r$ with $\deg r \lt \deg d.$ Since $c, d \in (f, g),$ we get $r = c - hd \subseteq (f, g).$ Contradiction, $r$ has degree less than $d.$ Therefore, $d | c$ and $c \in (d).$

Since $f \in (d)$ and $g \in (d),$ we have $d | f$ and $d | g.$ Sps. that $h | f$ and $h | g.$ Then $h$ divides every polynomial of the form $fl + gm$ with $l, m \in k[ x ],$ particularly $h | d.$

Since $p$ is irreductible, either $(p, f) = (p)$ or $(p, f) = (1).$ In the former, $p | f,$ q.e.d.

In the latter case, $p, f$ coprime, and $p | f$ follows from proposition 2.

Refer to proof to corollary 2 for prop. 1.

Consider the nonnegative integers $\{\lambda(b)\,|\,b\in I, b \neq 0\}.$

Since every set of nonnegative integers has a least element there is an $a \in I \setminus \{0\}$ such that $\forall b \in I \setminus \{0\}, \lambda(a) \leq \lambda(b).$

We've claimed that $I = Ra,$ clearly $Ra \subseteq I.$ Sps. that $b \in I,$ then there exists $c, d \in R$ such that $b = ca + d,$ where $d = 0$ or $\lambda(d) \lt \lambda(a).$ Since $d = b - ca \in I,$ the inequality $\lambda(d) \lt \lambda(a)$ cannot be satisfied; so $d = 0$ and $b = ca \in Ra.$ Therefore, $I \subseteq Ra.$

Form the ideal $(a, b).$

Since $R$ is a PID there exists $d$ such that $(a, b) = (d).$ Since $(a) \subseteq (d)$ and $(b) \subseteq (d)$ we have that $d | a$ and $d | b.$

If $d' | a$ and $d' | b,$ then $(a) \subseteq (d')$ and $(b) \subseteq (d').$ Then, $(d) = (a, b) \subseteq (d')$ and $d' | d.$ Therefore $(a, b) = (d).$

Sps. that $p | ab$ and that $p \nmid a.$ Since $p \nmid a$ it follows that they only share units as common divisors. By corollary 1 $(a, p) = R,$ so $(ab, pb) = (b).$ Since $ab \in (p)$ and $pb \in (p)$ we have $(b) \subseteq (p).$ Therefore $p | b$ and in a PID, prime elements $\iff$ irreductible elements.

Let $I = \bigcup_{i=1}^{\infty} (a_i),$ obviously $I$ is an ideal so $I = (a)$ for some $a \in R.$ But $a \in \bigcup_{i=1}^{\infty} (a_i)$ implies that $a \in (a_k)$ for some $k.$ This shows that $I = (a) \subseteq (a_k).$ It then follows that $I = (a_k) = (a_{k + l}) = \dots$

Let $a \in R \setminus \{0\},$ where $a$ is a nonunit, then we want to prove the following cases.

1. $a$ is divisible by irreductibles

   In the case that $a$ itself is irreductible, we are done. Otherwise, $a = a_1b_1$ where $a_1, b_1$ are nonunits. If $a_1$ irreductible, done. Otherwise $a_1 = a_2b_2$ where $a_2, b_2$ are nonunits. If $a_2$ irreductible, done. Otherwise, continue as before.

   Notice that $(a) \subset (a_1) \subset (a_2) \subset \dots$ and by lemma 5 we have that this is a finite chain, so there must exist some $k$ such that $a_k$ is irreductible.

2. $a$ is the product of irreductibles

   If $a$ is irreductible, done. Otherwise let $p_1$ be some irreductible such that $p_1 | a.$ Then $a = p_1c_1.$ If $c_1$ is a unit, done. Otherwise, continue as before. Again, notice that $(a) \subset (c_1) \subset (c_2) \subset \dots,$ which is a finite chain by lemma 5. There must exist some $k$ for which $a = p_1p_2\dots p_k c_k,$ where $c_k$ a unit and $p_kc_k$ is irreductible.

Sps. that there does not exist an $n$ satisfying the lemma, then for each integer $m > 0$ there would be an element $b_m$ such that $a = p^mb_m.$ Then $pb_{m+1} = b_m$ so that $(b_1) \subset (b_2) \subset (b_3) \subset$ which would be an infinite chain which contradicts lemma 5.

Let $\alpha = \text{ord}_p a$ and $\beta = \text{ord}_p b.$ Then $a = p^{\alpha}c$ and $b = p^{\beta}d$ with $p \nmid c$ and $p \nmid d.$ Thus $ab = p^{\alpha + \beta}cd.$ Since $p$ prime, $p \nmid cd.$ Therefore $\text{ord}_p ab = \alpha + \beta = \text{ord}_p a + \text{ord}_p b$

The existence of such a decomposition follows from proposition 5.

To show the uniqueness, let $q \in S$ and apply $\text{ord}_q$ to both sides of eq. ($\dag$). Using lemma 7, we get

$$\text{ord}_q a = \text{ord}_q u + \sum_p e(p)\,\text{ord}_q p.$$

By definition of $\text{ord}_q$ we get that $\text{ord}_q u = 0$ and that $\text{ord}_q p = 0$ if $q \neq p$ and $1$ otherwise. So $\text{ord}_q a = e(q).$ Since exponents $e(q)$ are uniquely determined, so is the unit $u.$

For $a + bi \in \mathbb{Q}[i]$ define $\lambda(a + bi) = a^2 + b^2.$

Let $\alpha = a + bi$ and $\gamma = c + di$ and sps. $\gamma \neq 0.$ $\alpha/\gamma = r + si,$ where $r, s \in \mathbb{Q}.$ Choose integers $m,n \in \mathbb{Z}$ such that $|r - m| \leq \frac{1}{2}$ and $|s - n| \leq \frac{1}{2}.$ Set $\delta = m + ni.$ Then $\delta \in \mathbb{Z}[i]$ and $\lambda((\alpha/\gamma) - \delta) \leq \frac{1}{2}\lambda(y) \lt \lambda(\gamma).$

It follows that $\lambda$ makes $\mathbb{Z}[i]$ an Euclidean domain.

For $\alpha = a + b\omega \in \mathbb{Z}[\omega]$ define $\lambda(\alpha) = a^2 - ab + b^2.$ Then, we can see that $\lambda(\alpha) = a\overline{a}.$

Now, let $\alpha, \beta \in \mathbb{Z}[\omega]$ and sps. that $\beta \neq 0.$ Then $\alpha/\beta = \alpha\overline{\beta}/\beta\overline{\beta} = r + s\omega,$ where $r, s \in \mathbb{Q}.$ We used the fact that $\beta\overline{\beta} = \lambda(\beta)$ is a positive integer and that $\alpha\overline{\beta} \in \mathbb{Z}[\omega]$ since $\alpha, \overline{\beta} \in \mathbb{Z}[\omega].$

Next we find $m$ and $n$ such that $|r - m| \leq \frac{1}{2}$ and $|s - n| \leq \frac{1}{2}.$ Then let $\gamma = m + n\omega.$ $\lambda((\alpha/\beta) - \gamma) = (r - m)^2 (r - m)(s - n) + (s - n)^2 \leq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} \lt 1.$