Zahlentheorie/Primfaktorzerlegung/Existenz/Fakt/Beweis2
Wir beweisen die Existenz durch Induktion über , und zwar betrachten wir die Aussage , die besagt, dass jede natürliche Zahl mit eine Primfaktorzerlegung besitzt. Für liegt eine Primzahl vor. Sei und sei, als Induktionsvoraussetzung, angenommen, dass jede Zahl eine Primfaktorzerlegung besitzt. Es ist zu zeigen, dass dann auch jede Zahl eine Primfaktorzerlegung besitzt. Die einzig neue zu betrachtende Zahl ist . Es ist also zu zeigen, dass wenn jede Zahl echt kleiner als eine Primfaktorzerlegung besitzt, dass dann auch eine Primfaktorzerlegung besitzt.
Wir betrachten also . Im Beweis dieses Induktionsschrittes kommt ein weiteres wichtiges Argumentationsschema zum Tragen, nämlich Beweis durch Fallunterscheidung. Dabei argumentiert man abhängig davon, ob eine zusätzliche Eigenschaft vorliegt oder nicht, in beiden Fällen muss man jeweils das nachweisen, was man zeigen will.
Hier macht man die Fallunterscheidung, ob eine Primzahl ist oder nicht. Wenn eine Primzahl ist, so liegt unmittelbar die Primfaktorzerlegung vor, die aus der Zahl selbst besteht. In diesem Fall wird also auf die Induktionsvoraussetzung gar nicht Bezug genommen.
Somit betrachten wir den Fall, wo keine Primzahl ist. Dies bedeutet, dass es eine nichttriviale Zerlegung mit kleineren Zahlen gibt. Für diese Zahlen und gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für zusammen.
