2. Primzahlen

Eine Primzahl ist eine natürliche Zahl größer oder gleich zwei, die außer der Eins und sich selbst keinen positiven Teiler aufweist. Der Begriff der Primzahl, der sich ganz natürlich aus der Untersuchung der Teilbarkeit ergibt, gehört zu den magischen Elementen der Mathematik. Durch ihre geheimnisvolle Verteilung besitzen die Primzahlen eine große Strahlkraft auch über die Mathematik hinaus, und aufgrund der zahlreichen einfach zu formulierenden, oft aber sehr schwer zu beantwortenden Fragen nehmen sie einen prominenten Platz in der Geschichte der Mathematik ein. Primzahlen sind Prüfsteine des mathematischen Gesamtwissens. Viele Fragen sind bis heute offen. Hinzu kommen die modernen Anwendungen in der Kryptographie, durch die das mathematische Ansehen der Primzahlen noch einmal gesteigert wurde.

 In diesem Kapitel stellen wir Primzahlen samt einigen gelösten und ungelösten Problemen vor. Wir beweisen den klassischen Satz von Euklid, der besagt, dass es keine größte Primzahl gibt. Damit ist die Menge der Primzahlen unendlich. Ein weiteres wichtiges Ergebnis ist die Eindeutigkeit der Primfaktorzerlegung. Wir geben einen modernen Beweis dieses Fundamentalsatzes der Zahlentheorie mit Hilfe starker Induktion.