Definition
Eine Natürliche Zahl heißt Primzahl, wenn sie nur durch 1 oder sich selbst teilbar ist.
Eigenschaften
Euklids erster Satz
Ist prim und sind mit , dann gilt oder
D.h.: Ist durch eine Primzahl teilbar, so ist entweder oder durch eine Primzahl teilbar.
Euklids zweiter Satz
Es gibt unendlich viele Primzahlen
Beweis: Angenommen es gibt eine endliche Menge aller Primzahlen. Dann ist das Produkt aller dieser Zahlen eine ganze Zahl und offensichtlich durch jede Primzahl teilbar.
Betrachte aber nun ! ist durch keine Primzahl teilbar, da erst die nächste durch teilbare Zahl ist. Also muss entweder eine neue Primzahl sein oder unentdeckte Primzahlen enthalten. Dadurch erhalten wir aber einen Widerspruch, da somit nicht die Menge aller Prizahlen war.
Primzahlsatz
Der Primzahlsatz beschreibt, wie häufig Primzahlen vorkommen. Sei Dann gilt