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} \dots p_{r} = q_{1} \dots 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} \dots p_{r} = q_{2} \dots 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