Primfaktorzerlegung

Darstellung einer natürlichen Zahl als Produkt aus Primzahlen

Die Primfaktorzerlegung ist die Darstellung einer positiven natürlichen Zahl als Produkt aus Primzahlen die dann als Primfaktoren von bezeichnet werden. Diese Darstellung ist eindeutig (bis auf die Reihenfolge der Faktoren; es ist eine Multimenge) und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie. Sie ist Gegenstand des Fundamentalsatzes der Arithmetik. Es ist bisher kein effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten.

Zahl Faktoren

einzeln

Anzahl Faktoren

kanonisch

1 0
2 1
3 1
4 2
5 1
6 2
7 1
8 3
9 2
10 2
11 1
12 3
13 1
14 2
15 2
16 4
17 1
18 3
19 1
20 3

Definitionen

Bearbeiten

Sei   eine natürliche Zahl. Eine Zahl   heißt Primfaktor von  ,

  • wenn   ein Teiler von   ist und
  •   eine Primzahl ist.

Die Primfaktorzerlegung ist die Darstellung der Zahl   als Produkt ihrer Primfaktoren. Da die Multiplikation für reelle Zahlen kommutativ und assoziativ ist, ist die Reihenfolge der Primfaktoren aus Sicht der Zahlentheorie unwichtig. Die Primfaktorzerlegung der Eins kann als leeres Produkt betrachtet werden. Wenn   selbst eine Primzahl ist, so ist sie selbst ihr einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird   als zusammengesetzte Zahl bezeichnet. Null ist niemals Teil der multiplikativen Gruppe und wird von solchen Betrachtungen ausgeschlossen. Ein Primfaktor kann mehrfach auftreten und daher muss in gewissen Kontexten die Zählweise (mit Vielfachheiten oder lediglich wie viele verschiedene) angegeben werden. Mehrfach auftretende Primfaktoren können mittels Exponentenschreibweise gut lesbar zusammengefasst werden. Sind die   verschiedenen Primfaktoren   aufsteigend geordnet ( ), spricht man auch von der kanonischen Primfaktorzerlegung:

 

Der Exponent   eines Primfaktors   ist die Vielfachheit von   in   und wird auch als  -Bewertung von   bezeichnet. Er gibt an, wie oft   durch   teilbar ist. Mit Vielfachheit gezählt hat   dann   Primfaktoren.

Eine äquivalente Schreibweise ist

 

wobei die Exponenten   nur für endlich viele   von 0 verschieden sind.

Beispiele für Primfaktorzerlegungen

Bearbeiten
 
  (Primzahl)
 
  (Zweierpotenz)
 , mit der kanonischen Darstellung  
  (Zehnerpotenz)

Fundamentalsatz der Arithmetik

Bearbeiten

Die Aussagen für Existenz der Primfaktorzerlegung für jede natürliche Zahl und deren Eindeutigkeit in der kanonischen Darstellung sind der Fundamentalsatz der Arithmetik, auch Hauptsatz der elementaren Zahlentheorie genannt. Beide Aussagen werden getrennt formuliert und bewiesen. Die Beweise sind elementar, werden klassisch als Widerspruchsbeweis formuliert und nutzen die Wohlordnung der natürlichen Zahlen. 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.[1]

Beweis der Existenz

Bearbeiten

Für   und   ist nichts zu zeigen (vgl. Teilbarkeit). Jede Primzahl ist selbst ihre Primfaktorzerlegung. Zu zeigen bleibt, dass für die restlichen natürlichen Zahlen eine Primfaktorzerlegung existiert.

Angenommen werde die Existenz solcher restlicher Zahlen, für die keine Primfaktorzerlegung existiert. Aufgrund der Wohlordnung von   existiert dann eine kleinste solche Zahl  . Da   keine Primzahl ist, hat   nichttriviale Teiler   mit  , wobei  . Da   die kleinste Zahl ist, für die keine Primfaktorzerlegung existiert, existiert für   (bzw.  ) eine Primfaktorzerlegung   (bzw.  ). Dann ist   eine Primfaktorzerlegung von  , im Widerspruch zur Annahme.

Beweis der Eindeutigkeit

Bearbeiten

Für  ,   und Primzahlen ist nichts zu zeigen. Zu zeigen bleibt, dass für die restlichen natürlichen Zahlen höchstens eine Primfaktorzerlegung existiert.

