# Unique Factorization

## Motivation§

Number theory is most easily described as the study of the natural numbers.

Some open problems in number theory include the twin prime conjecture, whether there exists an infinite number of prime pairs such that their difference is 2, or Goldbach’s conjecture, whether every number can be written as the sum of two primes.

## Unique Factorization in $\mathbb{Z}$§

### Integer Ring§

$\mathbb{Z}$

$\mathbb{Z} = \{0, -1, 1, -2, 2, -3, 3, \dots\}$ is the ring of integers with the usual definition of the sum and product operations.

- If $p$ positive and prime, then $-p$ is also prime.
- Every nonzero integer divides zero.
- No number can be divided by zero.

### Factorization§

The division operator over $\mathbb{Z}$ yields the following properties,

- $\forall a \neq 0, a | a$ (
*reflexive*), - If $a | b$ and $b | a,$ then $a = \pm b$ (
*symmetric*), - If $a | b$ and $b | c,$ then $a | c$ (
*transitive*), - If $a | b$ and $a | c,$ then $a | b + c.$

Let $n \in \mathbb{Z}\setminus\{0\}$ and let $p$ be prime, then $\exists e, p^e | n \wedge p^{a+1} \nmid n.$

Order

If $p, e, n \in \mathbb{Z}^{+},$ then $\exists a, p^e \gt n.$

We say that $e$ is the order of $n$ at $p$ and write $\text{ord}_p n = a.$

- Roughly, $e$ is the number of times that $p$ divides $n.$
- For $n = 0,$ we set $\text{ord}_p 0 = \infty.$
- $\text{ord}_p n = 0 \iff p \nmid n.$

Lemma 1

Every nonzero integer can be written as a product of primes.

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.

Factorization

We can collect prime terms and we can write $n = p_1^{e_1}p_2^{e_2}\dots p_r^{e_r},$ or

$$ n = (-1)^{\varepsilon(n)} \prod_p p^{a(p)}, $$

where $\varepsilon(n)$ yields 0 or 1 depending on the sign of $n,$ and the product is over all positive primes. The exponents $a(p)$ are nonnegative integers, and $a(p) = 0$ for a countably infinite number of primes.

Theorem 1

For every nonzero integer $n$ there exists a prime factorization uniquely determined by $n,$

$$ n = (-1)^{\varepsilon(n)} \prod_p p^{a(p)}, $$

where $a(n) = \text{ord}_p n.$

### Greatest Common Divisor§

Lemma 2

If $a, b \in \mathbb{Z}$ and $b > 0,$ there exists $q, r \in \mathbb{Z}$ such that $a = qb + r$ with $0 \leq r \lt b.$

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.

Ideals on $\mathbb{Z}$

If $a_1, a_2, \dots, a_n \in \mathbb{Z},$ then define $A = (a_1, a_2, \dots, a_n)$ to be the set of all integers of the form $a_1x_1 + a_2x_2 + \dots + a_nx_n$ with $x_1, x_2, \dots, x_n \in \mathbb{Z}.$

Notice that the sum and difference of any two elements in $A$ is also in $A.$ If $a \in A$ and $r \in \mathbb{Z},$ then $ra \in A.$

Then, $A$ is an ideal of ring $\mathbb{Z}.$

Lemma 3

If $a, b \in \mathbb{Z},$ then there exists $d \in \mathbb{Z}$ such that (a, b) = (d).

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).$

Greatest Common Divisor

Sps. $a, b, d \in \mathbb{Z},$ if $d | a$ and $d | b$ and every other common divisor of $a$ and $b$ divides $d,$ then we say that $d$ is the *greatest common divisor* (gcd) of $a$ and $b$ and write $(a, b) = d.$

If $c$ is another greatest common divisor, distinct from $d,$ then we must have $c | d$ and $d | c,$ so $c = \pm d.$ If there exists a gcd between two numbers, then it is determined up to sign.

Lemma 4

Let $a, b \in \mathbb{Z},$ if $(a, b) = (d),$ then $d$ is the greatest common divisor of $a$ and $b.$

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.$

### Coprimality§

Coprime

Sps. $a, b \in \mathbb{Z}$ such that $(a, b) = \pm 1.$ We say that $a$ and $b$ are *coprime* (or *relatively prime*)

Proposition 1

Sps. $a | bc$ and that $(a, b) = 1,$ then $a | c.$

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.$

Corollary 1

If $p$ prime and $p | bc,$ then either $p | b$ or $p | 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.$

