Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 …

Das Wort „Primzahl“ kommt aus dem Lateinischen (numerus primus) und bedeutet „die erste Zahl“. Die fundamentale Bedeutung der Primzahlen für viele Bereiche der Mathematik beruht auf den folgenden drei Konsequenzen aus dieser Definition:

• Primzahlen lassen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen. Diese Eigenschaft wird als Definition für Verallgemeinerungen genutzt.
• Lemma von Euklid: Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist bereits einer der Faktoren durch sie teilbar.
• Existenz und Eindeutigkeit der Primfaktorzerlegung: Jede natürliche Zahl lässt sich als Produkt von Primzahlen schreiben. Diese Produktdarstellung ist bis auf die Reihenfolge der Faktoren eindeutig.