Fundamental Theorem of Arithmetic

Theorem 5:  The Fundamental Theorem of Arithmetic

Every integer greater than $1$ is either prime or can be represented as the unique product of powers of prime numbers.

Proof:

(1)  First, prove existence.  It is true for the base case where $n=2$ since $2$ is a prime.

(2)  Assume that it is true for all $i$ with $i \le n$

(3)  For $n+1$, if $n+1$ is prime, then it is true.  If $n+1$ is not prime, then there exists integers $a,b$ such that $n+1 = ab$ with $a \le n$ and $b \le n$.  Since $a \le n$ and $b \le n$, they can be represented by a prime or a product of primes with $a=p_1p_2\dots{p_n}$ and $b=q_1q_2\dots{q_n}$

(4)  Then $n+1 = ab = p_1p_2\dots{p_n}q_1q_2\dots{q_n}$ which means that $n+1$ can be represented as a product of powers of prime numbers.

(5)  Assume that there is an integer that has two different product of powers of prime numbers.

(6)  Let $y$ be the least integer where this is true so that $y = p_1p_2\dots{p_m} = q_1q_2\dots{q_n}$ with $p_1\dots{p_m}$  and $q_1\dots{q_n}$.

(7)  From Euclid's Generalized Lemma, $p_1$ divides $q_i$ where $1 \le i \le n$.  But, then $\frac{y}{p_1} = p_2\dots{p_m} = \frac{q_1q_2\dots{q_n}}{p_1}$ which is smaller than $n$ and contradicts our assumption in step(6).