Thirty or so years ago, someone showed me a clever proof of the Fundamental Theorem of Arithmetic that did not make use of the lemma "If $p\mid ab$ then $p\mid a$ or $p\mid b$". I'm unable to reconstruct the argument; all I remember is that it used induction and that it didn't generalize to other number rings. Can anyone provide such a proof, or provide other offbeat elementary proofs of unique factorization of natural numbers into primes?
Nonstandard proofs of the fundamental theorem of arithmetic
elementary-proofsnt.number-theoryprime numbers
Best Answer
To summarize the comments, this is also known as Zermelo's proof. A version can be found on wikipedia. I will give the proof here to avoid link rot.
The proof is by contradiction. If FTA did not hold, then use the well ordering principle to select the smallest number $s$ which can be factored in two distinct ways into products of primes, $s = p_1p_2 \dots p_m = q_1q_2\dots q_n$. No $p$ can be equal to a $q$, for otherwise $s/p = s/q$ would give a smaller example, violating minimality.
Assume without loss of generality that $p_1 < q_1$. Let $P = p_2 \dots p_m$ and $Q = q_2 \dots q_n$. Then $s = p_1P = q_1Q$, so that
$$t=(q_1-p_1)Q = p_1(P-Q) < s$$
Since $t$ is less than $s$, then by minimality of $s$ there is only one way to factor it into a product of primes, namely the prime factorization of $q_1-p_1$ times the (known) prime factorization of $Q$. Since $p_1$ is a prime factor of $t$, $p_1$ must either be one of the prime factors of $q_1 - p_1$ or be one of the prime factors $q_i$ of $Q$. We already said that $p_1$ is not equal to any of the $q_i$, so $p_1$ is one of the prime factors of $q_1-p_1$. In particular, $p_1$ divides $q_1$. But $q_1$ is a prime not equal to $p_1$, a contradiction.