We present an induction proof by Zermelo for the
fundamental theorem of arithmetic.
Part 1. Every positive integer is a product of prime numbers.
Proof. If , it is the empty product of primes, and if , it is a prime number.
Let then . Make the induction hypothesis that all positive
integers with are products of prime numbers.
If is a prime number, the thing is ready. Else, is a
product of smaller numbers; these are, by the induction hypothesis,
products of prime numbers. The proof is complete.
Part 2. For any positive integer , its representation as product of prime numbers is unique up to the order of the prime factors.
Proof. The assertion is clear in the case that is a prime number, especially when .
Let then and suppose that the assertion is true for all positive integers less than .
If now is a prime, we are ready. Therefore let it be a composite number. There is a least nontrivial factor of . This must be a prime. Put where b is a positive integer. By the induction hypothesis, has a unique prime factor decomposition. Thus has a unique prime decomposition containing the prime factor .
Now we will show that cannot have other prime decompositions. Make the antithesis that has a different prime decomposition; let be the least prime factor in it. Now we have and where and with . Then
is a positive integer less than . Since , the induction hypothesis implies that the prime is in the prime decomposition of and thus also at least of or . But we know that , whence . Thus we would get . Because both and are primes, it would follow that . This contradicts the fact that . Consequently, our antithesis is wrong. Accordingly, has only one prime decomposition, and the induction proof is complete.
- 1 Esa V. Vesalainen: “Zermelo ja aritmetiikan peruslause”. Solmu 1 (2014).
- 2 Ernst Zermelo: Elementare Betrachtungen zur Theorie der Primzahlen. Wissenschaftliche Gesellschaft zu Göttingen (1934). English translation in:
- 3 H.-D. Ebbinghaus & A. Kanamori (eds.): Ernst Zermelo. Collected Works. Volume I. Set Theory, Miscellanea, Springer (2010). Ernst Zermelo: “Elementary considerations concerning the theory of prime numbers” 576581.