> [!NOTE] Theorem (FTA) > Every [[Natural Numbers|natural number]] $n > 1$ can be expressed uniquely as a product of [[Prime Numbers|primes]] (has a unique [[Prime Factorisation|prime factorisation]]). > ###### Proof ***Existence***: We proceed by [[Induction Principle|induction]]. Let $P(n)$ be statement that "every natural between $2$ and $n$ can be expressed as a product of primes." $P(2)$ is true since $2$ is a prime. Suppose for some integer $k\geq 2,$ $P(k)$ is true. So every natural number $m$ with $2\leq m\leq k$ can be expressed as a product of primes. If $(k+1)$ is prime, then we are done. Otherwise $(k+1)=ab$ where $a,b \in \mathbb{N}^{+}$ , $2\leq a,b\leq k.$ By the inductive hypothesis, $a$ and $b$ have prime factorisations hence so does $ab.$ ***Uniqueness***: Suppose $n = p_{1}p_{2}\dots p_{r} =q_{1}q_{2}\dots q_{s}$where each $p_{i}, q_{j}$ are primes. First consider $p_{1}$ divides $q_{1}\dots q_{s}$ since $p_{1}\mid n$ then by [[A Prime that Divides a Product of Integers Must Divide At Least On Factor (Euclid's Lemma)|Euclid's lemma]], either $p_{1}$ divides $q_{1}$ or $p_{1}\mid q_{2}\dots q_{s}.$ In the first case, $p_{1}=q_{1}$ since they're both primes. In second case, $p_{1}\mid q_{2}$ or $p_{1}\mid q_{3}\dots q_{s}$ so continuing conclude $p_{1}=q_{i}$ for some $i.$ WLOG assume $p_{1}=q_{1}$ (rearranging the $q_{i}$ as needed) so now $p_{2}\dots p_{r}=q_{2}\dots q_{s}.$ Then inductively $p_{i}=q_{i}$ and $r=s.$