Jede natürliche Zahl ist eine Primzahl oder kann als ein Produkt aus Primzahlen formuliert werden. Die “Zerlegung” einer Zahl in ein Produkt aus einer Abfolge von Primzahlen wird als Primfaktorzerlegung bezeichnet. Gemäß der mathematischen Definition ist die Primfaktorzerlegung die Darstellung einer natürlichen Zahl n als Produkt von Primzahlen. Die Primzahlen, die bei der Primfaktorzerlegung ermittelt werden, werden als Primfaktoren bezeichnet.
Wie eingangs erwähnt, wird bei der Primfaktorzerlegung eine natürliche Zahl in ein Produkt von Primzahlen zerlegt. Diese Primzahlen bzw. Primfaktoren sind eine natürliche Zahl, die nur durch sich selbst und durch 1 teilbar ist. Wie im Kapitel “Primzahlen” dargestellt, kann jede natürliche Zahl (n ≥ 2) in ein Produkt von Primzahlen zerlegen werden. Bei der Primfaktorzerlegung gibt es keine “festen” Rechenvorschriften, die Primfaktorzerlegung beruht im Wesentlich auf der Teilbarkeit von Zahlen
Bei der Primfaktorzerlegung wird mit Hilfe der Teilbarkeitsregeln untersucht, ob eine Zahl durch eine Primzahl teilbar ist. Auch, wenn es inzwischen eine Vielzahl an Möglichkeiten gibt, beginnt man in der Regel mit der kleinsten Primzahl (also der Zahl 2). Damit spart man sich den ersten Schritt (Primzahl suchen, durch die die Zahl teilbar ist). Kann die Zahl durch die Primzahl (in unserem Fall 2) geteilt werden, haben wir die erste Zerlegung erreicht. Die Zahl wird durch die Primzahl / Primfaktor geteilt. Das Ergebnis der so erhalten Zahl wird wieder auf die Teilbarkeit durch eine Primzahl geprüft.
Nachfolgend zwei Beispiele:
Beispiel 1: Primfaktorzerlegung der Zahl 18
Nun prüfen wir, ob die Ergebnis eine Primzahl ist. Die Zahl 3 ist eine Primzahl. Daher sind wir fertig mit der Primfaktorzerlegung der Zahl 18 und erhalten
18 = 2 · 3· 3
Beispiel 2: Primfaktorzerlegung der Zahl 25
Nun prüfen wir, ob die Ergebnis eine Primzahl ist. Die Zahl 5 ist eine Primzahl. Daher sind wir fertig mit der Primfaktorzerlegung der Zahl 25 und erhalten
25 = 5 · 5
In den zwei Beispielen haben wir gesehen, dass es kein allgemeines Schema für die Primfaktorzerlegung gibt. Im Wesentlichen beschränkt sich die Primfaktorzerlegung auf die Prüfung der Teilbarkeit einer Zahl und aus diesen “Teilbarkeiten” wird ein Produkt aus den einzelnen “Teilbarkeiten” errechnet.