Primfaktorzerlegung-Rechner

Zahlen in Primfaktoren zerlegen und Primzahlen erkennen

Jede ganze Zahl ab 2 lässt sich, abgesehen von der Reihenfolge der Faktoren, auf genau eine Weise als Produkt von Primzahlen schreiben: Das ist der Fundamentalsatz der Arithmetik. 360 = 2³ × 3² × 5, 1.001 = 7 × 11 × 13, und 97 lässt sich gar nicht zerlegen: Sie ist eine Primzahl. Dieser Rechner liefert die Primfaktorzerlegung, sagt sofort, ob die Zahl prim oder zusammengesetzt ist, und zeigt die fortgesetzte Division so, wie sie im Unterricht aufgeschrieben wird.

Die Zerlegung ist der Schlüssel zu vielen Rechnungen: Brüche kürzen, ggT und kgV bestimmen, Teiler zählen, Wurzeln vereinfachen. Sie hilft Schülerinnen und Schülern der Unter- und Mittelstufe, Lehrkräften bei der Vorbereitung von Arbeitsblättern, Teilnehmenden an Mathematik-Olympiaden und allen, die sich für Kryptografie interessieren: Die Sicherheit von RSA beruht darauf, dass sehr große Zahlen schwer zu faktorisieren sind.

1. Zahl eingeben

   Tippen Sie eine ganze Zahl in „Ganze Zahl zum Zerlegen“ (ab 2, bis zu 18 Ziffern). Leerzeichen und Tausendertrennzeichen werden ignoriert, 600.851.475.143 funktioniert also direkt. Die Schaltflächen neben „Beispiele:“ laden fertige Beispiele.

2. Ergebnis ablesen

   Oben steht „Primzahl“ oder „Keine Primzahl: zusammengesetzte Zahl“, darunter erscheint die Zerlegung mit Exponenten (360 = 2³ × 3² × 5) und ausgeschrieben. „Kopieren“ legt 2^3 × 3^2 × 5 in die Zwischenablage.

3. Eigenschaften erkunden

   Die Karten unter „Zahlentheoretische Eigenschaften“ zeigen τ(n), σ(n), φ(n), die Anzahl verschiedener Primfaktoren ω(n) und der Primfaktoren mit Vielfachheit Ω(n), ob n eine Quadratzahl ist, die Summe der echten Teiler sowie die vorherige und nächste Primzahl (bis 10¹²).

4. Von Hand nachprüfen

   Die Tabelle „Fortgesetzte Division (Divisionsleiter)“ wiederholt jeden Schritt (360 ÷ 2 = 180…) bis zum Quotienten 1, und „Alle Teiler“ listet die Teiler aufsteigend auf, die Primteiler hervorgehoben.

Das Verfahren: Fundamentalsatz und Formeln

Für eine ganze Zahl n ≥ 2 lautet die Zerlegung n = p1a1 × p2a2 × … × pkak. Man erhält sie, indem man so lange wie möglich durch den kleinsten Primfaktor teilt; Teiler muss man nur bis √n prüfen, denn eine zusammengesetzte Zahl hat immer einen Primfaktor, der höchstens so groß wie ihre Wurzel ist.

Bei großen Zahlen kombiniert das Tool drei Stufen: Probedivision durch die Primzahlen bis 10.000, einen deterministischen Miller-Rabin-Test zum Erkennen von Primzahlen und Pollards Rho-Methode (Brent-Variante), um zusammengesetzte Restfaktoren aufzuspalten. Gerechnet wird durchgehend mit exakten ganzen Zahlen, ohne Rundung.

• p₁ < p₂ < … < p_k: die verschiedenen Primfaktoren in aufsteigender Reihenfolge; ihre Anzahl heißt ω(n).
• a_i: der Exponent (die Vielfachheit) von p_i; die Summe a₁ + … + a_k ist Ω(n), die Anzahl der Primfaktoren mit Wiederholung.
• τ(n) = (a₁ + 1)(a₂ + 1)…(a_k + 1): die Anzahl der Teiler, weil jeder Teiler für jedes p_i einen Exponenten zwischen 0 und a_i wählt.
• σ(n) = ∏ (p_i^a_i+1 − 1) / (p_i − 1): die Summe aller Teiler; s(n) = σ(n) − n zeigt, ob die Zahl vollkommen, abundant oder defizient ist.
• φ(n) = n × ∏ (1 − 1/p_i): die Eulersche Phi-Funktion, also die Anzahl der zu n teilerfremden Zahlen von 1 bis n.
• Quadratzahl: n ist genau dann ein Quadrat, wenn alle a_i gerade sind; dann gilt √n = ∏ p_i^a_i/2, zum Beispiel √1.024 = 2⁵ = 32.

Beispiele zur Primfaktorzerlegung

Wofür braucht man die Primfaktorzerlegung?

• Brüche kürzen: 84/360 = (2² × 3 × 7)/(2³ × 3² × 5) = 7/30, nachdem die gemeinsamen Faktoren 2² × 3 = 12 gestrichen sind.
• Hauptnenner finden: Das kgV von 360 und 84 ist 2.520, der kleinste gemeinsame Nenner, um 1/360 und 1/84 zu addieren.
• Wurzeln vereinfachen (teilweise Wurzelziehen): √360 = √(2² × 3² × 10) = 2 × 3 × √10 = 6√10, denn jedes Paar gleicher Faktoren lässt sich aus der Wurzel ziehen.
• Teiler zählen und auflisten: nützlich bei Aufteilungsaufgaben (360 Stühle in gleich lange Reihen stellen: 24 mögliche Anordnungen Reihen × Spalten) und bei Hausaufgaben zur Teilbarkeit.
• Kryptografie und Knobelaufgaben: RSA beruht auf der Schwierigkeit des Faktorisierens; das berühmte Problem 3 von Project Euler fragt nach dem größten Primfaktor von 600.851.475.143, nämlich 6.857.

Häufige Fehler

• Durch eine Nicht-Primzahl teilen: 360 durch 4 oder 6 zu teilen ergibt zwar einen richtigen Quotienten, aber eine unvollständige Zerlegung; geteilt wird nur durch 2, 3, 5, 7, 11, 13…
• 1 für eine Primzahl halten: Die 1 hat nur einen Teiler und kommt in keiner Zerlegung vor.
• 2³ mit 2 × 3 verwechseln: 2³ = 2 × 2 × 2 = 8, dagegen 2 × 3 = 6; der Exponent zählt, wie oft der Faktor vorkommt.
• Einer Zahl „ansehen“, dass sie prim ist: 51 = 3 × 17, 91 = 7 × 13 und 1.001 = 7 × 11 × 13 sind zusammengesetzt; prüfen Sie immer bis zur Wurzel.

Alle Berechnungen laufen lokal in Ihrem Browser mit exakter Ganzzahlarithmetik (BigInt): Keine Zahl wird gesendet oder gespeichert. Grenzen: höchstens 18 Ziffern; benachbarte Primzahlen werden bis 10¹² angezeigt, die Teilerliste bis 1.000 Teiler und die Tabelle der fortgesetzten Division bis 40 Primfaktoren (mit Vielfachheit gezählt).