Zerlegung in Primfaktoren

Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl \(\displaystyle n\) als Produkt aus Primzahlen, die dann als Primfaktoren von \(\displaystyle n\) bezeichnet werden. Diese Darstellung ist (bis auf die Reihenfolge der Faktoren) eindeutig.

Definitionen

Sei \(\displaystyle n\) eine natürliche Zahl. Eine Zahl \(\displaystyle p\) heißt Primfaktor von \(\displaystyle n\), wenn \(\displaystyle p\) ein Teiler von \(\displaystyle n\) ist und \(\displaystyle p\) eine Primzahl ist.
Die Primfaktorzerlegung ist die Darstellung der Zahl \(\displaystyle n\) als Produkt ihrer Primfaktoren:
\(\displaystyle n = p_1 \cdot \ldots \cdot p_N = \prod\limits_{k=1}^{N}p_k\).
Da die Multiplikation kommutativ und assoziativ ist, ist die Reihenfolge der Primfaktoren aus Sicht der Zahlentheorie unwichtig. Wenn \(\displaystyle n\) selbst eine Primzahl ist, so ist es gleichzeitig selbst sein einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird \(\displaystyle n\) zusammengesetzte Zahl genannt.
Mehrfach auftretende Primfaktoren können mittels Exponenten-Schreibweise zusammengefasst werden. Sind die Primfaktoren aufsteigend geordnet, spricht man auch von der kanonischen Primfaktorzerlegung:
\(\displaystyle n=p_1^{e_1} \cdot \ldots \cdot p_M^{e_M} = \prod\limits_{k=1}^{M} p_k^{e_k}\),
wenn unter den \(\displaystyle N\) Primfaktoren \(\displaystyle M\) verschiedene sind.
Den Exponenten \(\displaystyle e_k > 0\) eines Primfaktors \(\displaystyle p_k\) nennt man auch Vielfachheit von \(\displaystyle p_k\) in \(\displaystyle n\) oder "\(\displaystyle p_k\)-Bewertung von \(\displaystyle n\)". Er gibt an, wie oft \(\displaystyle n\) durch \(\displaystyle p_k\) teilbar ist.
 
 

Beispiele für Primfaktorzerlegungen

\(\displaystyle 30 = 2 \cdot 3 \cdot 5\)
\(\displaystyle 37 = 37 \ \) (Primzahl)
\(\displaystyle 1024 = 2 \cdot \ldots \cdot 2 = 2^{10} \) (Zweierpotenz)
\(\displaystyle 63=9\cdot 7\) \(\displaystyle =3^2 \cdot 7\)
\(\displaystyle 6936 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 17 \cdot 17\), mit der kanonischen Darstellung \(\displaystyle 2^3 \cdot 3 \cdot 17^2\)
Benutzen Sie die Seite zur Berechnung der Primfaktorenzerlegung, um weitere Beispiele zu erhalten.

Eigenschaften

  • Bisher lässt die Primfaktorzerlegung von \(\displaystyle n\) wenig Rückschluss zu auf die Zerlegung von \(\displaystyle n+1\), außer dass sie keinen gemeinsamen Teiler haben können. Verwandt mit dieser Frage 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.
  • Die durchschnittliche Anzahl von Primfaktoren für größer werdendes \(\displaystyle n\) wächst nur sehr langsam an und zwar wie \(\displaystyle \ln( \ln (n))\), also der doppelt angewendete natürliche Logarithmus. Die Anzahl der Primfaktoren ist asymptotisch normalverteilt ist mit einem Erwartungswert \(\displaystyle \ln \ln n + \mathcal{O}(1)\) und einer Standardabweichung \(\displaystyle \mathcal{O}( \sqrt{\ln \ln n})\). (Zur Notation siehe Landau-Symbole.)

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 sie leichter addieren oder subtrahieren zu können.

Kryptographie

Eine wichtige Rolle spielen Primzahlen in der Kryptographie. Viele Verschlüsselungssysteme 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.

"Offensichtlich" ist das gefährlichste Wort in der Mathematik.

Eric Temple Bell

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Primfaktorzerlegung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе