In der Mathematik versteht man unter der Primfaktorzerlegung, auch als Zerlegung in Primfaktoren bezeichnet, die Darstellung einer natürlichen Zahl als Produkt von Primzahlen. Primfaktorzerlegungen für die Zahlen 30 und 6936 sind beispielsweise

$30\; =\; 2\; \backslash cdot\; 3\; \backslash cdot\; 5$

$6936\; =\; 2\; \backslash cdot\; 2\; \backslash cdot\; 2\; \backslash cdot\; 3\; \backslash cdot\; 17\; \backslash cdot\; 17$

Bei der kanonischen Primfaktorzerlegung sind die Primfaktoren nach ihrer Größe geordnet und zu Potenzen zusammengefasst. Die kanonische Darstellung von 6936 ist somit

$6936\; =\; 2^3\; \backslash cdot\; 3\; \backslash cdot\; 17^2$

Gemäß dem Fundamentalsatz der Arithmetik ist die kanonische Darstellung einer natürlichen Zahl eindeutig.

Die in der Primfaktorzerlegung einer Zahl auftretenden Primzahlen nennt man die Primfaktoren dieser Zahl. Zum Beispiel hat 6936 die Primfaktoren 2, 3 und 17. Den Exponenten des jeweiligen Primfaktors $p$ nennt man die p-Bewertung oder den $p$-Exponenten der Zahl. Unser Beispiel 6936 hat den 2-Exponenten 3, den 3-Exponenten 1 und den 17-Exponenten 2. Alle anderen p-Exponenten sind gleich 0.

Um die Primfaktorzerlegung einer Zahl zu berechnen stehen mehrere Faktorisierungsverfahren zur Verfügung. Diese berechnen nichttriviale Teiler ganzer Zahlen. Diese Aufgabenstellung ist als Faktorisierungsproblem für ganze Zahlen bekannt und kann mit den bekannten Methoden praktisch nicht effizient bezeichnet werden.

Eigenschaften

---

Die Primfaktorzerlegung der 1 besteht aus dem leeren Produkt (welches hier per Definition den Wert 1 hat) und die einer Primzahl $p$ besteht aus dem einzigen Faktor $p$. Eine natürliche Zahl größer als 1, die nicht selbst Primzahl ist, nennt man zusammengesetzt; ihre Primfaktorzerlegung besteht aus mehr als einem Faktor (möglicherweise auch mehrmals demselben).

Verallgemeinerung

---

In einem kommutativen unitären Ring kann man den Begriff des Primelements definieren und fragen, ob jedes Element eine Primfaktorzerlegung hat und ob diese eindeutig ist. Dabei stellt man fest, dass dies nicht immer so ist, z. B. hat die Zahl 4 im Ring $\backslash mathbb\{Z\}*$ keine Primfaktorzerlegung.

Falls jedoch eine Primfaktorzerlegung existiert, dann ist diese (bis auf Reihenfolge und Einheiten) eindeutig.

In einem faktoriellen Ring existiert stets eine Primfaktorzerlegung.

Weblinks

---

• Primfaktorenzerlegung online
• RSA Factoring Challenge

Zahlentheorie

مشكلة التفكيك إلى جداء عوامل أولية | Prime factor | Þáttun | Fattorizzazione | 素因数分解 | Priemfactor | Faktoryzacja | Факторизация | Faktorisering