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

Die Eindeutigkeit wird durch Induktion über ${}n$ gezeigt.  Für ${}n=2$ liegt eine Primzahl vor und die Aussage ist klar. Es 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 dem Lemma von Euklid 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 gelösten Aufgabe