Primzahlen sind natürliche Zahlen, die nur durch sich selbst und durch 1 teilbar sind, wobei 1 ausgenommen wird. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 sind die ersten zehn Primzahlen. (Allgemeiner definiert man in einem Integritätsbereich: Ein Element eines Integritätsbereiches wird Primelement genannt, falls es erstens weder eine Einheit ist noch die Null ist. Zweitens: Teilt das Element ein Produkt, so muss es auch eines der Faktoren teilen.) Eine interessante Frage ist, ob unendlich viele Primzahlen exisitieren. Folgender Beweis wird auf Euklid zurückgeführt und ist wegen seiner Einfachheit mein Lieblingsbeweis:
Nehmen wir an, es exisitieren nur endlich viele Primzahlen p1, p2, p3…pn. Dann können wir das Produkt p darüber bilden: p:=p1* p2* p3…pn. Die Zahl p+1 ist größer als jede Primzahl und damit keine Primzahl. Da p durch jede Primzahl teilbar ist, ist p+1 durch keine einzige Primzahl teilbar. Nach Definition müßtep+1 eine Primzahl ist, was sie aber nicht ist. Dies ist ein Widerspruch und damit muß es unendlich viele Primzahlen geben.