Also, Primzahlen sind ja alle Zahlen, die nur durch eins und sich selbst teilbar sind - mit anderen Worten: alle ganzen Zahlen mit genau zwei Teilern.
Das heißt, jede zusammengesetzte Zahl z besitzt mindestens einen Teiler, der nicht 1 oder z ist.
Nun ist relativ einfach zu beweisen, dass man jede Zahl eindeutig als Produkt von Primzahlen schreiben kann:
Nehmen wir an, es wäre nicht so, also es gäbe zusammengesetzte Zahlen, die sich nicht in Primfaktoren zerlegen lassen. Dann müsste es davon eine kleinste geben, nennen wir sie z.
Da z keine Primzahl ist, besitzt z einen Teiler, mit anderen Worten, es gibt eine kleinere Zahl t, mit der Eigenschaft, dass
t*n = z
für irgendeine ganze Zahl n zwischen 1 und z.
Da nun aber t und n beide kleiner sind als z, besitzen sie jeweils eine Primfaktorzerlegung, ihr Produkt besitzt als Primfaktorzerlegung also das Produkt der beiden einzelnen Primfaktorzerlegungen.
Nach Voraussetzung soll z aber nicht in Primfaktoren zerlegbar sein: das ist ein Widerspruch, also kann es eine solche Zahl nicht geben.
⇒ Jede zusammengesetzte Zahl (ganz gleich, wie groß sie auch sein mag) lässt sich in Primfaktoren zerlegen.
