> [!note] Theorem > > Every [[Natural Numbers|natural number]] equal to or greater than $2$ is either a [[Prime Number|prime]] or a product of primes. > > *Proof*. By the [[Axiom of Induction]]. Let $S$ be the [[Set|set]] of natural numbers that are primes or product of primes. > 1. $2 \in S$, by inspection. > 2. Assuming that $\{2, 3, \cdots, n\} \subset S$, consider $2 + n + 1$. > - If $2 + n + 1$ is a prime number, then $2 + n + 1 \in S$. > - Otherwise, $2 + n + 1$ may be the product of two numbers $a$ and $b$, by definition of a prime number. > - $a = p_1p_2 \cdots p_k$, $b = q_1q_2 \cdots q_e$, where $p$ and $q$ are sets of prime numbers, and $k$ and $e$ are natural numbers greater than 1. > - Since $a$ and $b$ are greater than 1, by assumption, they must either be primes or products of primes. > - The product or primes and products of primes is also a product of primes, therefore $2 + n + 1 \in S$. > > Therefore, $S = \{2, 3, \cdots\}$.