Then, if $p$ prime, $p \nmid b$ and $p \nmid c,$ then $p \nmid bc.$

Corollary 2

Sps. $p$ prime and that $a, b \in \mathbb{Z},$ then $\text{ord}_p (ab) = \text{ord}_p a + \text{ord}_p b.$

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.$

### Unique Factorization Proof§

Finally, the proof to Theorem 1. If we apply $\text{ord}_p$ to both sides of

$$ n = (-1)^{\varepsilon(n)} \prod_p p^{a(n)}, $$

and utilize the property of $\text{ord}_q$ given in corollary 2, we get

$$ \text{ord}_q n = \varepsilon(n) \text{ord}_q(-1) + \sum_p a(p)\,\text{ord}_q p . $$

Then, by definition of $\text{ord}_q,$ we get $\text{ord}_q (-1) = 0$ and $\text{ord}_q p = 0$ if $p, q$ are distinct and $1$ otherwise.

Then, the right hand side can be simplified into $a(q),$ i.e. $\text{ord}_q n = a(q).$

## Unique Factorization in $k[x]$§

### Polynomial Ring§

The unique factorization theorem can be generalized into other rings, not just the integers.

Polynomial Ring

The ring $k[x]$ are polynomials with coefficients in a field $k.$

#### Divisibility in $k[x]$§

- If $f, g \in k[ x ],$ then we say $f | g$ iff $\exists h \in k[ x ], g = fh.$
- If $\deg f$ denotes the degree of $f,$ then $\deg fg = \deg f + \deg g.$
- $\deg f = 0$ iff $f$ is a nonzero constant.
- $f | g$ and $g | f$ iff $f = cg$ where $c$ is a nonzero constant.

Units

The only polynomials that divide all others are the nonzero constants, i.e. the units of $k[ x ]$

Irreductible Polynomials

A nonconstant polynomial $p$ is said to be irreductible iff $q | p$ implies $q$ is either a constant or a constant times $p.$

These are analogous to the prime numbers in $\mathbb{Z}.$

### Factorization§

Lemma 1

Every nonconstant polynomial is the product of irreductible polynomials.

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.$

Monic Polynomial

A polynomial $f$ is monic if its leading coefficient is 1.

Every polynomial, save for zero, is a constant times a monic polynomial.

Order in $k[ x ]$

Let $p$ be a monic irreductible polynomial. We define $\text{ord}_p f$ to be the integer $a$ defined by the property that $p^a | f$ but that $p^{a+1} \nmid f.$ Such an integer must exist since the degree of powers of $p$ is monotonically increasing. Notice that $\text{ord}_p f = 0 \iff p \nmid f.$

Theorem 2

Sps. $f \in k[ x ],$ then

$$ f = c \prod_p p^{a(p)}, $$

where the product is over all the monic irreductible polynomials, and $c$ is a constant.

The constant $c$ and the exponents $a(p)$ are uniquely determined by $f,$ and $a(p) = \text{ord}_p f.$

### Greatest Common Divisor§

Lemma 2

Let $f, g \in k[ x ].$ If $g \neq 0,$ then there exists $h, k \in k[ x ]$ such that $f = hg + r,$ where $r = 0$ or $r \neq 0$ and $\deg r \lt \deg g.$

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.

Ideals on $k[ x ]$

If $f_1, f_2, \dots, f_n \in k[ x ],$ then $(f_1, f_2, \dots, f_n)$ is the set of all polynomials of the form $f_1h_1 + f_2h_2 + \dots + f_nh_n,$ where $h_1, h_2, \dots, h_n \in k[ x ].$

Then, $(f_1, f_2, \dots, f_n)$ is the ideal generated by $f_1, f_2, \dots, f_n.$

Lemma 3

Given $f, g \in k[ x ],$ there exists $d \in k[ x ]$ such that $(f, g) = (d).$

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).$

Greatest Common Divisor

Sps. $f, g \in k[ x ].$
Then $d \in k [ x ]$ is said to be the *greatest common divisor* of $f$ and $g$ iff $d | f$ and $d | g$ and every other common divisor of $f$ and $g$ divides $d.$

The greatest common divisor of two polynomials is determined up to multiplication by a constant.
If we require the gcd to be monic, then it is uniquely determined which is what we mean when we say *the* greatest common divisor.

Lemma 4

Let $f, g \in k[ x ].$ By Lemma 3, there exists $d \in k[ x ]$ such that $(f, g) = (d).$ Then, $d$ is a gcd of $f$ and $g.$

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.$

