Primfaktorzerlegung

Kernidee und Darstellung

Die Primfaktorzerlegung ist die Darstellung einer positiven natürlichen Zahl n ∈ N+ als Produkt aus Primzahlen p ∈ P. Diese Primzahlen heißen Primfaktoren von n. Die Darstellung ist eindeutig bis auf die Reihenfolge der Faktoren; mathematisch kann man sie als Multimenge auffassen. Die Primfaktorzerlegung gehört zu den grundlegenden Werkzeugen der Zahlentheorie und ist Inhalt des Fundamentalsatzes der Arithmetik.

Eine Zahl p heißt Primfaktor von n, wenn p ein Teiler von n ist und p eine Primzahl ist. Ist n selbst eine Primzahl, dann ist n ihr einziger Primfaktor. Hat n mehr als einen Primfaktor, heißt n zusammengesetzt. Die Eins kann als leeres Produkt verstanden werden. Null wird in diesen multiplikativen Betrachtungen ausgeschlossen.

Ein Primfaktor kann mehrfach vorkommen. Deshalb unterscheidet man, ob Primfaktoren mit Vielfachheit gezählt werden oder ob nur die verschiedenen Primfaktoren gezählt werden. Mehrfach vorkommende Faktoren fasst man mit Exponenten zusammen. Sind die M verschiedenen Primfaktoren p1, …, pM aufsteigend geordnet, spricht man von der kanonischen Primfaktorzerlegung: n = p1^e1 · p2^e2 … pM^eM = ∏(k=1 bis M) pk^ek. Der Exponent ek gibt die Vielfachheit des Primfaktors pk an, also wie oft n durch pk teilbar ist. Er heißt auch pk-Bewertung von n. Mit Vielfachheit gezählt hat n dann N = e1 + … + eM = ∑(k=1 bis M) ek Primfaktoren.

Eine äquivalente Schreibweise lautet n = ∏(p ∈ P) p^ep, wobei ep ∈ N0 gilt und nur endlich viele Exponenten ep von 0 verschieden sind.

Typische Beispiele

Einfache Beispiele zeigen, wie die Zerlegung funktioniert und wie die kanonische Schreibweise entsteht:

• 30 = 2 · 3 · 5.
• 37 = 37, weil 37 eine Primzahl ist.
• 1001 = 7 · 11 · 13.
• 1024 = 2 · … · 2 mit 10 Faktoren, also 2^10; das ist eine Zweierpotenz.
• 6936 = 2 · 2 · 2 · 3 · 17 · 17, kanonisch geschrieben als 2^3 · 3 · 17^2.
• 10000 = 2^4 · 5^4; das ist eine Zehnerpotenz.

Auch bei kleinen Zahlen erkennt man das Muster: 4 = 2^2, 8 = 2^3, 9 = 3^2, 12 = 2^2 · 3, 16 = 2^4, 18 = 2 · 3^2 und 20 = 2^2 · 5. Primzahlen wie 2, 3, 5, 7, 11, 13, 17 und 19 haben jeweils nur sich selbst als Primfaktor.

Eindeutigkeit und Existenz

Der Fundamentalsatz der Arithmetik, auch Hauptsatz der elementaren Zahlentheorie genannt, besteht aus zwei Aussagen: Jede natürliche Zahl besitzt eine Primfaktorzerlegung, und diese Zerlegung ist in kanonischer Darstellung eindeutig. Die beiden Aussagen werden getrennt formuliert und bewiesen. Die klassischen Beweise sind elementar, werden als Widerspruchsbeweise geführt und verwenden die Wohlordnung der natürlichen Zahlen. Der Satz findet sich vollständig und korrekt bewiesen in den Disquisitiones Arithmeticae von Carl Friedrich Gauß; er war in leicht abgewandelter Form bereits Euklid bekannt.

