Existenz und Eindeutigkeit der Primfaktorenzerlegung

Bei der Definition der Primfaktorenzerlegung treten zwei Fragen auf: Existiert diese für jede natürliche Zahl und sind die Primfaktoren einer Zerlegung (bis auf die Reihenfolge) immer gleich. Beide Fragen beantwortet der sogenannte Fundamentalsatz der Arithmetik positiv. Diese Satz wurde von Gauß erstmals mathematisch streng bewiesen, war aber schon im antiken Griechenland bekannt.

Jede natürliche Zahl $n>=2$ lässt bis auf die Reihenfolge eindeutig als Produkt von Primzahlen darstellen.

Sei $m>=2$ die kleinste natürliche Zahl für die keine Primfaktorenzerlegung existiert (wenn es überhaupt so eine Zahl gibt, muss es auch eine kleinste geben). $m$ ist keine Primzahl, denn diese haben eine triviale Primfaktorenzerlegung, die mit der Zahl selbst übereinstimmt. Damit gibt es $a,b\in \N$ mit $m>a,b>=2$ und $m=a\cdot b$. Da $m$ die kleinste natürliche Zahl ohne Primfaktorenzerlegung war, gibt es für $a$ und $b$ Primfaktorenzerlegungen. Seien diese: $a=\prod\limits p_i$ und $b=\prod\limits p_j$, wobei die $p_i$ und $p_j$ prim sind. Dann gilt $m=a\cdot b=\prod\limits p_i\cdot \prod\limits p_j$. Also haben wir eine Primfaktorenzerlegung für $m$ gefunden, im Widerspruch zur Annahme, dass eine solche für $m$ nicht existiert.

Wir nehmen wieder an, dass $m>=2$ die kleinste natürliche Zahl ist, deren Primfaktorenzerlegung nicht eindeutig ist. Da die Primfaktorenzerlegung für Primzahlen trivialerweise eindeutig ist, muss es sich bei $m$ um eine zusammengesetzte Zahl handeln.

Je zwei Zerlegungen von $m$ können keinen gemeinsamen Primfaktor enthalten. Denn wäre $p$ ein solcher, so hätte auch $m/p$ zwei Primfaktorenzerlegungen, im Widerspruch zur Annahme, dass $m$ die kleinste Zahl mit mehreren Primfaktorenzerlegung ist.

Es gibt also zwei Primzahlen $p!= q$, sodass $m=p\cdot a=q\cdot b$. Nach Satz 5303G ergibt sich nun dass $p|q\cdot b$, also $p|b$, da $p|q$ nicht möglich ist. Damit taucht aber $p$ als Primfaktor in $b$ auf, im Widerspruch dazu, dass 2 Zerlegungen keinen gemeinsamen Primfaktor enthalten können. Damit müssen wir unsere Annahme, dass es Zahlen mit mehreren Primfaktorenzerlegungen gibt fallen lassen und die Eindeutigkeit der Primfaktorenzerlegung ist bewiesen. $\qed$