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 pp be prime. From pab    pap \mid ab \implies p \mid a or pbp \mid b.


Let np=abnp = ab and abab a minimal counterexample. We assume, that pap \nmid a and show, that pbp \mid b.

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




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

a<pa<p: (nb)p=(ap)b(1)(bn)p=(pa)b,p:=xa+y(y<a)(x1)ab(bn)p(x1)ab=(pa(x1)a)bbpnpxab+ab=(paxa+a)bbpxab=yb=bpxnp=(bxn)p=yb<ab    pb \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 nNn \in \mathbb{N} has an unique prime factorization.


Let a=i=1npiki=i=1mqili \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) ps=qtp_s = q_t. With a:=psa^a := p_s\hat{a}: a^=psks1i=1,isnpiki=qtlt1i=1,itmqili \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 a^<a    n=m,s=t,pi=qi,ki=lii\hat{a}<a \implies n=m, \, s=t, \, p_i = q_i, \, k_i = l_i \, \forall i