Für die Existenz ist bei 0 und 1 nichts zu zeigen; jede Primzahl ist selbst ihre Primfaktorzerlegung. Für zusammengesetzte Zahlen nimmt man zum Widerspruch an, es gebe Zahlen ohne Primfaktorzerlegung. Wegen der Wohlordnung gibt es dann eine kleinste solche Zahl n. Da n > 1 nicht prim ist, hat n nichttriviale Teiler a und b mit a · b = n und 1 < a, b < n. Weil n die kleinste problematische Zahl ist, besitzen a und b jeweils eine Primfaktorzerlegung. Multipliziert man diese Zerlegungen, erhält man aber eine Primfaktorzerlegung von n. Das widerspricht der Annahme.

Für die Eindeutigkeit ist bei 0, 1 und Primzahlen ebenfalls nichts zu zeigen. Man nimmt an, es gebe zusammengesetzte Zahlen mit mehreren verschiedenen Primfaktorzerlegungen, und wählt wieder die kleinste solche Zahl n. Gemeinsame Faktoren in zwei Zerlegungen könnte man kürzen; dadurch entstünde eine kleinere Zahl, was der Minimalität von n widerspräche. Also kann man annehmen, dass die beiden Zerlegungen keine gemeinsamen Primfaktoren enthalten. Da ein Primfaktor p1 der einen Zerlegung das Produkt der anderen Zerlegung teilt, folgt mit dem Lemma von Euklid, dass p1 einen Faktor der anderen Zerlegung teilen muss. Weil dort ebenfalls nur Primzahlen stehen, müsste p1 dort selbst vorkommen. Das widerspricht der Annahme, dass die Zerlegungen keine gemeinsamen Primfaktoren haben.

Wichtige Eigenschaften

Aufeinanderfolgende Zahlen n und n + 1 können keine gemeinsamen Primfaktoren haben. Das ist für Teilbarkeitsaufgaben wichtig, weil ein gemeinsamer Primfaktor beide Zahlen teilen müsste.

Die Berechnung einer Primfaktorzerlegung gehört zum Faktorisierungsproblem für ganze Zahlen. Es gibt mehrere Faktorisierungsverfahren, die nichttriviale Teiler ganzer Zahlen bestimmen. Für beliebige Zahlen ist aber bisher kein effizientes Verfahren bekannt. Darauf beruhen weltweit Sicherheitskonzepte, besonders in der modernen Kryptographie. Ein verwandtes Thema ist der Primzahltest.

Die Anzahl von Primfaktoren besitzt auch statistische Eigenschaften. Hardy bewies unter anderem, dass die durchschnittliche Anzahl von Primfaktoren für größer werdendes n nur sehr langsam wächst, nämlich wie ln(ln(n)), also der doppelt angewendete natürliche Logarithmus. Der Satz von Erdős-Kac besagt außerdem, dass die Anzahl der Primfaktoren asymptotisch normalverteilt ist, mit Erwartungswert ln ln n + O(1) und Standardabweichung O(√(ln ln n)).

Die Funktion ω(n) ordnet jeder natürlichen Zahl die Anzahl ihrer paarweise verschiedenen Primfaktoren zu. Sie ist eine arithmetische Funktion und additiv, aber nicht streng additiv. Sie ist von der Teileranzahlfunktion zu unterscheiden, denn diese zählt alle Teiler einer Zahl, nicht nur die Primteiler. Beispiel: ω(1000) = 2, weil 1000 nur die verschiedenen Primfaktoren 2 und 5 hat. Mit der kanonischen Schreibweise gilt ω(n) = M.

Weitere Kennzahlen betreffen Exponenten und größte Primfaktoren: Der asymptotische arithmetische Mittelwert der maximalen Exponenten in den Primfaktorzerlegungen der Zahlen 1, 2, 3, … ist die Niven-Konstante, ungefähr 1,7. Der entsprechende Mittelwert der minimalen Exponenten ist genau 1. Der asymptotische Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer Zahl wird durch die Golomb-Dickman-Konstante γ ≈ 0,62433 angegeben.

Verallgemeinerungen

