Primfaktorzerlegung

Nimm die 60 und brich sie auseinander: 60 = 6 · 10. Die 6 zerfällt weiter in 2 · 3, die 10 in 2 · 5. Übrig bleibt 60 = 2 · 2 · 3 · 5, ein Produkt aus lauter Primzahlen, und keine davon lässt sich weiter zerlegen. Eine Primzahl ist eine Zahl mit genau zwei Teilern, der 1 und sich selbst, also 2, 3, 5, 7, 11 und so weiter. Das funktioniert mit jeder Zahl ab 2: Primzahlen sind die Atome der Zahlenwelt, und die Primfaktorzerlegung zeigt dir, aus welchen Atomen eine Zahl gebaut ist.

Der Faktorbaum

Der schnellste Weg zur Zerlegung ist ein Faktorbaum. Schreibe die Zahl oben hin und teile sie in zwei Faktoren, ganz egal welche. Ist ein Faktor noch keine Primzahl, bekommt er selbst zwei Äste, und so wächst der Baum nach unten weiter. Sobald an allen Enden Primzahlen stehen, bist du fertig: Die Blätter sind die Zerlegung. Das Schöne daran: Startest du bei 60 mit 6 · 10 oder mit 4 · 15, landest du in beiden Fällen bei denselben Blättern 2, 2, 3 und 5. Wer lieber ohne Baum arbeitet, teilt einfach immer wieder durch die kleinste Primzahl, die passt: 60 : 2 = 30, 30 : 2 = 15, 15 : 3 = 5, und die 5 ist selbst schon prim. Geteilt hast du dabei durch 2, 2 und 3, zusammen mit der übrig gebliebenen 5 ergibt das 60 = 2 · 2 · 3 · 5.

Eindeutig wie ein Fingerabdruck

Dass am Ende immer dieselben Primzahlen herauskommen, ist kein Zufall, sondern ein berühmter Satz: der Fundamentalsatz der Arithmetik. Er besagt, dass jede Zahl größer als 1 genau eine Primfaktorzerlegung besitzt, wenn man die Reihenfolge der Faktoren nicht mitzählt. 12 ist 2 · 2 · 3 und nichts anderes, so wie Wasser immer aus zwei Wasserstoffatomen und einem Sauerstoffatom besteht. Genau deshalb zählt die 1 übrigens nicht als Primzahl: Dürfte sie mitspielen, wäre 12 auch 1 · 2 · 2 · 3 oder 1 · 1 · 2 · 2 · 3, und die schöne Eindeutigkeit wäre dahin. Kommt ein Faktor mehrfach vor, schreibt man das kurz mit Potenzen: 24 = $2^3 \cdot 3$.

Und wozu das Ganze? Die Zerlegung macht den größten gemeinsamen Teiler (ggT) und das kleinste gemeinsame Vielfache (kgV) zum Ablesespiel. Nimm 24 = 2 · 2 · 2 · 3 und 36 = 2 · 2 · 3 · 3. Für den ggT sammelst du, was beide gemeinsam haben: 2 · 2 · 3 = 12. Für das kgV nimmst du jede Primzahl so oft, wie sie in der Zerlegung vorkommt, die mehr davon enthält, die 2 also dreimal und die 3 zweimal: 2 · 2 · 2 · 3 · 3 = 72. Kein Probieren, kein Raten. Und noch ein Ausblick: Bei riesigen Zahlen mit Hunderten von Stellen ist die Zerlegung selbst für Computer praktisch unmöglich, und genau diese Schwierigkeit schützt als Grundlage moderner Verschlüsselung jeden Tag deine Nachrichten.