Introduction
Often when I decide to write a post about some theorem or concept, the best are those that are both deep and easy to explain. These are admittedly hard to come by, but upon doing a bit of review of some basic number theory (study of properties of whole numbers), I stumbled across the Fundamental Theorem of Arithmetic (FToA) and thought that it was an almost perfect candidate.
The FToA is about the atomic nature of prime numbers, which, for those unfamiliar, are numbers whose only divisors are themselves and 1. The FToA basically tells us that each whole number is made up of some unique product of primes. There are proofs littered across mathematics that make use of either or both of the existence of such a decomposition and its uniqueness. For such a useful theorem, the proof is quite accessible and I thought it was worth writing about, so here we go.
Proving it
The theorem can be stated as follows:
Theorem: Every positive whole number $n > 1$ can be written as a unique product of prime numbers.
Proof: The proof has 2 parts. We will first show that the decomposition exists and then we will show that it’s unique. For existence, we will use induction. The base case, when $n = 2$, is trivial. 2 is the product of… well… 2. So now we assume that $n > 2$ and then every number $1 < k < n$ has such a decomposition. If $n$ is prime, we’ve succeeded (same logic we used for the base case). If $n$ is composite, then we can write $n = ab$ with $a$ and $b$ both strictly smaller than $n$. By the induction hypothesis, both $a$ and $b$ have prime factor decompositions, so $n$ does as well.
(If you aren’t familiar with induction, what we’ve done is shown that in the very smallest case, we have what we want. We’ve also shown that if what we want to prove holds for $2..n-1$, it also holds for $n$. Thus, if it holds for 2, it holds for 3. If it holds for 2 and 3, it holds for 4. If it holds for 2, 3 and 4, it holds for 5. Continuing this way forever, we see that every possible $n$ has the property we want.)
Now, for uniqueness. The way we typically show uniqueness in math is by supposing that there are 2 distinct versions of whatever it is we think is unique and showing that they must actually be the same. This is the technique we employ here. Suppose that we could write n two ways. That is, suppose we could validly write both of $n = p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ and $n = q_1^{f_1}q_2^{f_2}\dots q_m^{f_m}$ where the $p_i$ (distinct from one another) and $q_j$ (distinct from one another) are prime and the exponents are all positive. Notice that the first factorization has $k$ primes, the second has $m$ and that the exponents are not necessarily all the same (yet). We are truly assuming that we have 2 factorizations that are, at least initially, potentially completely different from one another. If we can show that $k = m$ and that $e_i = f_i$ for each $i$, then we’ve accomplished our objective.
We can assume, without loss of generality, that the $p_i$ are in increasing order (if they’re not, we can relabel them so that they are without affecting any part of the proof). Let’s look at $p_1$. It must divide one of the $q_j$ (this stems from the fact that if a prime divides a product of numbers, it must divide at least one of the numbers — this is not hard to prove using induction… try it?). Let’s say that $p_1|q_j$ for some $j$. Reorder the $q_j$ so that $p_1|q_1$. Because both $p_1$ and $q_1$ are prime, this means that $p_1 = q_1$. So divide each factorization by $p_1$ and $q_1$ respectively and repeat this process until you run out of primes in one of the decompositions. If one of the factorizations runs out before the other, then we will have written 1 as a product of primes greater than 1, which is impossible. They must thus run out at the same time, whence $k = m$, $e_i = f_i$ for each $i$ and our two factorizations must have been one and the same. QED.
Conclusion
Fundamental theorems abound all over mathematics. There are fundamental theorems of arithmetic, algebra, calculus, cyclic groups, linear algebra and others. This one, though, really gets at the very makeup of a mathematical entity that all of us understand, at least on a basic level: the positive whole numbers. Cool, no?