„Primfaktorzerlegung“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
→‎Existenz: Keine Verbesserung des Artikels
Zeile 1: Zeile 1:
Die '''Primfaktorzerlegung''' ist die Darstellung einer [[natürliche Zahl|natürlichen Zahl]] <math>n</math> als [[Produkt (Mathematik)|Produkt]] von [[Primzahl]]en. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Sie zählt zu den grundlegenden und klassischen Werkzeugen der [[Zahlentheorie]].
Die '''Primfaktorzerlegung''' ist die Darstellung einer [[natürliche Zahl|natürlichen Zahl]] <math>n</math> als [[Produkt (Mathematik)|Produkt]] von [[Primzahl]]en. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Sie zählt zu den grundlegenden und klassischen Werkzeugen der [[Zahlentheorie]].


Ja sie haben recht ich selbst bin mathe lehrer an der realschule kulmbach und kenne mich aus
== 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 [[Teilbarkeit|Teiler]] von <math>n</math> ist und
: <math>p</math> eine [[Primzahl]] ist.

Die Primfaktorzerlegung ist das Produkt der <math>N</math> Primfaktoren von <math>n</math>:
:<math>n= p_1 \cdot \ldots \cdot p_N = \prod_{k=1}^{N}p_k</math> .

Die Primfaktorzerlegung hängt dabei nicht von der Reihenfolge der Faktoren ab, da die [[Multiplikation]] [[Kommutativgesetz|kommutativ]] ist. Da [[Eins]] keine Primzahl ist, hat sie auch keinen Primfaktor. Ihre Primfaktorzerlegung kann als [[leeres Produkt]] betrachtet werden. Wenn <math>n</math> selbst eine Primzahl ist, so ist es gleichzeitig selbst sein einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird <math>n</math> [[zusammengesetzte Zahl]] genannt. Die [[Null]] ist niemals Teil der [[Multiplikative Gruppe|multiplikativen Gruppe]] und wird von solchen Betrachtungen ausgeschlossen.

Mehrfach auftretende Primfaktoren können mittels [[Potenz (Mathematik)|Exponenten]]-Schreibweise zusammengefasst werden. Sind die Primfaktoren aufsteigend [[Ordnungsrelation|geordnet]], spricht man auch von der ''kanonischen Primfaktorzerlegung'':
:<math>n=p_1^{e_1} \cdot \ldots \cdot p_M^{e_M} = \prod_{k=1}^{M} p_k^{e_k}</math>, wenn unter den <math>N</math> Primfaktoren <math>M</math> verschiedene sind.

Den Exponenten <math>e_k > 0</math> eines Primfaktors <math>p_k</math> nennt man auch „Vielfachheit von <math>p_k</math> in <math>n</math>“ oder „<math>p_k</math>-Bewertung von <math>n</math>“ (siehe [[Bewertungstheorie]]). 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>1024 = 2 \cdot \ldots \cdot 2 = 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>

