Mathematik
Primfaktorzerlegung mit Rechenweg
Gib eine ganze Zahl ein: Du erhältst ihre Primfaktorzerlegung mit Potenzen, die Divisionsleiter wie im Heft, die Liste der Teiler und die Antwort, ob die Zahl eine Primzahl ist.
Wie man eine Zahl in Primfaktoren zerlegt
Jede ganze Zahl größer als 1 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben: der Fundamentalsatz der Arithmetik. Man findet sie, indem man so oft wie möglich durch die kleinste Primzahl 2 teilt, dann durch 3, durch 5 und so weiter, und die Quotienten untereinander schreibt. Für 360: 360 : 2 = 180, : 2 = 90, : 2 = 45, : 3 = 15, : 3 = 5, : 5 = 1, also 360 = 2³ · 3² · 5.
Aus der Zerlegung folgt fast alles Weitere. Die Anzahl der Teiler ist das Produkt der um eins erhöhten Exponenten: bei 360 sind es 4 · 3 · 2 = 24. ggT und kgV zweier Zahlen ergeben sich aus dem Vergleich der Zerlegungen, und eine Zahl ist eine Quadratzahl, wenn alle Exponenten gerade sind.
Bei großen Zahlen wird das Probedividieren hoffnungslos langsam: 30 Stellen bräuchten Milliarden Versuche. Dieser Rechner erkennt Primzahlen mit dem Miller-Rabin-Test und spaltet zusammengesetzte Zahlen mit Pollards Rho-Methode, den Werkzeugen der Kryptografie.
Häufige Fehler
- 1 als Primzahl zählen: Eine Primzahl hat per Definition genau zwei Teiler, 1 hat nur einen.
- Bei einem Faktor aufhören, der keine Primzahl ist, wie bei 360 = 4 · 90: Die Zerlegung ist erst fertig, wenn alle Faktoren prim sind.
- Teiler über die Wurzel hinaus prüfen: Hat n bis √n keinen Teiler, ist n eine Primzahl.
Häufige Fragen
Wie erkenne ich, ob eine Zahl eine Primzahl ist?
Man prüft, ob eine Primzahl bis zu ihrer Quadratwurzel sie teilt. Bei 97, Wurzel etwa 9,8, genügen 2, 3, 5 und 7: keine teilt sie, also ist 97 eine Primzahl.
Wozu braucht man die Primfaktorzerlegung?
Für ggT und kgV, zum Kürzen von Brüchen und Wurzeln und zum Zählen von Teilern. In der Kryptografie beruht die Sicherheit von RSA gerade darauf, wie schwer es ist, riesige Zahlen zu zerlegen.
Was ist die Eulersche Phi-Funktion?
φ(n) zählt die Zahlen von 1 bis n, die mit n keinen gemeinsamen Faktor haben. Für eine Primzahl p ist sie p − 1, für 360 ist sie 96.
So funktioniert diese Berechnung
n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ. Anzahl der Teiler = (a₁ + 1)(a₂ + 1)…(aₖ + 1). Teilersumme = Π (pᵢ^(aᵢ+1) − 1) / (pᵢ − 1). Phi-Funktion φ(n) = Π pᵢ^(aᵢ−1)(pᵢ − 1). Verfahren: Probedivision durch die Primzahlen unter 1000, deterministischer Miller-Rabin-Test und Pollards Rho-Faktorisierung in der Variante von Brent.
Verwandte Rechner
Polynome faktorisieren
Ausklammern, Polynomdivision, binomische Formeln und quadratische Terme: ein Polynom Schritt für Schritt zerlegen.
Horner-Schema
Dividiert ein Polynom durch (x − a) und faktorisiert es.
ggT und kgV
Größter gemeinsamer Teiler und kleinstes gemeinsames Vielfaches mit Primfaktorzerlegung.
Periodische Dezimalzahl in Bruch
Von der periodischen Dezimalzahl zum Bruch und vom Bruch zur Dezimalzahl, mit Periode und erklärter Regel.