Eine Primzahl ist eine natürliche Zahl , die genau Teiler besitzt, nämlich und . Zum Beispiel sind Primzahlen, während und keine Primzahlen sind.
Beweise durch Induktion, daß sich jede natürliche Zahl als Produkt von Primzahlen schreiben läßt.