Beweis

Wir beweisen die Existenz und die Eindeutigkeit jeweils durch Induktion.  Für liegt eine Primzahl vor. Bei ist entweder eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung mit kleineren Zahlen . Für diese Zahlen gibt es nach der Induktionsvoraussetzung eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für zusammen. Zur Eindeutigkeit:  Bei ist die Aussage klar. Im Allgemeinen seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

Insbesondere teilt die Primzahl dann das Produkt rechts, und damit nach dem Lemma von Euklid einen der Faktoren. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Da nullteilerfrei ist, kann man beidseitig durch dividieren und erhält die Gleichung

Da ist, können wir die Induktionsvoraussetzung der Eindeutigkeit auf anwenden.