Zerlegung in Primfaktoren

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

Definitionen

Sei nn eine natürliche Zahl. Eine Zahl pp heißt Primfaktor von nn, wenn pp ein Teiler von nn ist und pp eine Primzahl ist.
Die Primfaktorzerlegung ist die Darstellung der Zahl nn als Produkt ihrer Primfaktoren:
n=p1⋅…⋅pN=∏k=1Npkn = 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 nn selbst eine Primzahl ist, so ist es gleichzeitig selbst sein einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird nn 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:
n=p1e1⋅…⋅pMeM=∏k=1Mpkekn=p_1^{e_1} \cdot \ldots \cdot p_M^{e_M} = \prod\limits_{k=1}^{M} p_k^{e_k},
wenn unter den NN Primfaktoren MM verschiedene sind.
Den Exponenten ek>0e_k > 0 eines Primfaktors pkp_k nennt man auch Vielfachheit von pkp_k in nn oder "pkp_k-Bewertung von nn". Er gibt an, wie oft nn durch pkp_k teilbar ist.
 
 

Beispiele für Primfaktorzerlegungen

30=2⋅3⋅530 = 2 \cdot 3 \cdot 5
37=37 37 = 37 \ (Primzahl)
1024=2⋅…⋅2=2101024 = 2 \cdot \ldots \cdot 2 = 2^{10} (Zweierpotenz)
63=9⋅763=9\cdot 7 =32⋅7=3^2 \cdot 7
6936=2⋅2⋅2⋅3⋅17⋅176936 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 17 \cdot 17, mit der kanonischen Darstellung 23⋅3⋅1722^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 nn wenig Rückschluss zu auf die Zerlegung von n+1n+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 nn wächst nur sehr langsam an und zwar wie ln⁡(ln⁡(n))\ln( \ln (n)), also der doppelt angewendete natürliche Logarithmus. Die Anzahl der Primfaktoren ist asymptotisch normalverteilt ist mit einem Erwartungswert ln⁡ln⁡n+O(1)\ln \ln n + \mathcal{O}(1) und einer Standardabweichung O(ln⁡ln⁡n)\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.

Alle Pädagogen sind sich darin einig: man muß vor allem tüchtig Mathematik treiben, weil ihre Kenntnis fürs Leben größten direkten Nutzen gewährt.

Felix Klein

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е
Datenschutzerklärung

 

Teilbarkeit