posted 6 Jan 2022

Unique Factorization in $\mathbb{Z}$

§ Factorization

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.

The division operator over $\mathbb{Z}$ has 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.$

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; as such, 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.

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

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

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.

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

Unique Factorization in Z\mathbb{Z}Z