Primfaktorzerlegung

So funktioniert die fortgesetzte Division

Teile die Zahl durch die kleinste Primzahl, durch die sie ohne Rest teilbar ist (2, dann 3, 5, 7, 11…), und wiederhole das mit dem Quotienten, bis du bei 1 ankommst. Die dabei verwendeten Teiler sind die Primfaktoren. Nimm zum Beispiel 360: dreimal durch 2 teilen (360 → 180 → 90 → 45), zweimal durch 3 (45 → 15 → 5) und einmal durch 5, also 360 = 2³ × 3² × 5.

Wofür man die Primfaktorzerlegung braucht

Die Zerlegung ist die Grundlage, um ggT und kgV zu bestimmen: Der größte gemeinsame Teiler ergibt sich aus dem Produkt der gemeinsamen Primfaktoren mit dem kleinsten Exponenten, während das kleinste gemeinsame Vielfache die gemeinsamen und nicht gemeinsamen Faktoren mit dem größten Exponenten nimmt. So kürzt man auch Brüche vollständig und zählt die Teiler einer Zahl (zu jedem Exponenten 1 addieren und multiplizieren). Übrigens: Gerade weil es so schwierig ist, riesige Zahlen zu zerlegen, ist die RSA-Verschlüsselung sicher, die Banken und Websites verwenden.

Warum jede Zahl nur eine einzige Zerlegung hat

Das besagt der Fundamentalsatz der Arithmetik: Jede ganze Zahl größer als 1 lässt sich auf genau eine Weise als Produkt von Primzahlen schreiben, abgesehen von der Reihenfolge. Das ist nicht selbstverständlich und muss bewiesen werden, aber deshalb funktioniert die Zerlegung wie ein Personalausweis der Zahl.

Der praktische Nutzen folgt daraus: Zwei Zahlen vergleicht man, indem man ihre Faktoren statt ihrer Werte betrachtet. Der größte gemeinsame Teiler nimmt die gemeinsamen Faktoren mit dem kleinsten Exponenten, das kleinste gemeinsame Vielfache alle Faktoren mit dem größten Exponenten, und keine der beiden Rechnungen verlangt, Teiler einzeln auszuprobieren.

Bei der Quadratwurzel ist Schluss

Um zu wissen, ob eine Zahl eine Primzahl ist, musst du nicht jeden Teiler bis zu ihr ausprobieren: Es genügt, bis zu ihrer Quadratwurzel zu gehen. Hat eine Zahl einen Teiler, der größer als die Wurzel ist, hat sie zwangsläufig auch einen kleineren, und auf den triffst du zuerst.

Deshalb braucht der Nachweis, dass 9.973 eine Primzahl ist, weniger als fünfundzwanzig Versuche und nicht zehntausend: Du probierst nur die Primzahlen bis 99. Bei der Zerlegung sagt dasselbe Prinzip, wann man aufhören kann: Ist der verbleibende Quotient kleiner als das Quadrat des aktuellen Teilers, ist dieser Quotient eine Primzahl.

Die Zahl, die sich leicht multiplizieren und schwer zerlegen lässt

Zwei große Primzahlen zu multiplizieren geht sofort; die beiden Faktoren aus dem Produkt zurückzugewinnen ist extrem schwierig, und niemand weiß, wie das bei Zahlen mit Hunderten von Stellen schnell geht. Die RSA-Kryptografie und damit ein großer Teil der Sicherheit im Internet beruht auf dieser Asymmetrie.

Bei kleinen Zahlen ist die Zerlegung dagegen sofort erledigt und im Alltag nützlich: einen Bruch kürzen, einen gemeinsamen Nenner finden, sehen, ob sich teilweise die Wurzel ziehen lässt. Es ist dasselbe Werkzeug in zwei völlig verschiedenen Größenordnungen.

Siehe auch

Für den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache gibt es den ggT- und kgV-Rechner, zum Kürzen eines Bruchs das Tool Brüche kürzen. Ist die Zahl groß, hilft dir die Seite Primzahlen.