Was ist die Primfaktorzerlegung?
Jede natürliche Zahl größer als 1 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben. Das besagt der Hauptsatz der Arithmetik. Die Zerlegung dient zum Kürzen von Brüchen, zum Bestimmen von ggT und kgV und beim Finden aller Teiler einer Zahl.
Der Rechner teilt die Zahl der Reihe nach durch 2, 3, 5, 7 und weitere Kandidaten, bis nichts mehr aufgeht. Es genügt, bis zur Wurzel der Zahl zu prüfen. Was am Ende übrig bleibt, ist selbst eine Primzahl. Daraus berechnet er die Anzahl und die Summe aller Teiler.
Primzahlen erkennen
Eine Zahl ist eine Primzahl, wenn sie nur durch 1 und sich selbst teilbar ist. Dann besteht die Zerlegung aus der Zahl selbst, der Rechner meldet das ausdrücklich. Die Zahlen 2, 3, 5, 7, 11 und 13 sind Beispiele, die 2 ist die einzige gerade Primzahl.
Bei sehr großen Zahlen mit großen Primfaktoren dauert die Probedivision etwas länger. Für Zahlen bis eine Billion läuft die Berechnung dennoch in der Regel sofort. Die Teilerliste wird nur gezeigt, solange sie übersichtlich bleibt.
Anwendungen der Zerlegung
Mit der Primfaktorzerlegung lassen sich ggT und kgV bestimmen: Für den ggT nimmt man die gemeinsamen Primfaktoren mit dem kleineren Exponenten, für das kgV alle Primfaktoren mit dem größeren. Außerdem erkennen Sie, ob eine Zahl ein Quadrat ist, nämlich wenn alle Exponenten gerade sind.
In der Informatik spielt die Zerlegung bei Verschlüsselungsverfahren wie RSA eine Rolle, weil sich große Zahlen nur sehr mühsam zerlegen lassen. Für Zahlen bis eine Billion ist das mit dem Rechner dagegen sofort möglich.
Zum Nachrechnen multiplizieren Sie die Faktoren der Zerlegung wieder zusammen. Das Ergebnis muss die Ausgangszahl sein. Auch die Teilerliste hilft bei der Probe: Jeder aufgeführte Teiler muss die Zahl ohne Rest teilen.
Rechenbeispiele Schritt für Schritt
Schulaufgabe: 84 in Primfaktoren zerlegen
Teilen Sie wiederholt durch die kleinste passende Primzahl: 84 ÷ 2 = 42, 42 ÷ 2 = 21, 21 ÷ 3 = 7, und 7 ist selbst prim.
| Zahl | 84 |
|---|---|
| Primfaktorzerlegung | 2² · 3 · 7 |
| Anzahl der Teiler | 12 |
| Alle Teiler | 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84 |
84 = 2² · 3 · 7. Die Teilerzahl ergibt sich aus (2 + 1) · (1 + 1) · (1 + 1) = 12.
Die Zahl 1001: drei Primfaktoren auf einmal
1001 sieht unauffällig aus, ist aber das Produkt der drei aufeinanderfolgenden Primzahlen 7, 11 und 13.
| Zahl | 1001 |
|---|---|
| Primfaktorzerlegung | 7 · 11 · 13 |
| Anzahl der Teiler | 8 |
| Summe der Teiler | 1.344 |
1001 = 7 · 11 · 13. Daraus folgt ein bekannter Trick: Jede dreistellige Zahl mal 1001 ergibt die Zahl zweimal hintereinander, etwa 123 · 1001 = 123123.
Jahreszahlen: 2026 und 2027
2026 ist gerade und damit durch 2 teilbar. Bleibt nach dem Teilen eine Zahl übrig, die durch keine Primzahl bis zu ihrer Wurzel teilbar ist, ist sie selbst prim.
| Zahl | 2026 |
|---|---|
| Primfaktorzerlegung | 2 · 1013 |
| Primzahl | Nein |
| Alle Teiler | 1, 2, 1013, 2026 |
2026 = 2 · 1013. Das Folgejahr 2027 ist dagegen eine Primzahl; der Rechner meldet dafür nur die Teiler 1 und 2027.
Zweierpotenz: 1024
1024 ist die Zahl, die in der Informatik für Kilo in Kibibyte steht.
| Zahl | 1024 |
|---|---|
| Primfaktorzerlegung | 2¹⁰ |
| Anzahl der Teiler | 11 |
| Summe der Teiler | 2.047 |
1024 = 2¹⁰, mit 11 Teilern. Die Teilersumme jeder Zweierpotenz ist um eins kleiner als die nächste Zweierpotenz: 2.047 = 2.048 − 1.
Vollkommene Zahl: 28
Eine Zahl heißt vollkommen, wenn die Summe ihrer echten Teiler die Zahl selbst ergibt. Die Summe aller Teiler ist dann genau das Doppelte.
| Zahl | 28 |
|---|---|
| Primfaktorzerlegung | 2² · 7 |
| Summe der Teiler | 56 |
| Alle Teiler | 1, 2, 4, 7, 14, 28 |
Die Teilersumme ist 56 = 2 · 28, ohne die 28 selbst bleiben 1 + 2 + 4 + 7 + 14 = 28. Nach 6 ist 28 die zweite vollkommene Zahl.
Sonderfälle und Grenzen
- Obergrenze: Der Rechner zerlegt ganze Zahlen von 2 bis 1.000.000.000.000. Größere Zahlen überschreiten die Genauigkeit, mit der der Browser ganze Zahlen sicher darstellt, und die Probedivision würde zu lange dauern.
- Negative Zahlen: Für negative Zahlen zerlegen Sie den Betrag und setzen den Faktor −1 davor, etwa −84 = −1 · 2² · 3 · 7. Der Rechner nimmt nur positive Zahlen an.
- Teilerliste: Die vollständige Liste aller Teiler erscheint nur bei bis zu 64 Teilern. Bei Zahlen mit sehr vielen Teilern, etwa 720.720, zeigt der Rechner nur Anzahl und Summe.
- Dezimalzahlen und Brüche: Nur ganze Zahlen haben eine Primfaktorzerlegung. Einen Bruch kürzen Sie, indem Sie Zähler und Nenner getrennt zerlegen und gemeinsame Faktoren streichen.
- Große Primfaktoren: Besteht eine Zahl nahe der Obergrenze aus zwei großen Primfaktoren, braucht die Probedivision am längsten, weil bis zur Wurzel geprüft werden muss. Das kann auf langsamen Geräten einen Moment dauern.
Mehr zum Thema Primzahlen und Teiler
Häufige Fragen
Wie bestimme ich mit der Primfaktorzerlegung den ggT und das kgV?
Zerlegen Sie beide Zahlen, zum Beispiel 84 = 2² · 3 · 7 und 90 = 2 · 3² · 5. Für den ggT nehmen Sie jeden gemeinsamen Primfaktor mit dem kleineren Exponenten: 2 · 3 = 6. Für das kgV nehmen Sie jeden vorkommenden Primfaktor mit dem größeren Exponenten: 2² · 3² · 5 · 7 = 1.260.
Wie erkenne ich schnell, ob eine Zahl durch 3, 9 oder 11 teilbar ist?
Durch 3 oder 9 ist eine Zahl teilbar, wenn ihre Quersumme durch 3 oder 9 teilbar ist; bei 2.025 ist die Quersumme 9. Für 11 bilden Sie die alternierende Quersumme von rechts: Bei 1.001 ist 1 − 0 + 0 − 1 = 0, also durch 11 teilbar. Durch 5 teilbar sind alle Zahlen mit Endziffer 0 oder 5.
Ist 0 oder 1 in Primfaktoren zerlegbar?
Nein. Die 1 hat keine Primfaktoren, man spricht vom leeren Produkt. Die 0 ist durch jede Zahl teilbar und lässt sich nicht eindeutig zerlegen. Der Hauptsatz der Arithmetik gilt deshalb nur für natürliche Zahlen ab 2, und der Rechner nimmt nur solche an.
Woran erkenne ich an der Zerlegung eine Quadratzahl?
Eine Zahl ist genau dann eine Quadratzahl, wenn alle Exponenten ihrer Primfaktorzerlegung gerade sind. 3.600 = 2⁴ · 3² · 5² ist ein Quadrat, nämlich 60². Ganz ähnlich ist eine Zahl eine Kubikzahl, wenn alle Exponenten durch 3 teilbar sind. Außerdem haben nur Quadratzahlen eine ungerade Anzahl von Teilern.
Warum ist die Zerlegung großer Zahlen für die Verschlüsselung wichtig?
Zwei große Primzahlen zu multiplizieren ist leicht, das Produkt wieder zu zerlegen dagegen extrem aufwendig. Auf diesem Ungleichgewicht beruht das RSA-Verfahren. Dort werden Zahlen mit Hunderten Dezimalstellen verwendet; für Signaturen empfehlen Normungsstellen derzeit Schlüssellängen von mindestens 2.048 Bit.
Quellen und Rechtsgrundlagen
- DLMF §27.2 Functions of Number Theory (Primzahlen, Teilerfunktionen) National Institute of Standards and Technology
- DLMF §27.3 Multiplicative Properties National Institute of Standards and Technology
- DLMF §27.19 Methods of Computation: Factorization National Institute of Standards and Technology
- FIPS 186-5 Digital Signature Standard (RSA-Schlüssellängen) National Institute of Standards and Technology
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.