Angenommen werde die Existenz solcher restlicher Zahlen, für die jeweils mehrere unterschiedliche Primfaktorzerlegungen koexistieren. Aufgrund der Wohlordnung von   existiert dann eine kleinste solche Zahl  . Mehrere unterschiedliche Primfaktorzerlegungen von   koexistieren höchstens dann (widerspruchsfrei), wenn zwei unterschiedliche Primfaktorzerlegungen   und   von   koexistieren. Außerdem ist   nicht prim, also  

Außerdem kann man   annehmen. Denn gäbe es einen gemeinsamen Faktor, nach Umsortierung zum Beispiel  , so wäre  . Da   minimale Zahl mit zwei verschiedenen Faktoren ist, wäre  , und somit wären obige Primfaktorzerlegungen identisch. Ein Widerspruch zur Wahl von  .

Da   das Produkt   teilt, teilt   nach dem Lemma von Euklid auch einen geeignet gewählten Faktor dieses Produkts. Dies kann allerdings kein Primfaktor   sein, denn sonst wäre  . Also teilt   ein Produkt aus nur   verschiedenen Elementen aus  . Dieses Argument kann man wiederholen, das heißt   teilt ein Produkt aus   verschiedenen Elementen aus   und so weiter. Schließlich muss   ein Element aus   teilen. Da es sich um Primzahlen handelt, ist somit  . Dies ist ein Widerspruch.

Eigenschaften

Bearbeiten
  •   und   können keine gemeinsamen Primfaktoren haben.
  • Um die Primfaktorzerlegung einer Zahl zu berechnen, stehen mehrere Faktorisierungsverfahren zur Verfügung, die nichttriviale Teiler ganzer Zahlen berechnen. Diese Aufgabenstellung ist als Faktorisierungsproblem für ganze Zahlen bekannt und kann mit den bisher bekannten Methoden nicht effizient berechnet werden, worauf weltweit Sicherheitskonzepte beruhen, insbesondere in der modernen Kryptographie. Siehe auch Primzahltest.
  • Hardy bewies mehrere erstaunliche statistische Erkenntnisse zum Thema, unter anderem, dass die durchschnittliche Anzahl von Primfaktoren für größer werdendes   nur sehr langsam anwächst und zwar wie  , also der doppelt angewendete natürliche Logarithmus. Der Satz von Erdős-Kac besagt darüber hinaus, dass die Anzahl der Primfaktoren asymptotisch normalverteilt ist mit einem Erwartungswert   und einer Standardabweichung  .[2] (Zur Notation siehe Landau-Symbole.)
  • Die Funktion  , die jede natürliche Zahl auf die Anzahl ihrer paarweise verschiedenen Primfaktoren abbildet, ist ein Beispiel für eine arithmetische Funktion, die additiv aber nicht streng additiv ist. Sie ist zu unterscheiden von der Teileranzahlfunktion, die alle Teiler einer Zahl zählt, nicht nur die Primteiler. Beispielsweise ist  , denn die Primfaktorzerlegung enthält zwei verschiedene Primzahlen: 2 und 5. Mit obiger Definition gilt:  .
  • Der asymptotische arithmetische Mittelwert der maximalen Exponenten der Primfaktorzerlegungen der Zahlen 1, 2, 3, … ist die Niven-Konstante (rund 1,7), der asymptotische arithmetische 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   angegeben.

Verallgemeinerung

Bearbeiten

Es gibt mehrere Möglichkeiten, Primzahlen zu verallgemeinern. Die bekannteste Anwendung sind die ganzen Zahlen, Primzahlen können dort auch ein negatives Vorzeichen haben. Andererseits ist dies schon ein spezielles Beispiel, da auch dort die Primfaktorzerlegung (bis auf Vorzeichen und Reihenfolge) eindeutig ist.

Genauso eindeutig ist die Primfaktorzerlegung in den von 0 verschiedenen rationalen Zahlen  

 

wobei die ganzzahligen Exponenten   nur für endlich viele   von 0 verschieden sind.

