3. Primes and Unique Factorization Theorem

A prime number is an integer $p$ such that

$p>1$ and $p = ab$ then either $a=1$ or $b=1$ (1)

This says that prime numbers cannot be decomposed into smaller pieces. There is an equivalent definition of primes:

$p|ab \Rightarrow p|a$ or $p|b$ (2)

In abstract algebra, an element $p$ is called a prime if (2) holds, and $p$ is called an irreducible if (1) holds. Our main focus of this chapter is to prove that $\mathbb{Z}$ is a unique factorization ring (or more specifically Unique factorization domain). And it is well-known that in UFD, prime elements and irreducible elements coincide.

Proposition: Let $p$ satisfies (1) if and only if $p$ satisfies (2)
Proof) Suppose $p|ab$, then $(p,a) = 1$, then $p|b$ by the previous posts. If $(p,a) = p$, then $p|a$ hence the result. Conversely, for the sake of contradiction that there exists two divisors $1<d_1, d_2<p$, not necessarily distinct. Then $p | d_1 d_2 \Rightarrow p| d_1$ or $p|d_2$, which cannot happen.

Lemma 1: Every integer $n>1$, $n$ is divisble by a prime.
Proof) Let $S$ be the set of all divisors $d$ such that $1<d<n$. Then if $S$ is empty, then $n$ is prime by definition, hence $n|n$. If nonempty, then since the set is bounded above by $n$, well-ordering principle guarantees a minimal element, call it $d$. Then if there existed $1<d'<d$ such that $d'|d$, then $d'|n$, contradicting the minimality of $d$. Hence we see that $d$ is a prime divisor.

Lemma 2: Every integer $n>1$, $n$ a product of prime numbers.
Proof) We carry the proof by (strong) induction. If $2$, then $2$ is clearly a product of prime. Suppose $n>2$, then by lemma 1, we see that $n = pm$, where $m<n$, then by inudction $m$ is a product of primes, and $pm$ is a product of primes.

Condition (2) can be generalized into

Lemma 3: (Generalized): If $p|a_1 \cdots a_n$, then $p|a_i$ for some $i=1, \ldots, n$.
Proof) $p|a_1$ or $p|a_2 \cdots c_n$. If the first case, then done. For the second case, we use induction.

Lemma 4: If $p|q_1 \cdots q_k$ with $q_i$ primes, then $p = q_i$ for some $i=1, \ldots, k$.
Proof) By above, $p|q_i$ for some $i$, then as only divisor of prime greater than $1$ is itself, $p =q_i$.

Theorem: (The Unique Factorization Theorem) Any positive integer can be written as a product of primes (unique up to order).
Proof) Let $n = p_1 \cdots p_r = q_1 \cdots q_s$ where $p_i$ and $q_j$ are all primes. This is possible by lemma 2. Then we see that $p_1 | q_1 \cdots q_s$. By lemma 4, $p_1 = q_k$ for some $k$, hence we see that $p_2 \cdots p_r = q_1 \cdots q_{k-1} q_{k+1} \cdots q_s$. By relabeling, we see that $p_2 \cdots p_r = q_1 \cdots q_{k-1}$. Then by induction, $k-1 = r-1 \Rightarrow k=r$ and $p_i = q_j$ for some $i$ and $j$.

The above theorem is sometimes refer to as the fundamental theorem of arithmetic because it is the central fact of the integers. The above theorem show that every element can be written into

$a = q_1 \cdots q_r$

uniquely up to order. Let's order the product such that $q_1 \leq q_2 \leq \cdots \leq q_r$, and group the same prime into an exponential form, then we get that

$a = p_1^{e_1} \cdots p_r^{e_r}$

Proposition: Let $a, b \in \mathbb{Z}$ with $e_i, f_j \geq 0$,

a = $p_1^{e_1} \cdots p_r^{e_r}$, b = $p_1^{f_1} \cdots p_r^{f_r}$, 

then $gcd(a,b) = p_1^{k_1} \cdots p_r^{k_r}$ with $k_i = min(e_i, f_i)$.
Proof) The proof is tedious. 

Appendix: Least Common Multiple
One can define least common multiple of $a,b$ to be the least element from the set $S = \{ c > 0 ~|~ a|c$ and $b|c \}$, as $ab \in S$ and it is bounded below $0$, by the well-ordering principle, we see that $S$ has a minimal element. The minimal element is defined to be the least common multiple of $a,b$, and denoted $lcm(a,b)$.

Then least common multiple satisfies the following equivalent definition: Let $c = lcm(a,b)$, then

    i) $a|c$  and  $b|c$ 
    ii) If $a|e$ and $b|e$, then $c \leq e$.

which looks analogous to the definition of the greatest common divisor, but in an "opposite" way. Some may call it the dual notion for those who have taken category theory. Then the last proposition can be rephrased into

Proposition: Let $a, b \in \mathbb{Z}$ with $e_i, f_j \geq 0$,

a = $p_1^{e_1} \cdots p_r^{e_r}$, b = $p_1^{f_1} \cdots p_r^{f_r}$, 

then $lcm(a,b) = p_1^{k_1} \cdots p_r^{k_r}$ with $k_i = max(e_i, f_i)$.
Proof) Again tedious.