„Primfaktorzerlegung“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
Xario (Diskussion | Beiträge) →Beispiele: danke daniel5Ko |
→Verallgemeinerung: andersrum |
||
(Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
Zeile 59: | Zeile 59: | ||
== Verallgemeinerung == |
== Verallgemeinerung == |
||
Es gibt mehrere Möglichkeiten, Primzahlen zu verallgemeinern. Die bekannteste Anwendung sind die [[ganze Zahl|ganzen Zahlen]], Primzahlen können dort auch ein negatives Vorzeichen haben. Andererseits ist dies schon ein spezielles Beispiel, da auch dort die Primfaktorzerlegung |
Es gibt mehrere Möglichkeiten, Primzahlen zu verallgemeinern. Die bekannteste Anwendung sind die [[ganze Zahl|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 [[Addition|additive Struktur]] zwingend notwendig ist. Üblicherweise wird von einem [[Ringtheorie#Spezialfälle|kommutativen Ring mit Eins]] ausgegangen, dort können [[Primelement]]e definiert werden, (für die dann [[Lemma von Euklid|Euklids Lemma]] gilt), ist der Ring auch noch [[Nullteiler|nullteilerfrei]] (also ein [[Integritätsring]]), |
Ein allgemeiner Ansatz verlangt mindestens einen Begriff der Teilbarkeit innerhalb der mathematischen Struktur. [[David Hilbert]] bewies, dass für die gewünschte Eindeutigkeit eine [[Addition|additive Struktur]] zwingend notwendig ist. Üblicherweise wird von einem [[Ringtheorie#Spezialfälle|kommutativen Ring mit Eins]] ausgegangen, dort können [[Primelement]]e definiert werden, (für die dann [[Lemma von Euklid|Euklids Lemma]] gilt), ist der Ring auch noch [[Nullteiler|nullteilerfrei]] (also ein [[Integritätsring]]), kann es zusätzlich ''[[irreduzibles Element|irreduzible Elemente]]'' geben, die nicht prim genannt werden können. Sie werden anders definiert, sind aber trotzdem unzerlegbar und enthalten die Primelemente als Teilmenge. |
||
Für einen Ring <math>R</math> ist eine ''Zerlegung in Primelemente'' einer Zahl <math>a\in R\setminus\{0\}</math> eine Darstellung der Form <math>a=ep_1^{l_1}p_2^{l_2}\dots p_n^{l_n}</math>. Dabei ist <math>e</math> eine Einheit, <math>n\in\mathbb{N}_0, p_i\in R</math> paarweise verschiedene Primelemente und <math>l_i\in \mathbb{N}</math> Vielfachheiten. In jedem Ring mit 1 gibt es für jedes von Null verschiedene Element so eine Darstellung. In Hauptidealringen (wie die [[Polynomring]]e) und euklidischen Ringen (wie <math>\mathbb{Z}</math>) kann man zeigen, dass diese Zerlegung bis auf Reihenfolge und Multiplikation mit Einheiten eindeutig ist. |
|||
Eine ''im wesentlichen eindeutige'' Zerlegung bedeutet ohne Beachtung der Reihenfolge der Faktoren (da der Ring kommutativ ist) und Multiplikation mit [[Einheit (Mathematik)|Einheiten]] (bei ganzen Zahlen ist das <math>-1</math>, wodurch das Vorzeichen bestimmt wird.) |
|||
⚫ | In allgemeinen Integritätsringen |
||
⚫ | In allgemeinen Integritätsringen ist das nicht immer so. Man muss deren Eindeutigkeit explizit fordern, was zur Definition von [[faktorieller Ring|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-Ring]]e. Ein etwas anderer Ansatz wird mit [[Primideal]]en verfolgt. |
||
Es gilt dann die Kette von echten Implikationen für Ringe: |
|||
:<math>\text{Integritaetsring}\Leftarrow\text{Faktoriell}\Leftarrow \text{Hauptideal} \Leftarrow\text{Euklidisch}</math> |
|||
=== Beispiele === |
=== Beispiele === |
||
[[Bild:Eisenstein integer lattice.png|thumb|Auch auf dem Dreiecksgitter der [[Eisenstein-Zahlen]] existiert für jeden Gitterpunkt eine Primfaktorzerlegung]] |
[[Bild:Eisenstein integer lattice.png|thumb|Auch auf dem Dreiecksgitter der [[Eisenstein-Zahlen]] existiert für jeden Gitterpunkt eine Primfaktorzerlegung]] |
Version vom 16. Januar 2011, 20:25 Uhr
Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl als Produkt aus Primzahlen, die dann als Primfaktoren von bezeichnet werden. Diese Darstellung ist (bis auf die Reihenfolge der Faktoren) eindeutig und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie und ist Gegenstand des Fundamentalsatzes der Arithmetik. Es ist bisher kein effizientes Faktorisierungsverfahren bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten.
Definitionen
Sei eine natürliche Zahl. Eine Zahl heißt Primfaktor von ,
Die Primfaktorzerlegung ist die Darstellung der Zahl als Produkt ihrer Primfaktoren:
- .
Da die Multiplikation kommutativ ist, ist die Reihenfolge der Primfaktoren aus Sicht der Zahlentheorie unwichtig. Da Eins keine Primzahl ist, hat sie auch keinen Primfaktor. Ihre Primfaktorzerlegung kann als leeres Produkt betrachtet werden. Wenn selbst eine Primzahl ist, so ist es gleichzeitig selbst sein einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird zusammengesetzte Zahl genannt. Die Null ist niemals Teil der multiplikativen Gruppe und wird von solchen Betrachtungen ausgeschlossen.
Mehrfach auftretende Primfaktoren können mittels Exponenten-Schreibweise zusammengefasst werden. Sind die Primfaktoren aufsteigend geordnet, spricht man auch von der kanonischen Primfaktorzerlegung:
- , wenn unter den Primfaktoren verschiedene sind.
Den Exponenten eines Primfaktors nennt man auch „Vielfachheit von in “ oder „-Bewertung von “. Er gibt an, wie oft durch teilbar ist.
Beispiele für Primfaktorzerlegungen
- (Primzahl)
- (Zweierpotenz)
- , mit der kanonischen Darstellung
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. Beide Aussagen werden getrennt formuliert und bewiesen. Die Beweise sind zahlentheoretisch 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 ), aufgrund der Wohlordnung von . Da dann weder die Eins noch eine Primzahl ist, besitzt es einen Teiler, damit existieren zwei natürliche Zahlen mit und beide sind größer als Eins und kleiner als . Da die kleinste Zahl ist die kein Produkt von Primfaktoren ist, müssen und also Primfaktorzerlegungen haben, etwa und . Dann ist aber auch eine Primfaktorzerlegung von , im Widerspruch zur Annahme.
Beweis der Eindeutigkeit
Angenommen, es gibt natürliche Zahlen mit jeweils mehreren unterschiedlichen Zerlegungen, dann auch wieder eine kleinste, genannt . Dies kann keine Primzahl sein und zwei Zerlegungungen von können keinen gemeinsamen Primfaktor enthalten, da dann auch zwei verschiedene Zerlegungen hätte und kleiner als wäre, im Widerspruch zur Annahme, dass minimal ist. Es gilt also etwa , wobei und Primzahlen sind und es gilt . Das abschließende Argument ist das Lemma von Euklid: Teilt eine Primzahl ein Produkt, so auch einen der Faktoren. Da durch teilbar ist muss einer der Faktoren der anderen Zerlegung durch teilbar sein und das ist , denn ist prim. Also taucht ein beliebiger Primfaktor stets in beiden Zerlegungen auf und damit sind sie identisch.
Eigenschaften
- Bisher lässt die Primfaktorzerlegung von wenig Rückschluss zu auf die Zerlegung von , außer dass sie keinen gemeinsamen Teiler haben können. Verwandt mit dieser Fragestellung sind Primzahlzwillinge bzw. Primzahllücken.
- 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 .[1] (Zur Notation siehe Landau-Symbole.)
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, (für die dann Euklids Lemma gilt), ist der Ring auch noch nullteilerfrei (also ein Integritätsring), kann es zusätzlich irreduzible Elemente geben, die nicht prim genannt werden können. Sie werden anders definiert, sind aber trotzdem unzerlegbar und enthalten die Primelemente als Teilmenge.
Für einen Ring ist eine Zerlegung in Primelemente einer Zahl eine Darstellung der Form . Dabei ist eine Einheit, paarweise verschiedene Primelemente und Vielfachheiten. In jedem Ring mit 1 gibt es für jedes von Null verschiedene Element so eine Darstellung. In Hauptidealringen (wie die Polynomringe) und euklidischen Ringen (wie ) kann man zeigen, dass diese Zerlegung bis auf Reihenfolge und Multiplikation mit Einheiten eindeutig ist.
In allgemeinen Integritätsringen ist das nicht immer so. Man muss deren 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.
Es gilt dann die Kette von echten Implikationen für Ringe:
Beispiele
- In dem Integritätsring sind die Elemente irreduzibel und keine zwei sind zueinander assoziiert. Aber 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.[2]
- Sowohl in den gaußschen Zahlen als auch den Eisenstein-Zahlen existiert stets eine Primfaktorzerlegung, natürlich außer für die 0 und die Einheiten. Wegen der fehlenden Ordnungsstruktur auf den komplexen Zahlen kann man jedoch nicht so einfach eine Darstellung als kanonisch bezeichnen, durch die jeweils vier Einheiten, die in beiden Ringen existieren, wird es noch unübersichtlicher.
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 Primfaktorenzerlegung bestimmt werden. In der Bruchrechnung können Brüche durch den ggT von Zähler und Nenner gekürzt werden, und zwei Brüche können auf den kleinsten gemeinsamen Nenner erweitert werden, um leichter addieren oder subtrahieren zu können.
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-stelligen oder 1000-stelligen Produkt dagegen sehr lange Zeit dauern. Primzahlen werden auch bei der Programmierung von Hashtabellen verwendet.
Literatur
- Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5.
Weblinks
- Factorization database von Markus Tervooren - schnelle Verarbeitung, bis zu 200.000 Dezimalstellen
- Die Primzahlseite von Arndt Brünner - benötigt JavaScript, enthält u.a. Primfaktorzerlegung
- Prime factorisation by Henry Bottomley (1998) - benötigt JavaScript, verarbeitet Eingaben bis ca. 17 Dezimalstellen
- Factorization using the Elliptic Curve Method - Java-Applet, verarbeitet Eingaben bis 10.000 Dezimalstellen
- WolframAlpha, universeller wissenschaftlich-technischer Taschenrechner
Fußnoten
- ↑ Thomas Kantke: Billige und teure Zahlen. In: Spektrum der Wissenschaft - SPEZIAL: Omega. Nr. 4/2003. Spektrum der Wissenschaft, Heidelberg 2003, S. 68–74.
- ↑ Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5, S. 72, 37.