Ein allgemeiner Ansatz verlangt mindestens einen Begriff der Teilbarkeit innerhalb der mathematischen Struktur. David Hilbert bewies, dass für die gewünschte Eindeutigkeit eine additive Struktur zwingend notwendig ist. Üblicherweise wird von einem kommutativen Ring mit Eins ausgegangen, dort können Primelemente definiert werden: Ein Element ist prim, wenn Euklids Lemma dafür gilt. Damit ist nicht garantiert, dass es für alle Elemente des Rings Zerlegungen in Primelemente gibt, aber wenn es welche gibt, dann sind sie eindeutig. Um die Existenz zu sichern, ist eine weitere Eigenschaft notwendig: die Unzerlegbarkeit. Um die definieren zu können, schränkt man die Struktur weiter ein und betrachtet nullteilerfreie Ringe (also Integritätsringe), dort können zusätzlich irreduzible Elemente definiert werden, die aber nicht prim genannt werden können. Sie sind unzerlegbar und enthalten die Primelemente als Teilmenge.

Zerlegungen in irreduzible Elemente in einem Integritätsring sind nicht notwendigerweise eindeutig. Um eine Struktur zu erhalten, in der die Produkt-Zerlegungen eindeutig sind, muss man diese Eindeutigkeit explizit fordern, was zur Definition von faktoriellen Ringen führt. Mit dieser Forderung lässt sich dann aber dort auch schon die Äquivalenz von irreduzibel und prim folgern: Faktorielle Ringe sind ZPE-Ringe. Ein etwas anderer Ansatz wird mit Primidealen verfolgt.

Beispiele

Bearbeiten
 
Auch auf dem Dreiecksgitter der Eisenstein-Zahlen existiert für jeden Gitterpunkt eine Primfaktorzerlegung
  • In dem Integritätsring   sind die Elemente   keine Primelemente aber irreduzibel, und keine zwei sind zueinander assoziiert. Es gilt:  . Man kann also nicht von einer Primfaktorzerlegung sprechen.
  • Ein irreduzibles Polynom heißt Primpolynom, wenn der Leitkoeffizient gleich   ist. Im Polynomring   über einem Körper   ist jedes nichtkonstante Polynom im Wesentlichen eindeutig als Produkt von Primpolynomen darstellbar.[3]
  • Sowohl in den gaußschen Zahlen als auch den Eisenstein-Zahlen existiert stets eine Primfaktorzerlegung (außer für die 0).

Praktische Anwendung

Bearbeiten

Aus den Primfaktorzerlegungen zweier Zahlen lässt sich erkennen, ob die eine Zahl durch die andere teilbar ist. Das kleinste gemeinsame Vielfache (kgV) und der größte gemeinsame Teiler (ggT) können leicht aus den Primfaktorzerlegungen bestimmt werden. In der Bruchrechnung können Brüche durch den ggT von Zähler und Nenner gekürzt werden. Beim Addieren und Subtrahieren werden zwei Brüche auf das kgV der Nenner erweitert.

Aus der kanonischen Primfaktorzerlegung

 

erhält man die Anzahl   der Teiler von  , indem man die Exponenten um Eins erhöht und dann miteinander multipliziert:

 

Kryptographie

Bearbeiten

Eine wichtige Rolle spielen Primzahlen in der Kryptographie. Verschlüsselungssysteme wie RSA basieren darauf, dass kein effizientes Faktorisierungsverfahren bekannt ist. So ist es innerhalb von Sekunden problemlos möglich, zwei 500-stellige Primzahlen zu finden und miteinander zu multiplizieren. Mit den heutigen Methoden würde die Rückgewinnung der beiden Primfaktoren aus diesem 999- oder 1000-stelligen Produkt dagegen eine sehr lange Zeit dauern.

Gödelnummern

Bearbeiten

Für jede Aufzählung von Primzahlen   ohne Wiederholung ist die durch

 

definierte Abbildung aller Tupel ganzer Zahlen   injektiv und berechenbar, durch Primfaktorzerlegung ist die Umkehrfunktion ebenfalls berechenbar. Die Abbildung eignet sich daher zur Definition von Gödelnummern.

Literatur

Bearbeiten
  • Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5.
Bearbeiten
Wiktionary: Primfaktorzerlegung – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise

Bearbeiten
  1. Franz Lemmermeyer: Zur Zahlentheorie der Griechen (PDF; 208 kB)
  2. Thomas Kantke: Billige und teure Zahlen. In: Spektrum der Wissenschaft – SPEZIAL: Omega. Nr. 4/2003. Spektrum der Wissenschaft, Heidelberg 2003, S. 68–74.
  3. Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5, S. 72, 37.