Primfaktorzerlegung

Einführung

Die Primfaktorzerlegung ist die Darstellung einer natürlichen Zahl [math]\displaystyle{ n }[/math] als Produkt aus Primzahlen, die dann als Primfaktoren von [math]\displaystyle{ n }[/math] bezeichnet werden. Diese Darstellung ist (bis auf die Reihenfolge der Faktoren) eindeutig und zählt zu den grundlegenden und klassischen Werkzeugen der Zahlentheorie.

Primzahl

Eine Primzahl ist eine natürliche Zahl größer als 1, die ausschließlich durch 1 und durch sich selbst ohne Rest teilbar ist. Die Primzahlen bis 20 lauten:

2, 3, 5, 7, 11, 13, 17, 19

Teilbarkeitsregeln

Im Rahmen einer Primfaktorzerlegung ist es notwendig herauszufinden, ob eine zu zerlegende Zahl durch eine bestimmte Primzahl teilbar ist. Hierfür existieren hilfreiche Teilbarkeitsregeln. Eine ganze Zahl ist teilbar durch:

• 2, wenn ihre letzte Ziffer durch 2 teilbar ist (sie also auf 0, 2, 4, 6 oder 8 endet).
• 3, wenn ihre Quersumme durch 3 teilbar ist.
• 5, wenn ihre letzte Ziffer durch 5 teilbar ist (sie also auf 0 oder 5 endet).

Es ist relativ einfach und schnell zu erkennen, ob eine Zahl durch 2, 3 oder 5 teilbar ist. Wenn allerdings größere Primzahlen im Spiel sind, ist eine schriftliche Division oder der Einsatz eines Taschenrechners zur Überprüfung der Teilbarkeit meist unumgänglich.

Vorgehensweise

Das systematische Vorgehen bei der Primfaktorzerlegung lässt sich in folgenden Schritten beschreiben:

1. Suche nach einem Primfaktor (einer Primzahl, welche die Ausgangszahl ohne Rest teilt). Man beginnt hierbei idealerweise bei der kleinsten Primzahl, der 2, und prüft die nächstgrößeren Primzahlen aufsteigend.
2. Division der Zahl durch diesen gefundenen Primfaktor.
3. Suche nach einem neuen Primfaktor für den berechneten Quotienten (die geteilte Zahl).
4. Erneute Division durch den gefundenen Primfaktor.

Dieser Prozess wird so lange wiederholt, bis der verbleibende Quotient selbst eine Primzahl ist. Die Primfaktorzerlegung ergibt sich am Ende aus dem Produkt aller gefundenen Primfaktoren.

Beispiel: Primfaktorzerlegung der Zahl 12

Gesucht ist die Primfaktorzerlegung der Zahl 12. Wir gehen systematisch vor:

Primfaktor suchen Wir beginnen die Suche nach einem geeigneten Teiler bei der kleinsten Primzahl, der 2. Wir prüfen: Ist 12 durch 2 teilbar?

• Antwort: Ja.
• Begründung: Gemäß den Teilbarkeitsregeln ist eine ganze Zahl durch 2 teilbar, wenn ihre letzte Ziffer durch 2 teilbar ist (hier die 2).

Zahl durch gefundenen Primfaktor teilen Wir führen die Division durch: [math]\displaystyle{ 12 : 2 = 6 }[/math]

Den ersten Primfaktor (die 2) haben wir somit gefunden. Da das Ergebnis 6 jedoch noch keine Primzahl ist, ist die Zerlegung noch nicht abgeschlossen.

Erneut Primfaktor suchen Für die Zahl 6 beginnen wir die Suche nach einem Primfaktor wieder bei der kleinsten Primzahl, der 2. Wir prüfen: Ist 6 durch 2 teilbar?

• Antwort: Ja.

Zahl erneut teilen Wir führen die nächste Division durch: [math]\displaystyle{ 6 : 2 = 3 }[/math]

Da es sich bei dem Ergebnis 3 um eine Primzahl handelt, ist die schrittweise Zerlegung nun erfolgreich abgeschlossen.

Ergebnis Die Primfaktorzerlegung bildet sich aus dem Produkt aller identifizierten Primfaktoren: [math]\displaystyle{ 12 = 2 \cdot 2 \cdot 3 }[/math]