Fundamental Theorem of Arithmetic

Proof of the Fundamental Theorem of Algebra's uniqueness part without utilizing Bézout's lemma.

Lemma (Euclid)

Let $p$ be prime. From $p \mid ab \implies p \mid a$ or $p \mid b$.

Proof:

Let $np = ab$ and $ab$ a minimal counterexample. We assume, that $p \nmid a$ and show, that $p \mid b$.

$$\begin{aligned} np &= ab &|-bp\\ (n-b)p &= (a-p)b \end{aligned}$$

$a=p$:

trivial

$a>p$:

$\textrm{From } p \nmid a \implies p \nmid (a-p) \textrm{ and with } (a-p)b < ab \implies p \mid b$

$a<p$: $$\begin{aligned} (n-b)p &= (a-p)b & &|\cdot(-1)\\ (b-n)p &= (p-a)b,\quad p:=xa+y \quad (y<a) & &|-(x-1)ab \\ (b-n)p - (x-1)ab &= (p-a-(x-1)a)b\\ bp-np-xab+ab &= (p-a-xa+a)b\\ bp-xab &= yb\\ =bp-xnp&=(b-xn)p = yb < ab\\ \implies p &\mid b \end{aligned}$$

Theorem (Fundamental Theorem of Arithmetic)

Every $n \in \mathbb{N}$ has an unique prime factorization.

Proof:

Let $$\begin{aligned} a = \prod_{i=1}^n p_i^{k_i} = \prod_{i=1}^m q_i^{l_i} \end{aligned}$$ and a the smallest number with a non-unique decomposition by primes. From Euclid's lemma follows, that for some (s,t) $p_s = q_t$. With $a := p_s\hat{a}$: $$\begin{aligned} \hat{a} = p_s^{k_s-1}\prod_{i=1, i\neq s}^n p_i^{k_i} = q_t^{l_t-1}\prod_{i=1, i\neq t}^m q_i^{l_i} \end{aligned}$$ Because $\hat{a}<a \implies n=m, \, s=t, \, p_i = q_i, \, k_i = l_i \, \forall i$