Fundamental Theorem of Arithmetics: Zermelo’s proof in detail

The Fundamental Theorem of Arithmetic: Zermelo’s proof in detail

Michael Emmerich, December 14th, 2024

Zermelo (1934) employs a proof by contradiction to establish the uniqueness of prime factorization for positive integers, demonstrating that the assumption of a non-unique prime factorization leads to a contradiction. Notably, his proof does not rely on Euclid’s Lemma. This essay reproduces Zermelo’s proof, which is somewhat tricky, with an effort to explain its steps in greater detail compared to previous works. It is important to note that the proof of the existence of prime factorization has already been covered in my previous essay, which also includes a proof of uniqueness based on Euclid’s Lemma. (Link).

Proof

He first postulates that if there exists a positive integer with non-unique prime factorization, there must be the smallest such integer, which we call ${m}$ .
Notably, all positive integers smaller than ${m}$ would have a unique prime factorization.
Contradiction assumption: Let us show that if such a smallest number ${m}$ with non-unique prime factorization exists, this leads to a contradiction:
If ${m}$ were the smallest integer with non-unique prime factorization, there would exist (at least) two distinct prime factorizations of ${m}$ .
Let us order the factors of ${m}$ in the two factorizations such that ${ m = q_1 q_2 \cdots q_n \quad}$ (first factorization),
${m = p_1 p_2 \cdots p_k }$ (second factorization).
Note that the two factorizations cannot have any common factor, say ${d = q_i = p_j}$ for some indices ${i}$ and ${j}$ . If they did, we could construct a smaller integer with non-unique prime factorization than ${m}$ , as dividing both factorizations by ${d}$ would yield such an integer.
Thus, ${p_1 \neq q_1}$ . Without loss of generality, assume ${p_1 < q_1}$ . (If ${p_1 > q_1}$ , we could simply exchange the letters ${p}$ and ${q}$ .)
Define a smaller positive integer: ${s := m - p_1 q_2 \cdots q_n.}$
The integer ${s}$ is smaller than ${m}$ and strictly positive because of the assumption ${p_1 < q_1}$ .
Using basic arithmetic (the distributive law), the following equalities hold: (Eq.1): ${s = p_1 \big(p_2 \cdots p_k - q_2 \cdots q_n\big)}$ , and (Eq.2): ${s = (q_1 - p_1) q_2 \cdots q_n}$ .
From the first equality, ${s}$ is divisible by ${p_1}$ .
From the second equality, ${s}$ is also divisible by ${q_1 - p_1}$ .
Thus, ${p_1}$ must divide either (a) one of the ${q_i}$ , or (b) ${q_1 - p_1}$ .
Case (a): If ${p_1}$ divides one of the ${q_i}$ for ${i = 2, \dots, n}$ , this leads to a contradiction because ${p_1 < q_i}$ (by ${p_1 < q_1}$ and the ordering ${q_1 \leq q_2 \leq \cdots \leq q_n}$ ). Since ${q_i}$ are prime, they cannot be divisible by the smaller prime ${p_1}$ .
Case (b): If ${p_1}$ divides ${q_1 - p_1}$ , then ${p_1}$ must also divide ${q_1}$ (since ${q_1 = (q_1 - p_1) + p_1}$ ). But ${q_1}$ is prime, and this is a contradiction because ${p_1 < q_1}$ .
Hence, both cases (a) and (b) lead to contradictions.
Therefore, there cannot exist a smallest integer ${m}$ with non-unique factorization. q.e.d.