# Proof

(related to Theorem: Fundamental Theorem of Arithmetic)

#### Proof of existence

• Let $$n > 1$$.
• According existence of prime divisors, we can find a prime divisor $$p\mid n$$.
• In the series of consecutive prime numbers, $$p_1=2, p_2=3, \ldots$$, we also can find an index $$i$$, for which we can write $n=p_{i}^1\cdot n_1,$ with $$p_i=p$$ and some $$n_1 < n$$.
• Since $$n$$ was either composite or prime, we have that $$n_1 > 1$$ or $$n_1=1$$. * In the latter case, we are done.
• In the first case, $$n_1$$ is another, non-trivial divisor of $$n$$.
• Repeating the same argument for $$n_1$$ we will find other prime $$q$$ and a new divisor $$n_2 < n_1$$, whereby we have $\begin{array}{ccl} n&=&p_i^2\cdot n_2,\text{ if }q=p_i\text{ or }\\ n&=&p_i\cdot p_j\cdot n_2 \text{ else.} \end{array}$
• Since $$n_1$$ was either composite or prime, we have again that $$n_2 > 1$$ or $$n_2=1$$, so we can repeat the above argument.
• By doing so, we will possibly find even further divisors $$n_2, n_3,\ldots$$ of $$n$$ and the corresponding primes $$p_k\mid n$$, grouping them by the corresponding powers $$p_k^{e_k}$$.
• Obviously, the set of these numbers is a non-empty subset of natural numbers.
• Following the well-ordering principle, the set of all $$\{n_k\}$$, $$k=1,2,\ldots$$, with all $$n > n_1 > n_2 >\ldots > 1$$, for which we repeat the argument, must have a minimum $$n_{p} > 1$$.
• By the corresponding corollary, $$n_p$$ must be a prime number.
• Thus, the repetition of the above steps will finally end and we will find a factorization of the form $n = p_1^{e_1}\cdot p_2^{e_2}\cdot\ldots\cdot p_r^{e_r},$ where $$p_r$$ denotes the biggest prime we have found, the $$p_1,\ldots p_r$$ denote consecutive primes (i.e. starting with $$p_1=2, p_2=3,\ldots$$ and ending at $$p_r$$), and $$e_i$$ denote the number of times we have found the prime $$p_i$$ in the procedure.

#### Proof of Uniqueness

• Assume that, applying the above procedure more then once, we can find two different factorizations of $$n$$: $\begin{array}{cclr} n&=&p_1^{e_1}\cdot p_2^{e_2}\cdot\ldots\cdot p_r^{e_r},&~~~~~~~~~~(1)\\ n&=&p_1^{f_1}\cdot p_2^{f_2}\cdot\ldots\cdot p_s^{f_s}.&~~~~~~~~~~(2) \end{array}$
• Without loss of generality, assume $$r\ge s$$.
• If $$r > s$$, then it follows from $$(1)$$ that $$p_r\mid n$$ and from $$(2)$$ that $$p_r\not\mid n$$, which is a contradiction, because a divisor of $$n$$ cannot be mutually not a divisor of $$n$$.
• By construction, our two factorizations list all consecutive primes, $$p_1 < p_2 < \ldots < p_r$$.
• Thus, it must be $$r=s$$.
• Now, if $$(1)$$ and $$(2)$$ are two different factorizations by hypothesis, then it must be $$f_i\neq e_i$$ for at least one $$i$$.
• Let, without loss of generality, assume $$f_i < e_i$$.
• Then, from $$(1)$$ it follows that $$p_i^{e_i}\mid n$$ and from $$(2)$$ that $$p_r^{e_i}\not\mid n$$, which is again is a contradiction, by the same argument.
• Thus, the two factorizations must be in fact identical.

Github: 