Fundamentalsatz der Arithmetik

aus Wikipedia, der freien Enzyklopädie

Der Fundamentalsatz der Arithmetik besagt, dass jede natürliche Zahl größer als eins eine Primfaktorzerlegung besitzt und dass diese bis auf die Reihenfolge der Faktoren eindeutig ist.

Zum ersten Mal vollständig und korrekt bewiesen findet sich der Fundamentalsatz der Arithmetik in den Disquisitiones Arithmeticae von Carl Friedrich Gauß. Er war aber bereits - wenn auch in leicht abgewandelter Form - Euklid bekannt.

Bemerkenswert ist, dass der Beweis für die Eindeutigkeit der Zerlegung nicht ohne die additive Struktur der natürlichen Zahlen auskommen kann. Ein Beispiel, aus dem hervorgeht, warum dies so ist, geht auf David Hilbert zurück: Betrachtet man die Menge

der „Hilbert-Zahlen“, so könnte man jeden Beweis der Eindeutigkeit in den natürlichen Zahlen, der nur auf Multiplikation beruht, auf diese Zahlen übertragen. In H ist aber die Zerlegung nicht eindeutig, da zum Beispiel ist. Man beachte, dass 4, 10 und 25 alles „Hilbert-Primzahlen“ sind, da sie in H nicht weiter zerlegt werden können.

(Hinweis: Die in diesem Absatz benutzte Bezeichnung „Hilbert-(Prim)Zahl“ wurde nur der einfacheren Erklärung wegen eingeführt und ist nicht mathematisches Allgemeingut.)

[Bearbeiten] Beweis

Der Beweis zerfällt in zwei Teile. Zunächst wird gezeigt, dass es eine Zerlegung in Primzahlen gibt, und in einem zweiten Schritt, dass diese Zerlegung eindeutig ist.

1. Existenz einer Zerlegung: Jede natürliche Zahl größer als eins kann als das Produkt von Primzahlen geschrieben werden oder ist selbst eine Primzahl. Diese Darstellung heißt Primfaktorzerlegung.

Der Beweis erfolgt indirekt, d. h. die Annahme, es gäbe natürliche Zahlen größer eins, die keine Primfaktorzerlegung besitzen, wird zu einem Widerspruch geführt.

Die kleinste zusammengesetzte Zahl größer eins, die keine Zerlegung in Primfaktoren besitzt, bezeichnen wir mit n. Da n keine Primzahl ist, gibt es einen Teiler a von n mit 1 < a < n. Daher kann n als

n = ab

mit

dargestellt werden. Da n nach unserer Annahme die kleinste Zahl ohne eine Primfaktorzerlegung ist, können die Zahlen a und b als Primfaktorzerlegung dargestellt werden. Damit haben wir jedoch n als Produkt von Primzahlen dargestellt. Dies ist ein Widerspruch zur Annahme, dass es Zahlen ohne Primfaktorzerlegung gibt. Damit ist die Existenz einer Zerlegung bewiesen.

2. Eindeutigkeit der Zerlegung

Zum Beweis verwenden wir als Hilfsatz das Lemma von Bézout. Der interessierte Leser findet einen konstruktiven Beweis mittels des Erweiterten Euklidischen Algorithmus.

Damit beweisen wir zunächst den Hilfssatz:

Wenn eine Primzahl p Teiler eines Produkts ab ist, dann ist p Teiler von a oder Teiler von b.

Der Beweis erfolgt erneut indirekt. Wir führen die Annahme, p sei weder Teiler von a noch von b, zu einem Widerspruch. Wenn p nicht Teiler von a ist (ggT(a,p)=1), gibt es nach dem Lemma von Bézout ganze Zahlen x und y, so dass

px + ay = 1.

Multiplikation mit b ergibt

pbx + aby = b;

da ab = n auf der linken Seite durch p teilbar ist, ist auch die Summe durch p teilbar. Folglich ist b durch p teilbar. Damit haben wir einen Widerspruch zur Annahme, dass p weder Teiler von a noch von b ist.

Diese Überlegung gilt auch, wenn p Teiler eines Produkts abc von drei Zahlen ist; wegen

abc = (ab)c

kann der Hilfssatz zunächst auf die beiden Faktoren (ab) und c angewendet werden. Damit ist p Teiler von (ab) oder von c. Falls p Teiler von (ab) ist, ist p Teiler von a oder von b. Durch Induktionsbeweis kann die Aussage so auf ein Produkt beliebig vieler Zahlen erweitert werden.

Wir betrachten zwei Primfaktorzerlegungen einer Zahl

Da p₁ Teiler von n ist folgt, dass p₁ Teiler einer der Primzahlen ist. Da eine Primzahl per Definition nur durch eins und sich selbst teilbar ist, muss p₁ identisch mit einer der Primzahlen sein. Jeder Faktor einer Zerlegung ist folglich identisch einem Faktor der anderen Zerlegung. Die Zerlegung ist damit bis auf die Reihenfolge eindeutig.