# Fundamental Theorem of Arithmetic

Posted on Sun 21 March 2021 in math

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: \begin{aligned} (n-b)p &= (a-p)b & &|\cdot(-1)\\ (b-n)p &= (p-a)b,\quad p:=xa+y \quad (y

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}