### Coprimality§

Coprime

$f, g \in k[ x ]$ are said to be coprime (or relatively prime) iff the common divisors of $f$ and $g$ are constants, i.e. $(f, g) = (1).$

Proposition 2

If $f$ and $g$ coprime, we have that $(f, g) = (1)$ so there are polynomials $l, m$ such that $lf + mg = 1.$ Thus, $lfh + mgh = h.$ Since $f$ divides the left hand side, $f | h.$

Corollary 1

If $p$ is an irreductible polynomial and $p | fg,$ then $p | f$ or $p | g.$

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.

Corollary 2

If $p$ is a monic irreductible polynomial and $f, g \in k[ x ],$ we have $\text{ord}_p fg = \text{ord}_p f + \text{ord}_p g.$

See pf. to corollary 2 for prop. 1.

### Unique Factorization Proof§

Finally, we have the tools to prove theorem 2. If we apply $\text{ord}_q$ to both sides of

$$ f = c\prod_p p^{a(p)}. $$

We get

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

Clearly $q \nmid c$ as $c$ is a constant, so $\text{ord}_q c = 0.$ Then $\text{ord}_q p = 0$ if $q \neq p$ and $1$ otherwise. Finally, we get that $\text{ord}_q f = a(q).$ This shows that the exponents are uniquely determined by $f$ and so is $c.$

## Unique Factorization in a Principal Ideal Domain§

The proof methods for unique factorization in $\mathbb{Z}$ and $k[ x ]$ are very similar. We can further generalize this notion of unique factorization. In this section, we will denote an integral domain with $R.$

### Euclidean Domain§

Euclidean Domain

$R$ is an *Euclidean domain* iff there exists a function $\lambda: R \setminus \{0\} \to \mathbb{N} \cup \{0\},$ such that if $a, b \in R, b \neq 0,$ there exists $c, d \in R$ with the property $a = cb + d$ and either $d = 0$ or $\lambda(d) \lt \lambda(b).$

The rings $\mathbb{Z}$ and $k[ x ]$ are examples of Euclidean domains. For $\mathbb{Z}$ we can consider $\lambda$ to be the absolute value function, in $k[ x ]$ $\lambda$ is the function that assigns to every polynomial its degree.

Proposition 3

If $R$ is an Euclidean domain, and $I \subseteq R$ is an ideal, then there exists $a \in R$ such that $ I = Ra = \{ra\,|\,r \in R\}.$

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.$

### Principal Ideal Domain§

For elements $a_1, a_2, \dots, a_n \in R,$ we define $(a_1, a_2, \dots, a_n) = Ra_1 + Ra_2 + \dots + Ra_n = \left\{\sum_{i=1}^n r_ia_i\,|\,r_i \in R\right\}.$ Then, $(a_1, a_2, \dots, a_n)$ is an ideal.

If an ideal $I$ is equal to $(a_1, a_2, \dots, a_n)$ for some elements $a_i \in I,$ we say that $I$ is finitely generated. If $I = (a)$ for some $a \in I,$ we say that $I$ is a principal ideal.

Principal Ideal Domain

If every ideal of $R$ is principal, then we say that $R$ is a *principal ideal domain* (PID).

Every Euclidean domain is a PID, but not every PID is an Euclidean domain, i.e. PID $\supset$ Euclidean domain. However finding counterexamples to PID $=$ Euclidean domain is somewhat hard. In practice, it is useful to show that a given ring is an Euclidean domain, which gives us the added bonus of showing that it is a PID.

#### Terminology§

Division

If $a, b \in R, b \neq 0,$ then we say that $b$ divides $a$ if $\exists c \in R, a = bc$ and write $b | a.$

In terms of ideals, $a | b \iff (b) \subseteq (a).$

Associate

$a, b \in R$ are *associates* if $a = bu$ for some unit $u.$

A unit is defined as $u \in R$ such that $(u) = R.$ And in terms of ideals, $a$ and $b$ are associates iff $(a) = (b).$

Irreducibility

An element $p \in R$ is irreductible if $a | p$ implies that $a$ is either a unit or an associate of $p.$

Prime

A nonunit $p \in R \setminus\{0\}$ is said to be prime if $p | ab$ implies that $p | a$ or $p | b.$

In terms of ideals, $p$ prime iff $ab \in (p) \implies a \in (p) \lor b \in (p).$

We now make distinct the notion of irreductible and prime elements. These notions do not generally coincide, unlike in $\mathbb{Z}$ and $k[ x ]$ and later we will show that they coincide in a PID.

