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
To summarize the comments, this is also known as Zermelo's proof. A version can be found on [wikipedia](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Uniqueness_without_Euclid%27s_lemma). 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.


