Primfaktorzerlegung

Primfaktorzerlegung: der Fingerabdruck, den jede Zahl genau einmal hat

Jede ganze Zahl über 1 ist ein Produkt von Primzahlen — und, das macht sie nützlich, nur auf eine einzige Weise. Der Fundamentalsatz der Arithmetik garantiert die Eindeutigkeit, weshalb die Zerlegung als Fingerabdruck taugt und weshalb so vieles darauf aufbaut, vom Kürzen von Brüchen bis zur Public-Key-Kryptografie.

So wird gerechnet

• Zerlegt eine Zahl in ihre Primfaktoren, in Potenzschreibweise und vollständig ausgeschrieben.
• Zählt die Teiler, ohne sie aufzulisten, direkt aus den Exponenten.
• Sagt, ob die Zahl prim ist — das ist schlicht der Fall, in dem sie sich in sich selbst zerlegt.

every integer above 1 factorises into primes in exactly one way

  360 = 2 x 2 x 2 x 3 x 3 x 5
      = 2^3 x 3^2 x 5

the number of divisors follows from the exponents
  d(n) = (3 + 1) x (2 + 1) x (1 + 1) = 24

Rechenbeispiel

360 zerlegen, indem wiederholt die kleinste passende Primzahl herausdividiert wird.

1. 360 / 2 = 180
2. 180 / 2 = 90
3. 90 / 2 = 45 2 appears three times
4. 45 / 3 = 15
5. 15 / 3 = 5 3 appears twice
6. 5 / 5 = 1 5 appears once
7. result 2^3 x 3^2 x 5

360 = 2³ × 3² × 5, und keine andere Primzahlkombination ergibt 360. Allein aus den Exponenten folgt die Teileranzahl: (3+1)(2+1)(1+1) = 24, denn jeder Teiler wählt 0 bis 3 Zweien, 0 bis 2 Dreien und 0 oder 1 Fünf.

Das Ergebnis lesen

• Die Teilerformel lohnt für sich. Man muss Teiler nie auflisten, um sie zu zählen — je Exponent eins addieren und multiplizieren, denn einen Teiler zu bilden heißt, unabhängig zu wählen, wie viele jeder Primzahl hineinkommen.
• Probedivision muss nur bis zur Quadratwurzel prüfen. Hat n einen Faktor über √n, gibt es zwangsläufig den passenden darunter — jenseits der Wurzel bleibt nichts zu finden. Deshalb ist die Zerlegung einer sechsstelligen Zahl sofort da.
• Nach 2 und 3 geht das Werkzeug in Sechserschritten und prüft nur 6k−1 und 6k+1. Alle übrigen Reste sind bereits durch 2 oder 3 teilbar, was zwei Drittel der Kandidaten gratis überspringt.
• Dass die Zerlegung sehr großer Zahlen schwer ist, ist ein Merkmal und keine Grenze dieses Werkzeugs. RSA beruht darauf, dass das Multiplizieren zweier großer Primzahlen leicht ist und ihre Rückgewinnung nicht — diese Asymmetrie ist das gesamte Sicherheitsargument.

Häufige Fragen

Ist 1 eine Primzahl?

Nein, und der Ausschluss ist eine bewusste Entscheidung, kein Versehen. Zählte 1 als prim, wären Zerlegungen nicht mehr eindeutig — 6 wäre 2×3 oder 1×2×3 oder 1×1×2×3 — und der Satz, der die Zerlegung nützlich macht, bräuchte in jeder Formulierung eine unschöne Ausnahme.

Warum zerlegt sich meine Zahl nur in sich selbst?

Weil sie prim ist. Eine Primzahl hat außer 1 und sich selbst keine Teiler, ihre Zerlegung ist also ein einzelner Term mit Exponent eins. Das Werkzeug sagt es ausdrücklich, statt es aus einer Ein-Element-Liste erschließen zu lassen.