Induktionsanfang:
ist das leere Produkt.
Induktionsschritt: Wir nehmen nun als Induktionshypothese an, die Aussage sei für die natürlichen Zahlen
mit
erfüllt. Wir müssen zeigen, daß
sich als Produkt von Primzahlen schreiben läßt.
Falls
eine Primzahl ist, so ist
das Produkt, das nur aus dem Faktor
besteht.
Falls
keine Primzahl ist, so kann man
schreiben mit natürlichen Zahlen
.
Dann können wir die Induktionshypothese auf
und
anwenden und erhalten Darstellungen von
und
als Produkte von Primzahlen. Damit ist
als Produkt von
und
ebenfalls ein Produkt von Primzahlen.