Primfaktorzerlegung - LinkFang.de





Primfaktorzerlegung


Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl [math]n[/math] als Produkt aus Primzahlen, die dann als Primfaktoren von [math]n[/math] bezeichnet werden. Diese Darstellung ist (bis auf die Reihenfolge der Faktoren) eindeutig 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.

Definitionen

Sei [math]n[/math] eine natürliche Zahl. Eine Zahl [math]p[/math] heißt Primfaktor von [math]n[/math],

wenn [math]p[/math] ein Teiler von [math]n[/math] ist und
[math]p[/math] eine Primzahl ist.

Die Primfaktorzerlegung ist die Darstellung der Zahl [math]n[/math] als Produkt ihrer Primfaktoren. Da die Multiplikation 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 [math]n[/math] selbst eine Primzahl ist, so ist sie selbst ihr einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird [math]n[/math] zusammengesetzte Zahl genannt. Die Null ist niemals Teil der multiplikativen Gruppe und wird von solchen Betrachtungen ausgeschlossen. Ein Primfaktor [math]p[/math] kann mehrfach auftreten; mehrfach auftretende Primfaktoren können mittels Exponenten-Schreibweise zusammengefasst werden. Sind die Primfaktoren aufsteigend geordnet, spricht man auch von der kanonischen Primfaktorzerlegung:

[math]n=p_1^{\;\;e_1} \cdot p_2^{\;\;e_2} \dotsm p_M^{\ \ e_M} = \prod_{k=1}^{M} p_k^{\;\;e_k}[/math]       Unter den [math]N \left(=\sum_{k=1}^{M} e_k\right)[/math] Primfaktoren sind [math]M[/math] verschiedene.

Der Exponent [math]e_k[/math] eines Primfaktors [math]p_k[/math] ist die Vielfachheit von [math]p_k[/math] in [math]n[/math] und wird auch als [math]p_k[/math]-Bewertung von [math]n[/math] bezeichnet. Er gibt an, wie oft [math]n[/math] durch [math]p_k[/math] teilbar ist.

Beispiele für Primfaktorzerlegungen

[math]30 = 2 \cdot 3 \cdot 5[/math]
[math]37 = 37 \ [/math] (Primzahl)
[math]1001 = 7 \cdot 11 \cdot 13[/math]
[math]1024 = \underbrace {2 \cdots 2}_{\text{10-mal}} = 2^{10}[/math] (Zweierpotenz)
[math]6936 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 17 \cdot 17[/math], mit der kanonischen Darstellung [math]2^3 \cdot 3 \cdot 17^2[/math]
[math]10000 = 2^4 \cdot 5^4 [/math] (Zehnerpotenz)

Fundamentalsatz der Arithmetik

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.

Beweis der Existenz

Der Eins wird das leere Produkt zugeordnet und jede Primzahl stellt selbst ihre Primfaktorzerlegung dar. Damit bleibt zu zeigen, dass alle restlichen natürlichen Zahlen tatsächlich aus Primfaktoren zusammengesetzt sind.

Angenommen, es gibt Zahlen, die sich nicht als Produkt von Primzahlen darstellen lassen, dann gibt es auch eine kleinste solche Zahl (genannt [math]n[/math]), aufgrund der Wohlordnung von [math]\N[/math]. Da [math]n[/math] dann weder die Eins noch eine Primzahl ist, besitzt [math]n[/math] einen nichttrivialen Teiler, das heißt, es existieren zwei natürliche Zahlen [math]a, b[/math] mit [math]ab=n[/math] und beide sind größer als Eins und kleiner als [math]n[/math]. Da [math]n[/math] die kleinste Zahl ist, die kein Produkt von Primfaktoren ist, müssen [math]a[/math] und [math]b[/math] also Primfaktorzerlegungen haben, etwa [math]a= \Pi p_i[/math] und [math]b = \Pi q_j[/math]. Dann ist aber [math]\Pi p_i \cdot \Pi q_j[/math] auch eine Primfaktorzerlegung von [math]n[/math], im Widerspruch zur Annahme.

Beweis der Eindeutigkeit

Angenommen, es gibt natürliche Zahlen mit jeweils mehreren unterschiedlichen Zerlegungen, dann auch wieder eine kleinste, genannt [math]n[/math]. Dies kann keine Primzahl sein und zwei Zerlegungen von [math]n[/math] können keinen gemeinsamen Primfaktor [math]p[/math] enthalten, da dann auch [math]n / p[/math] zwei verschiedene Zerlegungen hätte und kleiner als [math]n[/math] wäre, im Widerspruch zur Annahme, dass [math]n[/math] minimal ist. Es gilt also etwa [math]n = p \cdot a= q \cdot b[/math], wobei [math]p[/math] und [math]q[/math] Primzahlen sind, und es gilt [math]p \neq q, a\neq b[/math]. Das abschließende Argument ist das Lemma von Euklid: Teilt eine Primzahl ein Produkt, so auch einen der Faktoren. Da [math]n[/math] durch [math]p[/math] teilbar ist, muss einer der Faktoren der anderen Zerlegung durch [math]p[/math] teilbar sein und das ist [math]b[/math], denn [math]q[/math] ist prim. Also taucht ein beliebiger Primfaktor stets in beiden Zerlegungen auf und damit sind sie identisch.

Eigenschaften

Verallgemeinerung

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.

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

  • In dem Integritätsring [math]\mathbb Z[\sqrt{-5}][/math] sind die Elemente [math]2,3, 1 \pm \sqrt{-5}[/math] keine Primelemente aber irreduzibel, und keine zwei sind zueinander assoziiert. Es gilt: [math]6=2\cdot 3=\left(1+\sqrt{-5}\right)\cdot\left(1-\sqrt{-5}\right)[/math]. Man kann also nicht von einer Primfaktorzerlegung sprechen.
  • Ein irreduzibles Polynom heißt Primpolynom, wenn der Leitkoeffizient gleich [math]1[/math] ist. Im Polynomring [math]K[x][/math] über einem Körper [math]K[/math] ist jedes nichtkonstante Polynom im Wesentlichen eindeutig als Produkt von Primpolynomen darstellbar.[2]
  • Sowohl in den gaußschen Zahlen als auch den Eisenstein-Zahlen existiert stets eine Primfaktorzerlegung (außer für die 0).

Praktische Anwendung

Aus der Primfaktorenzerlegung lässt sich erkennen, ob eine Zahl durch eine andere teilbar ist. Das kleinste gemeinsame Vielfache (kgV) und der größte gemeinsame Teiler (ggT) können leicht aus der Primfaktorzerlegung 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.

Kryptographie

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 sehr lange Zeit dauern.

Gödelnummern

Für jede Aufzählung von Primzahlen [math]p_1, p_2, \ldots[/math] ohne Wiederholung ist die durch

[math](e_1, e_2, \ldots, e_M) \mapsto p_1^{e_1} \cdot p_2^{e_2} \dotsm p_M^{e_M}[/math]

definierte Abbildung aller Tupel ganzer Zahlen [math]e_1, e_2, \ldots, e_{M-1} \geq 0, \ e_M \gt 0[/math] injektiv und berechenbar, durch Primfaktorzerlegung ist die Umkehrfunktion ebenfalls berechenbar. Die Abbildung eignet sich daher zur Definition von Gödelnummern.

Siehe auch

Literatur

  • Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5.

Weblinks

 Wiktionary: Primfaktorzerlegung – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise

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

Kategorien: Primzahl

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Primfaktorzerlegung (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.