Zahlentheorie/Primfaktorzerlegung/Fakt/Beweis/Aufgabe/Lösung


Die Eindeutigkeit wird durch Induktion über gezeigt. Für liegt eine Primzahl vor. Es sei nun und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl das Produkt rechts teilt. Nach dem Lemma von Euklid muss dann einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Daraus ergibt sich durch Kürzen, dass

ist. Nennen wir diese Zahl . Da ist, können wir die Induktionsvoraussetzung auf anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen.