Halting Processes and Proofs

I was again reading my absolute favorite book on mathematics, Mathematical Problems and Proofs [1] (no, I am not paid for this endorsement, it really is that great), and on page 11 of the text, Example 1.20 gives Euclid’s Theorem on Prime Numbers, demonstrating that the set of prime numbers must be infinite. I immediately recalled that all natural numbers are either prime, or the product of primes, known as the Fundamental Theorem of Arithmetic. This is a different result, the proof of which is not presented in [1] (at least I didn’t see it).

I checked Google, and there’s a straightforward proof using induction, but it lacks intuitive appeal. As such, I spent a few minutes this morning thinking about it, and I realized you can construct an intuitive proof. I haven’t seen this proof elsewhere, though it could be a known result. Even if it is known, what’s interesting is the structure of the proof, which is you can show that it must be the case that the algorithm upon which the proof relies, will eventually halt. This is pretty interesting, and maybe it’s a new form of proof. At a minimum, we have an intuitive proof of the Fundamental Theorem of Arithmetic that does not rely on induction.

The Proof

Assume you have a natural number $n \in \mathbb{N}$ . If $n$ is prime, then we’re done. So assume that $n$ is not prime. As such, it must be the case that $n = a_1b_1$ , for $a_1,b_1 \in \mathbb{N}$ , and therefore, $a_1 = \frac{n}{b_1} \in \mathbb{N}$ . The intermediate result will be to show that all numbers are either prime, or have at least one prime factor, which we will then use to prove the Fundamental Theorem of Arithmetic. As such, if $a_1$ is prime, then we’re done. Therefore, assume $a_1$ is not prime, and as such, $a_2 = \frac{a_1}{b_2}$ , for $a_2,b_2 \in \mathbb{N}$ . We can of course continue to apply this process for increasing values of $i \in \mathbb{N}$ , generating decreasing values of $a_i$ . However, there are only finitely many numbers less than $n$ , and as such, this process must eventually terminate, producing a prime number $a_m = \frac{a_{m-1}}{b_m}$ . Note that $a_m = \frac{n}{b_1 \cdots b_m}$ , and as such, $n = a_m (b_1 \cdots b_m)$ . Therefore, all natural numbers have at least one prime factor.

Now let’s express $n$ as the product of this prime number $p_1 = a_m$ , and the remaining factors, $f_1 = b_1 \cdots b_m$ , i.e., $n = p_1f_1$ . Note that $f_1$ cannot be prime, so we can therefore run the algorithm above on $f_1$ , which will produce another prime number factor $p_2$ , and another remaining factor $f_2$ , such that $n = p_1p_2f_2$ . Note that it must be the case that $f_2 < f_1$ , and in general, $f_{i+1} < f_i$ , and therefore it requires fewer steps to calculate each successive prime factor. Because the number of steps is always a natural number, this process must terminate. Therefore, $n$ will eventually be expressed as the product of a finite number of primes.