A few days ago I came across a proof of the Fundamental Theorem of Arithmetic (aka Unique Factorization) in Courant and Robbin’s What is Mathematics that I hadn’t seen it before. I liked it enough to learn it.
Then another surprise – I saw it again yesterday in Primes and Programming by Peter Giblin, a book that Larry Zimmerman had recommended to a student from the summer high school program.
The usual proof that I know is based on Euclid, and basically is a proof by Strong Induction. This new proof is by the Principle of Least Element. So the key is to suppose that unique factorization fails, and to reason about the least positive integer \(N\) that has more than one factorization into primes. Even though we’ll show this number doesn’t exist, we can deduce lots of information about it!
First, some notation. Let’s say that two distinct prime factorizations of \(N\) are
\[\text{(1)}\qquad N = p_1 p_2 \dots p_r \text{ and } N = q_1 q_2 \dots q_s\]
Of course, we’ll arrange the primes in non-decreasing order, so that in particular, \(p_1\) and \(q_1\) are the smallest primes in those factorizations.
The other primes don’t take a big role in what comes next, so let’s write \(P = p_2 \dots p_r\) and \(Q = q_2 \dots q_s\), so that we have
\[N = p_1 P = q_1 Q.\]
The first observation is that \(p_1\) and \(q_1\) are different primes, otherwise if they were equal, we could factor them off and then \(N/p_1 = P\) would be a smaller positive integer with two distinct prime factorizations.
Now that that’s done, let’s assume without loss of generality that \(p_1 < q_1\), and we’ll form a new number:
\[\text{(2)}\qquad M = (q_1 – p_1) Q\]
By equation (2), it’s clear that \(M\) is a positive integer that is less than \(N\), and therefore does factor uniquely into primes. Now we rewrite \(M\) as follows:
\[M = (q_1 – p_1) Q = q_1 Q – p_1 Q = N – p_1 Q = p_1 P – p_1 Q = p_1 (P – Q)\]
That is, \[\text{(3)}\qquad M = p_1 (P – Q)\]
We’re almost there. Note that because of equation (3), the prime \(p_1\) is a prime factor of \(M\). Now consider the factorization of \(M\) given in equation (2). Since we were careful to list the primes in non-decreasing order, \(p_1\) can’t be any of the primes in \(Q = q_2 \dots q_s\), and so it must be a factor of \((q_1 – p_1)\). Suppose that \((q_1 – p_1) = p_1 t\). Then solving for \(q_1\), we find that \(q_1 = p_1 (t+1)\). And this is a contradiction, since then \(q_1\) would not be a prime number!
