Zahlentheorie/Primfaktorzerlegung/Fakt/Beweis

Beweis

Wir beweisen die Existenz und die Eindeutigkeit jeweils durch Induktion.  Für ${}n=2$ liegt eine Primzahl vor. Bei ${}n\geq 3$ ist entweder ${}n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ${}n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung ${}n=ab$ mit kleineren Zahlen ${}a,b<n$. Für diese Zahlen gibt es nach der Induktionsvoraussetzung eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für ${}n$ zusammen. Zur Eindeutigkeit:  Bei ${}n=2$ ist die Aussage klar. Im Allgemeinen seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

${}n=p_{1}{\cdots }p_{r}=q_{1}{\cdots }q_{s}\,.$

Insbesondere teilt die Primzahl ${}p_{1}$ dann das Produkt rechts, und damit nach dem Lemma von Euklid einen der Faktoren. Nach Umordnung können wir annehmen, dass ${}q_{1}$ von ${}p_{1}$ geteilt wird. Da ${}q_{1}$ selbst eine Primzahl ist, folgt, dass ${}p_{1}=q_{1}$ sein muss. Da ${}\mathbb {Z}$ nullteilerfrei ist, kann man beidseitig durch ${}p_{1}=q_{1}$ dividieren und erhält die Gleichung

${}n^{\prime }=p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,.$

Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung der Eindeutigkeit auf ${}n'$ anwenden. 

Zur bewiesenen Aussage