Primfaktorzerlegung

Nachweis

Die erste Person, die das Theorem bewies, war Euklid. Der erste detaillierte und korrekte Beweis fand sich in den Disquisitiones Arithmeticae von Carl Friedrich Gauß.

Manche Leute denken vielleicht, dass das Theorem überall zutrifft. In allgemeineren Zahlensystemen, wie z.B. algebraischen ganzen Zahlen, trifft das Theorem jedoch nicht zu. Dies wurde erstmals 1843 von Ernst Kummer in seiner Arbeit über Fermats letzten Satz erwähnt. Weitere Informationen dazu finden Sie unter Algebraische Zahlentheorie.

Der Beweis besteht aus zwei Teilen: erstens zeigen wir, dass jede Zahl als Produkt von Primzahlen geschrieben werden kann; zweitens zeigen wir, dass, wenn wir eine Zahl ein zweites Mal als Produkt von Primzahlen schreiben, dann müssen die beiden Listen der Primzahlen gleich sein.

Erster Teil des Beweises

Wir zeigen, dass, wenn nicht jede Zahl größer als 1 als Produkt von Primzahlen geschrieben werden kann, wir in einer Art Unmöglichkeit enden. Daraus schließen wir, dass es wahr sein muss, dass jede Zahl als Produkt von Primzahlen geschrieben werden kann.

Sehen Sie nun, was passiert, wenn jemand sagt, er kenne eine positive ganze Zahl größer als 1, die nicht als Produkt von Primzahlen geschrieben werden kann. In diesem Fall bitten wir ihn/sie, alle Zahlen, die größer als 1 sind und nicht als Produkt von Primzahlen geschrieben werden können, zu erwähnen. Eine dieser Zahlen muss die kleinste sein: nennen wir sie n. Diese Zahl n kann natürlich nicht 1 sein. Sie kann auch keine Primzahl sein, denn eine Primzahl ist ein "Produkt" einer einzigen Primzahl: sich selbst. Sie muss also ein Produkt von Zahlen sein. Daher-

n = ab

wobei sowohl a als auch b positive ganze Zahlen sind, die natürlich kleiner als n sind. Aber: n war die kleinste Zahl, die nicht als Produkt von Primzahlen geschrieben werden kann. Es muss also möglich sein, a und b als Produkte von Primzahlen zu schreiben, weil beide kleiner als n sind. Aber dann muss das Produkt

n = ab

kann auch als ein Produkt von Primzahlen geschrieben werden. Das ist eine Unmöglichkeit, weil wir gesagt haben, dass n nicht als Produkt von Primzahlen geschrieben werden kann.

Wir haben jetzt die Unmöglichkeit gezeigt, die besteht, wenn der erste Teil des Satzes nicht wahr wäre. Auf diese Weise haben wir nun den ersten Teil des Theorems bewiesen.

Zweiter Teil des Beweises

Jetzt müssen wir beweisen, dass es nur einen Weg gibt, eine positive Zahl größer als 1 als Produkt von Primzahlen zu schreiben.

Dazu verwenden wir das folgende Lemma: Wenn eine Primzahl p ein Produkt ab teilt, dann teilt sie a oder sie teilt b (Euklid-Lemma). Zuerst beweisen wir nun dieses Lemma. Nehmen wir nun an, dass p nicht a dividiert. Dann sind p und a Koprim und wir haben die Identität von Bezout, die besagt, dass es ganze Zahlen x und y geben muss, so dass

px + ay = 1.

Alles mit b zu multiplizieren ergibt

pbx + aby = b,

Denken Sie daran, dass ab durch p geteilt werden konnte. Nun haben wir also auf der linken Seite zwei Terme, die durch p teilbar sind. Der Term auf der rechten Seite ist also auch durch p teilbar.

Jetzt werden wir beweisen, dass wir eine ganze Zahl größer als 1 nur auf eine Weise als Produkt von Primzahlen schreiben können. Nehmen wir zwei Produkte der Primzahlen A und B, die das gleiche Ergebnis haben. Wir wissen also für das Ergebnis der Produkte, dass A = B ist. Nehmen wir irgendeine Primzahl p aus dem ersten Produkt A. Sie teilt A, also teilt sie auch B. Wenn wir das gerade geprüfte Lemma mehrmals verwenden, können wir sehen, dass p dann mindestens einen Faktor b von B teilen muss. Aber die Faktoren sind alle selbst Primzahlen, also ist auch b eine Primzahl. Aber wir wissen, dass p ebenfalls prim ist, also muss p gleich b sein. Wir dividieren nun also A durch p und teilen auch B durch p. Und wir erhalten ein Ergebnis wie A* = B*. Wieder können wir eine Primzahl p aus dem ersten Produkt A* nehmen und herausfinden, dass sie gleich einer Zahl im Produkt B* ist. Wenn wir auf diese Weise fortfahren, sehen wir am Ende, dass die Primfaktoren der beiden Produkte genau gleich sein müssen. Dies beweist, dass wir eine positive ganze Zahl als ein Produkt von Primzahlen nur auf eine einzige Weise schreiben können.