Wir beweisen die Existenz durch Induktion über ${\displaystyle {}n}$.  Für ${\displaystyle {}n=2}$ liegt eine Primzahl vor. Bei ${\displaystyle {}n\geq 3}$ ist entweder ${\displaystyle {}n}$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ${\displaystyle {}n}$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung ${\displaystyle {}n=ab}$ mit kleineren Zahlen ${\displaystyle {}a,b<n}$. Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für ${\displaystyle {}n}$ zusammen.