=== 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 [[Zahlentheorie#elementare Zahlentheorie|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.

==== Existenz ====

Um die Existenz einer Primfaktorzerlegung zu zeigen, werden die positiven natürlichen Zahlen zweckmäßigerweise in drei Gruppen unterteilt: die Eins, die Primzahlen und der Rest, die [[Zusammengesetzte Zahl|zusammengesetzten Zahlen]]. Die Eins entspricht definitionsgemäß dem [[Leeres Produkt|leeren Produkt]]. Jede Primzahl ist gleich dem Produkt aus nur einem Faktor: der Primzahl selbst. Es bleibt noch zu zeigen, dass sich auch die zusammengesetzten Zahlen als Produkt von Primzahlen darstellen lassen.

Angenommen, es gäbe zusammengesetzte Zahlen, die sich nicht als Produkt von Primzahlen darstellen ließen, dann gäbe es auch eine kleinste solche Zahl. Diese Zahl sei <math>n</math>. Da <math>n</math> weder die Eins noch eine Primzahl ist, besitzt sie einen Teiler <math>a</math> mit <math>1 < a < n</math> und lässt sich deshalb als Produkt <math>n = a \cdot b</math> mit <math>1 < b < n</math> schreiben. Da es sich dabei nicht um das Produkt zweier Primzahlen handelt, muss <math>a</math> oder <math>b</math> eine zusammengesetzte Zahl sein. Diese Zahl wäre kleiner als <math>n</math> und stünde damit im Widerspruch zur Annahme, dass <math>n</math> die kleinste zusammengesetzte Zahl ist.

==== Eindeutigkeit ====

Gäbe es unterschiedliche Zerlegungen von natürlichen Zahlen, könnte die kleinste Zahl mit unterschiedlichen Zerlegungen betrachtet werden. Dies führt zu einem Widerspruch, da gezeigt werden kann, dass in diesem Fall diese kleinste Zahl dividiert durch einen Primfaktor ebenfalls mehrere Zerlegungen haben muss. Dies folgt aus einem [[Hilfssatz]]: Teilt eine Primzahl ein Produkt, so auch einen der Faktoren.<ref>{{Literatur| Autor= Jürgen Wolfart | Titel=Einführung in die Algebra und Zahlentheorie | Verlag= Vieweg | Jahr=1996 | Ort= Braunschweig/Wiesbaden |ISBN=3-528-07286-5 | Seiten= 6-7}}</ref> Dieser ist wiederum eine Folgerung aus dem [[Lemma von Bézout]] und dient als Grundlage für eine verallgemeinerte Definition von Primzahlen, den [[Primelement]]en.

=== Eigenschaften ===

* Bisher lässt die Primfaktorzerlegung von <math>n</math> keinerlei Rückschluss zu auf Zerlegung von <math>n+1</math>, verwandt mit dieser Fragestellung sind [[Primzahlzwilling]]e bzw. [[Primzahllücke]]n.
* Um die Primfaktorzerlegung einer Zahl zu berechnen, stehen mehrere [[Faktorisierungsverfahren]] zur Verfügung, die [[Nichttrivialer Teiler|nichttriviale Teiler]] ganzer Zahlen berechnen. Diese Aufgabenstellung ist als [[Faktorisierungsproblem für ganze Zahlen]] bekannt und kann mit den bisher bekannten Methoden nicht [[Effizienz (Informatik)|effizient]] berechnet werden, worauf weltweit Sicherheitskonzepte beruhen, insbesondere in der modernen [[Kryptographie]]. Siehe auch [[Primzahltest]].
* [[Godfrey Harold Hardy|Hardy]] bewies mehrere erstaunliche [[Statistik|statistische]] Erkenntnisse zum Thema, unter anderem dass die [[Durchschnitt|durchschnittliche]] Anzahl von Primfaktoren für größer werdendes <math>n</math> nur sehr langsam anwächst und zwar wie <math>\ln \ln n</math>, also der doppelt angewendete [[natürlicher Logarithmus|natürliche Logarithmus]]. Der [[Satz von Erdős-Kac]] besagt darüber hinaus, dass die Anzahl der Primfaktoren [[Normalverteilung|asymptotisch normalverteilt]] ist mit einem [[Erwartungswert]] <math>\ln \ln n + \mathcal{O}(1)</math> und einer [[Standardabweichung]] <math>\mathcal{O}( \sqrt{\ln \ln n})</math>.<ref>{{Literatur | Autor= Thomas Kantke
| Herausgeber=
| Titel= Billige und teure Zahlen
| Sammelwerk= [[Spektrum der Wissenschaft]] - SPEZIAL: Omega
| Nummer= 4/2003
| Auflage=
| Verlag= Spektrum der Wissenschaft
| Ort= Heidelberg
| Jahr= 2003
| Seiten= 68-74
| Online=
| Zugriff=
| Kommentar=
}}
</ref> (Zur Notation siehe [[Landau-Symbole]].)


== Verallgemeinerung ==
== Verallgemeinerung ==

Version vom 6. Mai 2010, 15:20 Uhr

Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl als Produkt von Primzahlen. Diese Darstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Sie zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie.

Ja sie haben recht ich selbst bin mathe lehrer an der realschule kulmbach und kenne mich aus

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 im Wesentlichen 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, ist der Ring auch noch nullteilerfrei (also ein Integritätsbereich), so gibt es zusätzlich irreduzible Elemente, die nicht prim genannt werden können. Sie werden anders definiert, sind aber trotzdem unzerlegbar und enthalten die Primelemente als echte Teilmenge.

Eine im wesentlichen eindeutige Zerlegung bedeutet ohne Beachtung der Reihenfolge der Faktoren (da der Ring kommutativ ist) und Multiplikation mit Einheiten (bei ganzen Zahlen ist das , wodurch das Vorzeichen bestimmt wird.) In allgemeinen Integritätsbereichen kann man nicht von Primfaktorzerlegungen sprechen, da diese Eindeutigkeit nicht gegeben ist. Stattdessen spricht man von Zerlegungen in irreduzible Faktoren. 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.

Beispiele

Auch auf dem Dreiecksgitter der Eisenstein-Zahlen existiert für jeden Gitterpunkt eine Primfaktorzerlegung
  • In dem Integritätsbereich 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.[1]
  • Sowohl in den gaußschen Zahlen als auch den Eisenstein-Zahlen existiert stets eine Primfaktorzerlegung, natürlich außer für die 0. 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.

Fußnoten

  1. ↑ Jürgen Wolfart: Einführung in die Algebra und Zahlentheorie. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5, S. 72, 37.
Abgerufen von „https://de.wikipedia.org/w/index.php?title=Primfaktorzerlegung&oldid=74036221“