Das Ergebnis der Primfaktorzerlegung verstehen
Die folgende Tabelle zeigt die Primfaktorzerlegungen einiger geläufiger Zahlen und veranschaulicht damit die Exponentenschreibweise.
| Zahl | Primfaktorzerlegung | Anzahl der Teiler |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (eine Primzahl) | 17 (sie selbst, Exponent 1) | 2 |
| 1024 | 2¹⁰ | 11 |
- Die Zerlegung einer Primzahl besteht schlicht aus ihr selbst mit dem Exponenten 1, und sie besitzt stets genau 2 Teiler: 1 und sich selbst. Genau dies ist die definierende Eigenschaft einer Primzahl.
- Die Zahl 1 ist weder prim noch zusammengesetzt und besitzt keine Primfaktorzerlegung (sie ist das leere Produkt); dieser Rechner verlangt daher eine Eingabe von mindestens 2.
- Bei sehr großen Zahlen wird die Probedivision rechnerisch langsam, da sie mögliche Primzahlen bis zur Quadratwurzel der Zahl prüfen muss — deshalb ist die Zerlegung äußerst großer Zahlen mit Hunderten von Stellen rechnerisch schwer und bildet die Sicherheitsgrundlage der RSA-Verschlüsselung.
Was ist eine Primfaktorzerlegung?
Die Primfaktorzerlegung ist das Verfahren, eine ganze Zahl in jene Primzahlen zu zerlegen, deren Produkt sie ergibt. Eine Primzahl ist eine ganze Zahl größer als 1 mit genau zwei positiven Teilern, nämlich 1 und sich selbst (2, 3, 5, 7, 11, 13, ... sind die ersten Primzahlen). So zerfällt etwa 360 in 2³ × 3² × 5, also 360 = 2×2×2×3×3×5.
Der Fundamentalsatz der Arithmetik, eines der Grundergebnisse der Zahlentheorie, garantiert, dass jede ganze Zahl größer als 1 genau eine Primfaktorzerlegung besitzt, abgesehen von der Reihenfolge der notierten Faktoren. Diese Eindeutigkeit macht die Primfaktorzerlegung zu einer wohldefinierten, verlässlichen Operation und nicht zu einer von mehreren gleichermaßen gültigen Antworten.
Die Primfaktorzerlegung trägt zentrale Bereiche der Mathematik und Informatik: Sie dient dazu, den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache zu bestimmen, sämtliche Teiler einer Zahl zu ermitteln sowie Brüche und Wurzeln zu vereinfachen — und bei sehr großen Zahlen bildet ihre rechnerische Schwierigkeit die mathematische Grundlage der RSA-Verschlüsselung, die darauf beruht, dass sich eine große Zahl weit schwerer zerlegen als aus ihren Faktoren zusammensetzen lässt.
So verwenden Sie diesen Rechner für die Primfaktorzerlegung
- Geben Sie eine ganze Zahl von mindestens 2 ein (höchstens 1 Billion).
- Der Rechner dividiert nach dem üblichen Verfahren der Probedivision wiederholt durch den jeweils kleinstmöglichen Primfaktor, bis nur noch 1 übrig bleibt.
- Lesen Sie die Primfaktorzerlegung in Exponentenschreibweise ab (etwa 2³ × 3² × 5), wobei jeder Exponent angibt, wie oft die betreffende Primzahl im Produkt auftritt.
- Betrachten Sie die Gesamtzahl der positiven Teiler der Zahl sowie die Summe all dieser Teiler — beide ergeben sich unmittelbar aus der Primfaktorzerlegung.
So werden Primfaktorzerlegung, Teileranzahl und Teilersumme berechnet
Die Probedivision ermittelt die Primfaktorzerlegung, indem sie ab 2 nacheinander mögliche Primzahlen prüft, die Zahl durch jede Primzahl so oft teilt, wie diese ohne Rest aufgeht, und danach zur nächsten Kandidatin übergeht. Rechenbeispiel: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45 (nicht mehr durch 2 teilbar, also tritt 2 dreimal auf); 45 ÷ 3 = 15, ÷3 = 5 (nicht mehr durch 3 teilbar, also tritt 3 zweimal auf); 5 ÷ 5 = 1 (5 tritt einmal auf). Ergebnis: 360 = 2³ × 3² × 5.
Ist die Primfaktorzerlegung n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ bekannt, so erhält man die Gesamtzahl der positiven Teiler (einschließlich 1 und n selbst), indem man zu jedem Exponenten 1 addiert und die Ergebnisse multipliziert: (e₁+1) × (e₂+1) × ... × (eₖ+1). Rechenbeispiel für 360 = 2³ × 3² × 5¹: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 Teiler.
Die Summe aller Teiler ergibt sich aus der multiplikativen Formel der Teilersumme: Jede Primzahlpotenz p^e der Zerlegung steuert (p^(e+1) − 1) ÷ (p − 1) bei — die Summe der geometrischen Reihe 1 + p + p² + ... + p^e —, und diese Beiträge werden über alle Primfaktoren hinweg multipliziert. Rechenbeispiel für 360: Der Term 2³ steuert (2⁴−1)/(2−1) = 15 bei, der Term 3² steuert (3³−1)/(3−1) = 13 bei und der Term 5¹ steuert (5²−1)/(5−1) = 6 bei; die Multiplikation 15 × 13 × 6 = 1170 ergibt die Summe aller 24 Teiler von 360.
Häufige Fehler
- Die Zerlegung abbrechen, bevor 1 erreicht ist — jeder gefundene Faktor muss vollständig herausdividiert werden und nicht bloß ein einziges Mal, bevor man zur nächsten Kandidatin übergeht.
- Die 1 als Primzahl behandeln — nach heutiger mathematischer Konvention ist 1 weder prim noch zusammengesetzt, und ihre Aufnahme in eine Zerlegung würde die vom Fundamentalsatz der Arithmetik garantierte Eindeutigkeit verletzen.
- Vergessen, dass für die Teileranzahl der Exponent und nicht allein die Primzahl selbst maßgeblich ist — die Formel verwendet für jede Primzahl (Exponent + 1) und nicht bloß die Anzahl der verschiedenen Primzahlen.
- Annehmen, jede große Zahl besitze kleine Primfaktoren — viele große Zahlen, insbesondere Produkte zweier großer Primzahlen, besitzen überhaupt keine kleinen Faktoren, und genau diese Eigenschaft macht sie für kryptografische Anwendungen nützlich.
Häufig gestellte Fragen
Wie bestimmt man die Primfaktorzerlegung einer Zahl?
Man teilt die Zahl wiederholt durch die kleinste Primzahl, die ohne Rest aufgeht, bleibt bei dieser Primzahl, solange sie ohne Rest teilt, geht dann zur nächsten Primzahl über und wiederholt dies, bis der verbleibende Quotient 1 beträgt. Für 360 teilt man dreimal durch 2 (360→180→90→45), danach zweimal durch 3 (45→15→5) und schließlich einmal durch 5 (5→1), woraus 360 = 2³ × 3² × 5 folgt.
Wie viele Teiler besitzt eine Zahl?
Man addiert zu jedem Exponenten der Primfaktorzerlegung 1 und multipliziert die Ergebnisse. Für 360 = 2³ × 3² × 5¹ beträgt die Teileranzahl (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. Gezählt werden dabei alle positiven Teiler, einschließlich 1 und der Zahl selbst.
Was besagt der Fundamentalsatz der Arithmetik?
Der Fundamentalsatz der Arithmetik besagt, dass sich jede ganze Zahl größer als 1 auf genau eine Weise als Produkt von Primzahlen schreiben lässt, abgesehen von der Reihenfolge der aufgeführten Primzahlen. Diese Eindeutigkeit macht die Primfaktorzerlegung zu einer wohldefinierten Operation statt zu einer von mehreren gleichermaßen gültigen Antworten und trägt weite Teile der Zahlentheorie.
Ist 1 eine Primzahl?
Nein. Nach heutiger mathematischer Konvention ist 1 weder prim noch zusammengesetzt. Eine Primzahl ist dadurch definiert, dass sie genau zwei verschiedene positive Teiler besitzt, nämlich 1 und sich selbst; die Zahl 1 besitzt hingegen nur einen positiven Teiler, sich selbst, und erfüllt die Definition daher nicht. Der Ausschluss der 1 ist zudem nötig, damit der Fundamentalsatz der Arithmetik gilt, da sich eine Zahl sonst mit beliebig vielen zusätzlichen Faktoren 1 zerlegen ließe.
Warum ist die Primfaktorzerlegung für die Verschlüsselung wichtig?
Die heutige RSA-Verschlüsselung beruht darauf, dass sich zwei große Primzahlen rechnerisch leicht multiplizieren lassen, während sich ihr großes Produkt mit den derzeit bekannten klassischen Algorithmen nur sehr schwer wieder in die ursprünglichen Primzahlen zerlegen lässt. Diese Asymmetrie — leicht zu multiplizieren, schwer zu zerlegen — erlaubt es, den öffentlichen Schlüssel (das Produkt) offen zu teilen, während der private Schlüssel (die Primfaktoren) geheim und bei hinreichend großen Primzahlen in praktisch vertretbarer Zeit nicht rekonstruierbar bleibt.
Wie bestimmt man die Summe aller Teiler einer Zahl?
Ausgehend von der Primfaktorzerlegung n = p₁^e₁ × p₂^e₂ × ... berechnet man für jeden Primfaktor (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1) und multipliziert die Ergebnisse. Für 360 = 2³ × 3² × 5 liefert der Term 2³ den Wert (2⁴−1)/(2−1)=15, der Term 3² den Wert (3³−1)/(3−1)=13 und der Term 5¹ den Wert (5²−1)/(5−1)=6; die Multiplikation 15×13×6 = 1170 ergibt die Summe aller Teiler von 360.
Quellenangaben
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)