Primzahlen berechnen – nicht nur was für Mathematiker

Mit Aufgaben zur Berechnung von Primzahlen wollen die Lehrer Schüler nicht nur ärgern. Sie helfen u. a. Unternehmen besser zu verstehen, ob Bewerber anhand von mathematischen Grundregeln und durch sorgfältiges Arbeiten bestimmte Zahlen als Primzahlen oder zusammengesetzte Zahlen identifizieren können. Deshalb eignet sich diese Seite insbesondere auch als Vorbereitungsseite für das Bewerberauswahlverfahren.

Eine Spielwiese für viele Mathematiker

Primzahlen sind natürliche (also positive, ganze) Zahlen, die nur durch 1 und sich selbst teilbar sind. Zwar erfüllt die Zahl 1 auch beide Bedingungen, gehört aber, gerade weil sie für die Definition gebraucht wird, selbst nicht dazu. Die kleinste Primzahl ist daher die 2. Weiter geht es mit 3, 5, 7, 11, 13, 17, 19, … Die Liste ist lang. Sehr lang. Benutzt werden die Zahlen unter anderem zur Datenverschlüsselung im Internet. Und weil die Definition der Primzahlen so schön einfach ist, ist es ein Hobby vieler Mathematiker, sich mit ihnen auseinander zu setzen. Man kann zum Beispiel fragen: Wie viele Primzahlen gibt es? Kann man sie mit einer Formel berechnen?

Ein historischer Beweis

Auf die erste Frage gibt es eine klare Antwort. Dass es unendlich viele Primzahlen gibt wurde bereits um 300 v. Chr. von Euklid bewiesen. Sein Beweis funktioniert indirekt. Das heißt, dass man das Gegenteil dessen annimmt, was man beweisen will und einen Widerspruch herleitet. Also nimmt man an, man hätte alle Primzahlen gefunden und in einer Liste durchnummeriert: .
Dann muss die Zahl einen Primteiler p besitzen. Dieser kann aber mit keiner der p Primzahlen übereinstimmen, weil beim Teilen immer ein Rest von 1 übrig bleibt. Die Liste war also doch nicht vollständig und ist eine weitere Primzahl. Den Beweis kann man beliebig oft wiederholen.

Verheißungsvolle Kandidaten

Direkt berechnen kann man Primzahlen nicht. Doch es gibt bestimmte Zahlen, bei denen die Wahrscheinlichkeit, dass es sich bei Ihnen um Primzahlen handelt, größer ist als bei anderen. Pierre Fermat vermutete, dass alle Zahlen Fk der Form , für natürliche Zahlen k, Primzahlen sind. Das stimmt aber nur für k = 0, 1, 2, 3 und 4. Aussichtsreicher ist das Testen von sogenannten Mersenneschen Zahlen (oder Mersenne-Zahlen). Das sind Zahlen Mk der Form , wobei k wieder eine natürliche Zahl ist. Wenn k eine Primzahl ist, besteht die Möglichkeit, dass auch Mk eine ist. Im September 2013 wurde durch das Testen von Mersenneschen Zahlen die bislang größte Primzahl entdeckt, nämlich , eine Zahl mit 17.425.170 Stellen. Die Berechnungen werden inzwischen von Computern durchgeführt. Jeder kann an der Suche nach der nächstgrößten Primzahl teilnehmen, indem er auf seinem Computer ein entsprechendes Programm im Hintergrund laufen lässt (Projekt GIMPS).