Every Integer Greater Than 2 Has a (Possibly Non-unique) Prime Factorization

Question

Not a particularly difficult question! However, just for the sake of completeness, I wanted to check if the following two proofs work.

To begin with, I prove every integer greater than $2$ has a prime divisor. Take any integer $x$ $\geq 2$. Since $x$ divides itself, the set $S$ of integers $\geq 2$ that divide $x$ is nonempty. By the well-ordering property, $S$ has a smallest element. Take the smallest element of $S$, which I'll call $y$. $y$ must be a prime. To establish this, suppose $y$ isn't a prime. Then there are integers $a,b$ such that $y\gt a,b \geq 2$ and $a,b$ both divide $y$. But if $a,b$ divide $y$, then $a,b$ must divide $x$ and therefore $a,b \in S$. This contradicts minimality of $y$. So $y$ must be a prime. This proves the property that every integer $\geq 2$ must have a prime divisor.

To prove that every integer can be written as a product of possibly non-unique primes and $1$, I think it should be sufficient to do strong induction on the composite numbers. Base case is $4$ and it follows obviously. Assuming the claim is true for each of the first $k^{th}$ composites, I note that the $k+1$$^{th}$ composite can be written as the product of two integers $a,b \geq2$. If $a,b$ are prime, then the proposition is true. If either or both of $a,b$ are composites, then they be must one of the first $k$ composites and the proposition must be true of $a,b$ by the inductive hypothesis. So the proposition is true of the $k+1$$^{th}$ composite and is therefore true for all integers greater than $2$.

Answer 1

Either of these proofs are fine. I would propose rewriting the second proof more simply - it's true that you could use induction to prove a statement such as:

The $k^{th}$ composite number can be written as a product of primes.

However, this is a bit silly - since now you have to handle primes and composites separately, even though the same logic applies. It also has the issue that you're writing a proof without knowing which number in particular you're applying it to - you could get in trouble if you had to use more specifics about the number in question but could only say "it's the $1000^{th}$ composite number."

It's easier just to write the proof by strong induction on $n$ itself:

We will prove by strong induction that every $n\geq 2$ can be written as a product of primes. If $n$ is prime, the claim is trivial. Otherwise, we can write $n=ab$ for $2\leq a,b < n$ and use strong induction to rewrite $a$ and $b$ as products of primes - and multiplying these products together gives $n$ as a product of primes.

---

The comments raised some questions of using strong induction vs. using well-ordering; I think your proofs make appropriate use of both - essentially, your proofs provide algorithms of finding a prime factor or a prime factorization respectively. Your first proof says:

Test every number from $2$ up to $x$ to see which are divisors of $x$. Note that $x$ is assured to be a divisor of $x$, but there may be others. Let $y$ be the least such divisor.

This gives us an iterative algorithm for extracting prime divisors of numbers - and, in general, uses of the well-ordering theorem correspond to an algorithm like this*.

The second proof corresponds to a recursive algorithm:

Check whether $n$ is prime. If so, note that $n=n$ is a prime factorization. If not, write $n=ab$ and recursively apply this algorithm to both $a$ and $b$ and combine the resulting prime factorizations.

The fact that this algorithm finishes is provided by strong induction - since, to factor $n$, we are only going to try to apply the algorithm to smaller inputs, and we can only do that for so long.

These algorithms correspond to the intuition behind the two proofs - indicating that you made a good choice in which to use (and also indicating, as was brought up in comments, that your proofs are constructive - they provide an algorithm for producing the objects they claim exist). It's possible, though not advisable, to rewrite the second proof to start with:

Suppose that it's not true that all $n\geq 2$ have a prime factorization. Let $n$ be the least number without a prime factorization. ...

This would be considered inelegant because it uses proof by contradiction, but could be rephrased as a direct proof without changing the structure of the argument. Note that writing a proof this way also makes it nonconstructive - if I want to actually factor $289$, it doesn't help me to know why there can't be a number that doesn't have a prime factorization! Which is to say: it's a good thing you didn't write a proof that started this way. :)

---

(*This assumes you have an algorithm to test whether something is in the given set - but, for the set of divisors of $x$, that's clearly possible)