Eine beliebige (ganze, positive) Zahl ist entweder prim wenn sie nur durch 1 und (verschieden) durch sich selbst teilbar ist, oder zusammengesetzt, wenn man sie noch durch andere Zahlen teilen kann. So sind etwa die Zahlen 3 und 5 prim, da man sie nur durch 1 und sich selbst teilen kann. Setzt man diese Zahlen zusammen (multipliziert man sie), so erhält man die Zahl \(3\cdot5=15\) - die 15 ist also eine zusammengesetzte Zahl.
Interessant an diesem Satz ist die Eindeutigkeit der Produkte. Betrachten wir dazu erneut die Zahl 15, sie ist das Produkt aus 3 und 5. Der Satz besagt nun, wenn \(15=3\cdot5\), dann läßt sich die 15 nicht durch Produkte anderer Primzahlen darstellen - etwa ist \(15\ne2\cdot7\). Man nennt die Zahlen 3 und 5 Primfaktoren der Zahl 15.
Um eine zusammengesetzte Zahl in ihre Primfaktoren zu zerlegen, geht man so ähnlich vor, wie bei der Primzahl-Überprüfung. Man testet also, welche Primzahlen Teiler der vorliegenden Zahl sind. Hat man einen Primfaktor gefunden, so kann man diesen per Division sozusagen aus der Zahl herausziehen (findet man etwa bei der Zahl 20 den Primfaktor 2, so kann diese aus der 20 durch Division herausgenommen werden: \(20\div2=10\)). Mit dem erhaltenen Rest (hier 10) verfährt man wieder genauso wie mit der Ausgangszahl, so lange, bis der Rest selbst eine Primzahl ist (die 10 hat wieder den Primfaktor 2, also erneut \(10\div2=5\). Die 5 ist prim, wir haben also alle Primfaktoren gefunden: \(20=2\cdot2\cdot5\)).
Ermittelt man auf diese Weise die Primfaktorzerlegung einer Zahl, so muss man oft recht umständlich und viel rechnen.
Meist allerdings (mit etwas Übung) sieht man sofort einen Teiler, so dass man schneller zur Primfaktorzerlegung kommt, wenn man diesen sofort herauszieht (etwa sieht man bei der zusammengesetzten Zahl 125 sofort den Primfaktor 5, welchen man auch sofort herausziehen kann). Wichtig bei dieser Vorgehensweise ist, dass man jeden gefundenen Faktor stets bis zum Schluss weiter zerlegen muss!