Primfaktorzerlegung

In der Mathematik versteht man unter der Primfaktorzerlegung, auch als Zerlegung in Primfaktoren bezeichnet, die Darstellung einer natürlichen Zahl als Produkt von Primzahlen.

Beispiel:

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.

Beispiel:

Dass die Primfaktorzerlegung natürlicher Zahlen bis auf die Reihenfolge der Faktoren eindeutig ist, ist Aussage des Fundamentalsatzes der Arithmetik.

Es gibt Faktorisierungsverfahren, die eine Zahl in ihre Primfaktoren zerlegen.

Inhaltsverzeichnis

Kanonische Darstellung

Bei der kanonischen Darstellung einer Primfaktorzerlegung sind die Primfaktoren nach ihrer Größe geordnet und zu Potenzen zusammengefasst.

Beispiel:

\frac{1200}{6936} =   \frac{2 \cdot 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 5}{2 \cdot 2 \cdot 2 \cdot 3 \cdot 17 \cdot 17} =   \frac{2 \cdot 5^2}{17^2} =   2 \cdot 5^2 \cdot 17^{-2}

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).

Die Schwierigkeiten zur Zerlegung einer Zahl in ihre Primfaktoren werden als Faktorisierungsprobleme bezeichnet. Verschlüsselungsverfahren wie das RSA-Kryptosystem basieren auf der Annahme, dass die Primfaktorzerlegung von sehr großen Zahlen mit den heutigen Methodiken praktisch nicht durchführbar ist.

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 \mathbb{Z}[\sqrt{-3}] 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


Kategorie:Zahlentheorie

See also: Primfaktorzerlegung, Bewertungstheorie, Einheit (Mathematik), Faktorieller Ring, Faktorisierungsproblem, Faktorisierungsverfahren, Fundamentalsatz der Arithmetik, Mathematik, Natürliche Zahl, Primelement