[Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
	Mathematik-Online-Lexikon:
	Primfaktorzerlegung

Eine Primzahl ist eine natürliche Zahl , die genau Teiler besitzt, nämlich und . Zum Beispiel sind Primzahlen, während und keine Primzahlen sind.

Beweise durch Induktion, daß sich jede natürliche Zahl als Produkt von Primzahlen schreiben läßt.

Lösung.

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.