factorization motivator
If \(p\) is prime and \(p | ab\), then \(p|a\) or \(p|b\).
If \(p|a\), we are done.
Consider the case where \(p|ab\) yet \(a\) is not divisible by \(p\). Then, \(a\) and \(p\) are coprime. This means that, we have:
\begin{equation} \gcd (a,p) = 1 = s a + tp \end{equation}
We note that:
\begin{align} b &= 1 \cdot b \\ &= (sa+tp) b \\ &= sab + tpb \\ &= s(ab) + tb(p) \end{align}
Notice that both of these elements are divisible by \(p\) (\(p|ab\) and of course \(p|p\)). Therefore, \(p|b\) as desired.
statement of the theorem
Every integer greater than \(1\) is a prime or a product of primes. This factorization is unique.
Proof
Existence
Let \(S\) be the list of integers bigger than \(1\) which are prime or are products of primes. Consider the set \(T\) which is all integers bigger than \(1\) which isn’t prime or are products of primes:
\begin{equation} T = \{2, 3, \dots, \} \setminus S \end{equation}
We desire \(T\) to be empty.
Assume for the sake of contradiction that \(T\) isn’t empty. By WOP, take some smallest element of \(t \in T\).
\(t\) is not in \(S\), so it mustn’t be prime. This means:
\begin{equation} t = ab \end{equation}
Though…. \(a\) and \(b\) must be smaller than \(t\) (otherwise their product wouldn’t make \(t\), as we are working with only positive numbers (integers greater than \(1\)) here). So \(a\) and \(b\) must be in $S$—meaning they are primes or product of primes. This makes \(t\) a prime or product of primes, reaching contradiction.
Uniqueness
We show this by induction. We see that: \(2 = 2\). Now, suppose a unique prime factorization holds for all integers smaller than \(n\). Let:
\begin{equation} n = p_1 \dots p_{r} = q_1 \dots q_{s} \end{equation}
Let us order it such that \(p_1 \leq … \leq p_{r}\), \(q_1 \leq … \leq q_{s}\).
By the factorization motivator, each \(p_{j}|n\) implies that \(p_{j}|q_{i}\) (you can see this by treating \(n = q_1 … q_{s}\), so \(p_{j}|n \implies p_{j}|(q_1 \cdot \dots \cdot q_{s})\) so \(p_{j}\) should be divisible by some \(q_{j}\).)
Now, this condition implies \(p_{j} = q_{i}\), because primes are not divisible by anything except themselves and \(1\) (and \(1\) is not considered prime).
Consider, then, two such equivalences:
\begin{equation} p_{1} = q_{j} \end{equation}
\begin{equation} q_{1} = p_{k} \end{equation}
Now, this means that:
\begin{equation} p_{1} \leq p_{k} = q_{1} \leq q_{j} = p_{1} \end{equation}
Therefore, the only way this can work (the fact that \(q_1\) is sandwiched on both ends — by \(p_1\leq q_1 \leq p_1\)) is that \(p_1 = q_1\).
Therefore, we now have:
\begin{equation} \frac{n}{p_1} = p_{2} \cdot \dots \cdot p_{n} = q_{2} \cdot \dots \cdot q_{n} \end{equation}
You will note \(\frac{n}{p_1} < n\). Now, we can invoke induction. \(\blacksquare\)