### Greatest Common Divisor§

Greatest Common Divisor

$d \in R$ is said to be a (gcd) of two elements $a, b \in R$ if

- $d | a$ and $d | b,$
- $d’ | a \wedge d’ | b \implies d’ | d.$

If both $d$ and $d’$ are gcds of $a$ and $b,$ then $d$ is associate to $d’.$

Proposition 4

Let $R$ be a PID and $a, b \in R.$ Then $a$ and $b$ have a gcd and $(a, b) = (d).$

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).$

### Coprimality§

Coprime

$a$ and $b$ are coprime iff their common divisors are units.

Corollary 1

If $R$ is a PID and $a, b \in R$ are coprime, then $(a, b) = R.$

Corollary 2

If $R$ is a PID, and $p \in R$ is irreductible, then $p$ prime.

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.

In a PID we will use *prime* and *irreductible* interchangeably.

### Order§

Lemma 5

Let $(a_1) \subseteq (a_2) \subseteq (a_3) \subseteq \dots$ be an ascending chain of ideals. Then there exists $k \in \mathbb{N}$ such that $(a_k) = (a_{k+l})$ for $l = 0, 1, 2, \dots.$ That is, the chain breaks in finitely many steps.

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 $

Proposition 5

Every nonzero nonunit of $R$ is a product of irreductibles.

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

$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.

$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.

We use the following lemma to construct the $\text{ord}$ function akin to those for $\mathbb{Z}$ and $k[ x ].$

Lemma 6

Let $p$ be prime and $a \neq 0.$ Then there exists $n \in \mathbb{Z}$ such that $p^{n} | a$ but $p^{n + 1} \nmid a.$

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.

Then the integer $n$ defined in lemma 6 is uniquely determined by $p$ and $a,$ and we set $n = \text{ord}_p a.$

### Unique Factorization Proof§

Lemma 7

If $a, b \in R \setminus \{0\},$ then $\text{ord}_p (ab) = \text{ord}_p a + \text{ord}_p b.$

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$

Let $S \subset R$ be a set of primes with the properties

- $\forall p \in R \exists s \in R,$ such that $p$ and $s$ are associates.
- $\nexists a, b \in S$ such that $a$ and $b$ are associates.

To generate the set $S$ we can choose a representative prime from each class of associate primes. In $\mathbb{Z}$ we can construct the set $S$ by choosing all positive primes. In $k[ x ]$ we chose $S$ to be the set of monic irreductible polynomials.

There does not exist a general way to construct $S$ for an arbitrary PID.

Theorem 3

Let $R$ be a PID and $S$ a set of primes with the aforementioned properties.

Then if $a \in R \setminus \{0\},$ then we can write

$$ a = u \prod_p p^{e(p)}, \tag{\dag} $$

where $u$ is a unit and the product is over all $p \in S.$ The unit $u$ and the exponents $e(p)$ are uniquely determined by $a.$ In fact, $e(p) = \text{ord}_p q.$

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.$

## $\mathbb{Z}[i]$ and $\mathbb{Z}[\omega]$§

### Gaussian Integers§

Gaussian Integers

Let $i = \sqrt{-1}$ and consider $\mathbb{Z}[i] \subset \mathbb{C}$ defined by $\{a + bi\,|\,a,b \in \mathbb{Z}\}.$

Clearly, $\mathbb{Z}[i]$ is closed under addition and attraction.

Also, if $a + bi, c+ di \in \mathbb{Z}[i],$ then $(a + bi)(c + di) = ac + adi + bci + bdi^2 = (ac - bd) + (ad + bc)i \in \mathbb{Z}[i].$ So $\mathbb{Z}[i]$ is closed under multiplication and is a ring.

Since $\mathbb{Z}[i] \subset \mathbb{C},$ it is an integral domain as well.

Proposition 6

$\mathbb{Z}[i]$ is an Euclidean domain.

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.

### Eisenstein Integers§

The numbers $\pm 1$ and $\pm i$ are the roots of $x^4 = 1$ over the complex numbers. Consider $x^3 = 1,$ since $x^3 - 1 = (x - 1)(x^2 + x + 1),$ the roots are $1, \left(-1 \pm \sqrt{-3}\right) / 2.$ Let $\omega = \left(-1 + \sqrt{-3}\right)/2,$ then $\omega^2 = \left(-1 - \sqrt{-3}\right)/2$ and that $1 + \omega + \omega^2 = 0.$

Eisenstein Integers

