Der Fundamentalsatz der Arithmetik (auch einzigartiger Faktorisierungssatz genannt) ist ein Satz der Zahlentheorie. Das Theorem besagt, dass jede positive ganze Zahl größer als 1 als ein Produkt von Primzahlen geschrieben werden kann (oder die ganze Zahl selbst eine Primzahl ist). Außerdem ist diese Darstellung bis auf die Reihenfolge der Faktoren eindeutig: Gibt es zwei Zerlegungen einer Zahl in Primfaktoren, so unterscheiden sie sich nur durch die Reihenfolge der Primzahlen.
Beispiele:
6936 = 23 · 3 · 172 und 1200 = 24 · 3 · 52
Das Finden der Primzahlen nennt man Faktorisierung. Wenn jemand eine andere Zerlegung von 6936 oder 1200 als Produkt von Primzahlen findet, lassen sich die Primfaktoren in die richtige Reihenfolge bringen, sodass beide Zerlegungen übereinstimmen.
Bedeutung und Darstellung
- Der Satz liefert für jede n > 1 eine eindeutige Darstellung der Form n = p1a1 · p2a2 · … · pkak, wobei pi verschiedene Primzahlen sind und ai positive ganze Exponenten.
- Diese Darstellung nennt man die Primfaktorzerlegung oder kanonische Primfaktorzerlegung einer Zahl.
- Die Eindeutigkeit bedeutet, dass die Menge der Primfaktoren und die zugehörigen Exponenten eindeutig bestimmt sind (bis auf Permutation der Faktoren).
Kurzer Beweisüberblick
Existenz: Man zeigt durch vollständige Induktion über n ≥ 2, dass jede Zahl n mindestens eine Primfaktorzerlegung besitzt. Wenn n selbst prim ist, sind wir fertig. Ist n zusammengesetzt, so hat n einen nichttrivialen Teiler d mit 1 < d < n; dann zerlegt man d und n/d nach der Induktionsannahme weiter in Primfaktoren und multipliziert die Zerlegungen zusammen.
Eindeutigkeit: Für die Eindeutigkeit verwendet man ein zentrales Hilfsmittel der Zahlentheorie, das sogenannte Euklidische Lemma: Wenn eine Primzahl p ein Produkt a·b teilt, dann teilt p entweder a oder b. Mit diesem Lemma lässt sich zeigen, dass jeder in zwei Weisen gegebene Primfaktor einer Zerlegung auch in der anderen Zerlegung vorkommen muss; durch wiederholtes Entfernen gleicher Primfaktoren zeigt man schließlich, dass beide Zerlegungen übereinstimmen (bis auf Reihenfolge).
Anwendungen
- In der Kryptographie spielt der Satz eine wichtige Rolle, insbesondere beim RSA-Verfahren: RSA nutzt die Tatsache, dass das Produkt zweier großer Primzahlen leicht zu berechnen ist, das Zurückrechnen (Faktorisieren) dieses Produkts aber für große Zahlen sehr aufwändig ist.
- Weitere Anwendungen finden sich in der Theorie der arithmetischen Funktionen (z. B. Anzahl der Teiler, größte gemeinsame Teiler), in der Kodierungstheorie und bei algorithmischen Fragestellungen.
Verallgemeinerungen und Grenzen
- Der Fundamentalsatz gilt nicht nur in den ganzen Zahlen, sondern hat Verallgemeinerungen in der abstrakten Algebra: In Integritätsbereichen, die eindeutige Faktorisierungseigenschaften besitzen (sogenannte eindeutige Faktorisierungsbereiche, UFDs), gilt eine analoge Aussage.
- Es gibt jedoch Ganzheitsringe, in denen die eindeutige Primfaktorzerlegung fehlschlägt (z. B. der Ring Z[√−5]), wodurch die Bedeutung des Begriffs „Primfaktor“ und „Irreduzibel“ in der algebraischen Zahlentheorie vertieft wird.
Praktische Hinweise zur Faktorisierung
- Kleine Zahlen lassen sich durch wiederholte Division durch aufsteigende Primzahlen faktorisieren (Trial Division).
- Für große Zahlen werden effiziente Algorithmen wie Pollard-Rho, Quadratisches Sieb oder das Allgemeine Zahlkörpersieb verwendet; die Faktorisierung großer Zahlen bleibt jedoch für sehr große Größen computational anspruchsvoll.
Der Fundamentalsatz der Arithmetik ist damit eine fundamentale Strukturbedingung der ganzen Zahlen und bildet die Grundlage vieler weiterer Ergebnisse und Anwendungen in Mathematik und Informatik.