Primzahlen und Primfaktorzerlegungen lassen sich in andere mathematische Strukturen übertragen. Bei den ganzen Zahlen können Primzahlen auch ein negatives Vorzeichen haben; dort bleibt die Primfaktorzerlegung bis auf Vorzeichen und Reihenfolge eindeutig. Auch für von 0 verschiedene rationale Zahlen q ∈ Q× gibt es eine eindeutige Darstellung q = ± ∏(p ∈ P) p^ep, wobei ep ∈ Z gilt und nur endlich viele Exponenten von 0 verschieden sind.

Für allgemeinere Strukturen braucht man mindestens einen Begriff der Teilbarkeit. David Hilbert bewies, dass für die gewünschte Eindeutigkeit eine additive Struktur notwendig ist. Üblicherweise betrachtet man einen kommutativen Ring mit Eins. Dort können Primelemente definiert werden: Ein Element ist prim, wenn Euklids Lemma dafür gilt. Das garantiert noch nicht, dass alle Elemente in Primelemente zerlegt werden können; wenn solche Zerlegungen existieren, sind sie aber eindeutig.

Für die Existenz von Zerlegungen braucht man zusätzlich den Begriff der Unzerlegbarkeit. Dazu betrachtet man nullteilerfreie Ringe, also Integritätsringe. Dort lassen sich irreduzible Elemente definieren. Sie sind unzerlegbar, aber nicht automatisch prim; Primelemente bilden eine Teilmenge der irreduziblen Elemente. Zerlegungen in irreduzible Elemente sind in Integritätsringen nicht notwendig eindeutig. Strukturen, in denen solche Produktzerlegungen eindeutig sind, heißen faktorielle Ringe; sie sind ZPE-Ringe. In ihnen folgt auch die Äquivalenz von irreduzibel und prim. Ein anderer Ansatz arbeitet mit Primidealen.

Beispiele zeigen, warum diese Unterscheidungen wichtig sind. Im Integritätsring Z[√-5] sind 2, 3 und 1 ± √-5 irreduzibel, aber keine Primelemente, und keine zwei davon sind zueinander assoziiert. Es gilt 6 = 2 · 3 = (1 + √-5) · (1 - √-5), daher kann man dort nicht von einer Primfaktorzerlegung sprechen. Im Polynomring K[x] über einem Körper K ist dagegen jedes nichtkonstante Polynom im Wesentlichen eindeutig als Produkt von Primpolynomen darstellbar. Auch in den gaußschen Zahlen und den Eisenstein-Zahlen existiert außer für 0 stets eine Primfaktorzerlegung.

Anwendungen

Aus den Primfaktorzerlegungen zweier Zahlen kann man erkennen, ob die eine Zahl durch die andere teilbar ist. Außerdem lassen sich das kleinste gemeinsame Vielfache (kgV) und der größte gemeinsame Teiler (ggT) leicht bestimmen. In der Bruchrechnung kann man Brüche mit dem ggT von Zähler und Nenner kürzen. Beim Addieren und Subtrahieren von Brüchen erweitert man die Nenner auf das kgV.

Aus der kanonischen Primfaktorzerlegung n = ∏(k=1 bis M) pk^ek erhält man die Anzahl T der Teiler von n, indem man alle Exponenten um 1 erhöht und die Ergebnisse multipliziert: T = ∏(k=1 bis M)(ek + 1).

In der Kryptographie spielen Primzahlen eine wichtige Rolle. Verschlüsselungssysteme wie RSA beruhen darauf, dass kein effizientes Faktorisierungsverfahren bekannt ist. Es ist innerhalb von Sekunden möglich, zwei 500-stellige Primzahlen zu finden und miteinander zu multiplizieren. Aus dem entstehenden 999- oder 1000-stelligen Produkt die beiden Primfaktoren zurückzugewinnen, würde mit heutigen Methoden dagegen sehr lange dauern.

Primfaktorzerlegungen eignen sich auch zur Definition von Gödelnummern. Für jede Aufzählung von Primzahlen p1, p2, … ohne Wiederholung ist die Abbildung (e1, e2, …, eM) ↦ p1^e1 · p2^e2 … pM^eM injektiv und berechenbar, wenn e1, e2, …, eM-1 ≥ 0 und eM > 0 gelten. Durch Primfaktorzerlegung ist auch die Umkehrfunktion berechenbar.