Consider $\mathbb{Z}[\omega] = \{a + b\omega\,|\, a, b \in \mathbb{Z}\}.$

Clearly, $\mathbb{Z}[\omega]$ is closed under addition and subtraction.

Also, $(a + b\omega)(c + d\omega) = ac + (ad + bc) \omega + bd\omega^2 = (ac - bd) + (ad + bc- bd) \omega.$ Thusly, $\mathbb{Z}[\omega]$ is a ring.

Again, $\mathbb{Z}[\omega] \subset \mathbb{C}$ so it is an integral domain.

Additionally, $\mathbb{Z}[\omega]$ is closed under complex conjugation. Since $\overline{\sqrt{-3}} = \overline{\sqrt{3}\cdot i} = - \sqrt{3}\cdot i = -\sqrt{-3}$ we get that $\overline{\omega} = \omega^2.$ So if $\alpha = a + b\omega \in \mathbb{Z}[\omega],$ then $\overline{\alpha} = a + b\overline{\omega} = a + b\omega^2 = (a - b) - b\omega \in \mathbb{Z}[w].$

Proposition 7

$\mathbb{Z}[\omega]$ is 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.$

Let $\rho = \alpha - \gamma\beta.$ Then either $\rho = 0$ or $\lambda(p) = \lambda(\beta((\alpha/\beta) - \gamma)) = \lambda(\beta)\lambda((\alpha / \beta) - \gamma) \lt \lambda(\beta).$

Then, $\mathbb{Z}[i]$ and $\mathbb{Z}[\omega]$ are PIDs as well, which means the theorem of unique factorization is true.

## Exercises§

**Exercise 1:** Let $a$ and $b$ be nonzero integers. We can find nonzero integers $q$ and $r$ such that $a = qb + r,$ where $0 \leq r \lt b.$ Prove that $(a, b) = (b, r).$

**Solution:**
Clearly $a | qb + r.$
Let $d$ be the gcd of $a$ and $b.$
Because $d | a,$ we get $d | qb + r,$ so $d | qb$ and $d | r.$

As a result, any common divisor of $a$ and $b$ is also a divisor of $r.$ Because $r \lt b,$ there can be no common divisor between $b$ and $r$ greater than those of $a$ and $b.$ Therefore, $(a, b) = (b, r).$

**Exercise 2:**
(*this is a continuation to ex. 1*)
If $r \neq 0,$ we can find $q_1$ and $r_1$ such that $b = q_1r + r_1$ with $0 \leq r_1 \lt r.$
Show that $(a, b) = (r, r_1).$
This process can be repeated.
Show that it must end in finitely many steps.
Show that the last nonzero remainder must equal $(a, b).$

**Solution:** We’ve proved this in my cryptography class, see theorem 3.1 under the Euclidean algorithm.

Exercise 3 skipped.

**Exercise 4:**
Let $d = (a, b)$ show that the Euclidean algorithm can be used to find $m$ and $n$ such that $am + bn = d.$

**Solution:** The process is outlined under the Bézout Coefficients section from my cryptography notes.

Exercise 5 skipped.

**Exercise 6:**
Let $a, b, c \in \mathbb{Z}.$
Show that the equation $ax + by = c$ has integer solutions iff $(a, b) | c.$

**Solution:**
Let $d = (a, c).$

($\Rightarrow$) We can see that $d$ divides the left hand side which means that $d$ must divide $c.$

($\Leftarrow$) Sps. $d | c$ so $c = dc’$ for some $c’ \in \mathbb{Z}.$ Then we can write $au + bv = d$ for some $m, n \in \mathbb{Z}.$ Then by multiplying the expression by $c’$ we get $auc’ + bvc’ = dc’ = c.$ Finally let $x = uc’$ and $y = vc’$ be integer solutions to $ax + by = c.$

**Exercise 7:**
Let $d = (a, b)$ and $a = da’$ and $b = db’.$
Show $(a’, b’) = 1.$

**Solution:**
Let $d’ = (a’, b’),$ so $d’ | a’$ and $d’ | b’.$
Then $dd’ | a$ and $dd’ | b.$
If $d’ \neq 1$ then $dd’$ is a common divisor of $a$ and $b$ that is larger than $d.$

**Exercise 8:**
Let $x_0$ and $y_0$ be a solution to $ax + by = c.$
Show that all solutions have the form $x = x_0 + t(b / d), y = y_0 - t(a / d)$ where $d = (a, b)$ and $t \in \mathbb{Z}.$