Jede natürliche Zahl n >= 2 lässt sich als Produkt von Primzahlen darstellen

Dieses Ergebnis ist auch bekannt als Der Fundamentalsatz der Arithmetik.

Für den Beweis wird eine besondere Variante der Vollständigen Induktion verwendet:
Wir schließen von allen Vorgängern von n auf n.




Das Prinzip lautet:
n0 sei eine natürliche Zahl mit der wir beginnen.
Sei A(m) eine Aussage für alle natürlichen Zahlen m0 ≤ m < n.
Wenn für jede natürliche Zahl n ≥ n0 aus der Aussage A(m) die Aussage A(n) folgt, dann gilt A(n) für alle natürlichen Zahlen n ≥ n0.

Nun zu unserer Aufgabe:
Sei n ≥ 2 und jede natürliche Zahl m < n lasse sich als Produkt von Primzahlen darstellen.
Wenn n eine Primzahl ist, ist die Aussage bewiesen.
Wenn n keine Primzahl ist, dann hat n einen echten Teiler m.
Das heißt: 1 < m < n und n = mr mit 1 < r < n.
Da m und r natürliche Zahlen und kleiner als n sind, sind sie nach Voraussetzung Produkte von Primzahlen.
Das heißt auch n = mr ist ein Produkt von Primzahlen.

Nochmal Prinzip und Beispiel verknüpft:
n0 = 2.
A(m): Alle natürlichen Zahlen kleiner als n lassen sich als Produkt von Primzahlen darstellen.
Aus A(m) folgt A(n): Die Zahl n lässt sich als Produkt von Primzahlen darstellen.
Nun gilt A(n) für alle natürlichen Zahlen n ≥ n0.