Zum Inhalt springen

Ganze Zahlen/Hauptsatz über Primfaktorzerlegung/Euklid/Textabschnitt

Aus Wikiversity

Wir möchten nun zur Primfaktorzerlegung, deren Existenz wir bereits in Fakt gezeigt haben, beweisen, dass sie eindeutig ist. Natürlich kann man

schreiben, mit eindeutig ist also eindeutig bis auf die Reihenfolge gemeint. Um dies zu zeigen brauchen wir zunächst das sogenannte Lemma von Euklid, das eine wichtige Eigenschaft einer Primzahl beschreibt.


Es sei eine Primzahl und teile ein Produkt von natürlichen Zahlen .

Dann teilt einen der Faktoren.

Wir setzen voraus, dass kein Vielfaches von ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ein Vielfaches von ist. Unter der gegebenen Voraussetzung sind und teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen mit

Da ein Vielfaches von ist, gibt es ein mit

Daher ist

Also ist ein Vielfaches von .


Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl ein beliebiges Produkt teilt, dann teilt mindestens einen Faktor. Man wendet das Lemma einfach auf an (formal ist das eine Induktion über die Anzahl der Faktoren). Dies wird im Beweis des folgenden Hauptsatzes der elementaren Zahlentheorie verwendet.


Jede natürliche Zahl , , besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

mit Primzahlen , und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

Die Existenz der Primfaktorzerlegung wurde bereits in Fakt gezeigt. Die Eindeutigkeit wird durch Induktion über gezeigt. Für liegt eine Primzahl vor. Sei nun und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl das Produkt rechts teilt. Nach Fakt muss dann einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Daraus ergibt sich durch Kürzen, dass

ist. Nennen wir diese Zahl . Da ist, können wir die Induktionsvoraussetzung auf anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

In der kanonischen Primfaktorzerlegung schreibt man die beteiligten Primzahlen in aufsteigender Reihenfolge mit ihrem jeweiligen Exponenten, also beispielsweise

Damit ist insbesondere zu jeder ganzen Zahl und jeder Primzahl eindeutig bestimmt, ob in der Primfaktorzerlegung überhaupt vorkommt und wenn ja mit welchem Exponenten.