Zahlentheorie/Primfaktorzerlegung/Fakt/Beweis3

Beweis

Die Existenz der Primfaktorzerlegung wurde bereits in Fakt gezeigt. Die Eindeutigkeit wird durch Induktion über ${}n$ gezeigt. Für ${}n=2$ liegt eine Primzahl vor. Sei nun ${}n\geq 3$ und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

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

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl ${}p_{1}$ das Produkt rechts teilt. Nach Fakt muss dann ${}p_{1}$ einen der Faktoren rechts teilen. 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. Daraus ergibt sich durch Kürzen, dass

${}p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,$

ist. Nennen wir diese Zahl ${}n'$. Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung auf ${}n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

Zur bewiesenen Aussage