Banner der Website mathematik.de. Motiv: Überall ist Mathematik

Primzahlen

2, 3, 5, 7, 11, 13, 17, 19, 23, ...

Was ist eine Primzahl?

Eine natürliche Zahl wird Primzahl genannt, wenn sie größer als 1 ist und nicht als Produkt von zwei kleineren Zahlen geschrieben werden kann. Z.B. ist 7 eine Primzahl, da es außer 1 und 7 keine Teiler gibt; 12 dagegen ist keine Primzahl, da man 12 - zum Beispiel - als "2 mal 6" schreiben kann. Durch Ausprobieren kann man die Primzahleigenschaft von nicht zu großen Zahlen leicht ermitteln. Hat man einen geeignet programmierten Computer zur Verfügung, so kann man sich die Arbeit abnehmen lassen und zum Beispiel feststellen, dass 1236718507534581290478731 ebenfalls eine Primzahl ist.
Primzahlen faszinieren die Mathematiker schon seit über 2000 Jahren. Obwohl viele sehr tief liegende Sachverhalte über Primzahlen bekannt sind, gibt es noch zahlreiche offene Probleme.

Primzahlen sind die ,,Bausteine'' der Zahlen

Primzahlen können multiplikativ nicht zerlegt werden. Jede andere Zahl ist als Produkt von Primzahlen schreibbar, etwa ,,20'' als ,,2 mal 2 mal 5'' oder ,,110'' als ,,2 mal 5 mal 11''. Diese Produktdarstellung ist sogar bis auf die Reihenfolge eindeutig.
Als etwas gewagte Analogie könnte man also sagen: Betrachtet man die Zahlen 1, 2, 3, 4, ... als so etwas wie die ,,Moleküle" der Zahlen, so entsprechen die Primzahlen den ,,Atomen''.
Insbesondere folgt so: Für jede Zahl gibt es einen Teiler, der sogar Primzahl ist.

Wie viele Primzahlen gibt es?

Durch Ausprobieren kommt man schnell zu der Vermutung, dass es beliebig viele Primzahlen gibt: Man kann immer eine noch größere finden.
Dass das wirklich so ist, wurde schon im alten Griechenland von Euklid bewiesen. Dieser Beweis gehört zu den bekanntesten der gesamten Mathematik, er ist auch nicht besonders schwierig:

Die Beweisidee besteht in der Angabe eines Verfahrens, das bei Eingabe von n Primzahlen mindestens n+1 Primzahlen produziert. (Das "n" könnte Laien verwirren, es soll für irgendeine natürliche Zahl stehen. Ausführlicher heißt es: Das Verfahren macht aus 2 Primzahlen 3 Primzahlen, aus 3 Primzahlen 4 Primzahlen, aus 4 Primzahlen 5 Primzahlen usw.) Wenn es so ein Verfahren gibt, kann die Anzahl der Primzahlen offensichtlich nicht beschränkt sein.
Das Verfahren geht so: Sind n Primzahlen gegeben, so geben wir ihnen erst einmal einen Namen; sie sollen p1, p2, ..., pn heißen. Dann bilden wir das Produkt aller dieser Zahlen und addieren 1, in Formeln:
m = p1 mal p2 mal ... mal pn + 1.
Von dieser - eventuell riesengroßen - Zahl m suchen wir nun einen Teiler, der Primzahl ist; warum das geht, steht im vorigen Abschnitt.
Dieser Primteiler soll p genannt werden. Und nun die Pointe: Teilt man m durch p, so geht es auf, denn p ist ja ein Teiler. Teilt man dagegen m durch p1 (oder durch p2, oder p3, oder ...), so geht es nicht auf, denn es bleibt der Rest 1. Folglich kann p nicht eine der Zahlen p1, p2, ..., pn sein, wir haben also wirklich eine neue Primzahl erhalten.

Zusammen: Es gibt unendlich viele Primzahlen.

Wie kann man systematisch alle Primzahlen finden?

Das bekannteste Verfahren ist das Sieb des Eratosthenes, benannt nach dem griechischen Mathematiker Eratosthenes von Kyrene, der im dritten vorchristlichen Jahrhundert lebte.
Hier sein Vorschlag, um alle Primzahlen zu finden:

Schreibe die natürlichen Zahlen, beginnend mit 2, hintereinander hin:
2, 3, 4, 5, 6, 7, 8, 9, ...
Streiche alle echten Vielfachen von 2, also 4, 6, ...:
2, 3, 4, 5, 6, 7, 8, 9, ...
Streiche alle echten Vielfachen von 3, also 6, 9, ... (die 6 ist schon in der ersten Runde ausgeschieden): 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

Und so weiter: Als nächstes werden die Vielfachen von 5 gestrichen, dann die von 7 usw. Genauer: Im k-ten Durchgang streiche die Vielfachen der k-ten Zahl, die bis dahin noch ,,überlebt'' hat; das ist dann die k-te Primzahl.
Die Begründung für den Erfolg des Verfahrens ist leicht: Jede Nicht-Primzahl n hat einen echten Primteiler p, und damit wird n bei der zu p gehörigen Streichungsrunde gestrichen.

Wie sind die Primzahlen verteilt?

Es ist plausibel, dass es im Bereich ,,sehr großer'' Zahlen immer weniger Primzahlen gibt, denn für große n haben viel mehr Zahlen die Möglichkeit, ein Teiler von n zu sein. So wird es sicher prozentual weniger Primzahlen zwischen 1 und 1000 geben als zwischen 1 und 100. Wie sieht es aber genau aus?
Um besser über das Problem reden zu können, werden wir mit P(m) die Anzahl der Primzahlen bezeichnen, die höchstens so groß wie m sind. (Zum Beispiel ist P(10) = 4, denn unterhalb von 10 gibt es 4 Primzahlen: 2, 3, 5 und 7.)
Wie groß ist P(m) für große m? Oder noch besser: Wie groß ist das Verhältnis von P(m) zu m? Schon Gauß hat sich intensiv mit dieser Frage auseinander gesetzt, eine Lösung gab es aber erst gegen Ende des 19. Jahrhunderts. Sie wurde unabhängig voneinander durch Hadamard und de la Vallee-Poussin gefunden, hier ist sie:

Bezeichnet ln(m) den natürlichen Logarithmus von m, so ist das Verhältnis von P(m) zu m in sehr guter Näherung - wenigstens bei ,,großen'' m - durch 1/ln(m) gegeben.
Für alle, die mit dem natürlichen Logarithmus nicht viel anfangen können, folgt hier eine andere Formulierung. Nehmen Sie irgendeine Zahl r, zum Beispiel r=10, und rechnen Sie dann m=2.718 hoch r aus: m = 2.718 mal 2.718 ...mal 2.718, das ganze r mal. In unserem Beipiel r=10 ist m ziemlich genau gleich 22012. Und dann gilt: Der Anteil der Primzahlen, die höchstens so groß wie m sind, ist ziemlich genau gleich 1/r. In unserem Beispiel: Etwa ein Zehntel der Zahlen unter 22012 ist Primzahl.


Primzahltests

Es ist für eine große Zahl m auch mit Computerhilfe sehr mühsam, die Primzahleigenschaft festzustellen. Eigentlich sind alle Zahlen n, die kleiner als m sind, zu testen: Teilt n die Zahl m? Man kann sich aber schnell klar machen, dass man nur Zahlen bis zur Wurzel von m testen muss, denn ist n ein Teiler von m, so ist eine der Zahlen n oder m/n höchstens so groß wie die Wurzel.
Das kann immer noch eine Menge sein. Hat zum Beispiel m 100 Stellen im Dezimalsystem, so hat die Wurzel 50 Stellen. Könnte ein Computer pro Sekunde eine Million Zahlen n testen (lässt sich m durch n teilen?), so hätte er immer noch mehr Jahre zu tun, als das Weltall voraussichtlich bestehen wird. Es gibt aber bessere Tests, hier der bekannteste:

Ausgangspunkt des Tests ist ein Ergebnis, das schon von Fermat gefunden wurde. Es setzt voraus, dass man weiß, was für zwei Zahlen a und b die Zahl ,,a modulo b'' bedeutet: Damit ist die Zahl gemeint, die beim Teilen von a durch b als Rest übrig bleibt. (Zum Beispiel ist 15 modulo 2 gleich 1, und 139 modulo 4 ist gleich 3.)
Fermat konnte nun zeigen: Startet man mit einer Primzahl p und einer Zahl a, die zwischen 1 und p-1 liegt und rechnet man dann a hoch p-1 aus (also die Zahl a mal a mal ... mal a, insgesamt p-1 mal), so gilt: Diese Zahl modulo p ist gleich 1.
Hier ein Test für p=5 und a=3. Es ist 3 hoch 4 gleich 81, und wenn man 81 modulo 5 rechnet, kommt wirklich 1 heraus.
Und warum ist das ein Primzahltest? Soll man m auf Primzahleigenschaft testen, so wähle man ein a kleiner m und prüfe, ob (a hoch m-1) modulo m gleich 1 ist; Computer können das in Windeseile, auch bei sehr großen Zahlen. Kommt etwas von 1 Verschiedenes heraus, war m bestimmt keine Primzahl, obwohl damit noch lange kein Teiler bekannt ist.
Es ist nun so, dass man üblicherweise mit diesem Test sehr schnell herausfinden kann, ob eine Zahl eine Zahl eine Primzahl ist oder nicht. Es gibt einige Ausnahmezahlen, die so genannten Carmichael-Zahlen, bei denen der Test versagt: Der Test ergibt immer 1, obwohl es sich nicht um eine Primzahl handelt. Das kleinste Beispiel ist die Zahl 561. Seit 1992 weiß man, dass es unendlich viele derartige ,,Versager'' gibt, sie sind aber sehr dünn gesät. Glücklicherweise gibt es - etwas komplizierter zu beschreibende - Tests, die immer anwendbar sind.


Einige besondere Primzahlen

Für Zahlen besonders einfacher Bauart gibt es Tests, die viel wirkungsvoller sind, damit können dann viel größere Kandidaten untersucht werden als mit den üblichen Verfahren.
Berühmtes Beispiel dafür sind die Mersenne-Primzahlen, das sind Primzahlen der Form ,,(2 hoch r) - 1''. So sind zum Beispiel 7 (= (2 hoch 3) - 1) und 31 (= (2 hoch 5) - 1) Mersenne-Primzahlen. (2 hoch r) - 1 ist allerdings nicht für jedes r eine Primzahl; setzt man etwa r=4, so kommt als (2 hoch 4) - 1 die Zahl 15 heraus, und die ist sicher nicht prim. Ob es für ein großes r klappt, kann man mit Computerhilfe relativ schnell ermitteln. Daher ist es kein Wunder, dass alle Primzahlrekorde der letzten Zeit von Mersenne-Primzahlen aufgestellt wurden (s.u.).
Bemerkenswert sind auch Primzahlen der Form (2 hoch r)+1, man nennt sie Fermat-Primzahlen. Einfache Beispiele sind 5 und 17, es ist unbekannt, ob es unendlich viele Beispiele gibt. Die sind - überraschenderweise - für die Geometrie wichtig: Man kann ein gleichseitiges n-Eck genau dann mit Zirkel und Lineal konstruieren,wenn n ein Produkt von verschiedenen Fermat-Primzahlen - und möglicherweise noch einer Zweierpotenz - ist. Ein 17-Eck kann man also konstruieren, ebenso ein 80-Eck (denn 80=5· 24), ein 7-Eck aber nicht. Mit solchen Fragen beschäftigte sich übrigens der noch sehr junge Gauß in seiner Dissertation.

Primzahlen sind nützlich!

Primzahlen spielen in der public-key-Kryptographie (= Kryptographie mit öffentlichem Schlüssel) eine wichtige Rolle. Die Idee: Man suche sich zwei große Primzahlen p und q, ,,groß'' bedeutet hier: einige hundert Stellen. Streng geheim! Dann rechne man p mal q aus, das Ergebnis soll n heißen. Die Zahl n wird jedem, der es wissen möchte, verraten, und damit kann man dann Nachrichten verschlüsseln, die nur der/die-jenige entschlüsseln kann, der p und q kennt.

Die Pointe: Es ist nach dem gegenwärtigen Wissensstand praktisch unmöglich, aus einem Produkt p mal q nachträglich wieder p und q herauszubekommen. Bei kleinen Zahlen geht das, ist das Produkt gleich 77, so rät man schnell die Primteiler 7 und 11. Was aber ist mit

78457630683971672300324001194081223769

oder gar mit vierhundertstelligen Produkten aus der professionellen Kryptographie?
Die Sicherheit vieler Kryptosysteme beruht damit allein auf einer zahlentheoretischen Schwierigkeit. Und das macht verständlich, dass einige Leute ziemlich aufgeregt waren, als ein Algorithmus auf der Grundlage von Quantencomputern entwickelt wurde, durch den man auch von riesengroßen zusammengesetzten Zahlen sehr schnell die Faktoren identifizieren kann. Allerdings gibt es Quantencomputer erst auf dem Papier. Jedenfalls nach dem gegenwärtigen Stand der Technik.
(Wie Quantencomputer die Kryptographie revolutionieren würden, ist etwas genauer in einem Beitrag des Buches ,,Alles Mathematik'' beschrieben: M. Aigner - E. Behrends, Vieweg Verlag 2000.)

Die größte zurzeit bekannte Primzahl

Rekordhalter ist jetzt, im Dezember 2001, die Zahl

213466917 - 1 .

Das ist eine Mersenne-Primzahl, Tests für andere Typen so großer Zahlen stehen auch nicht zur Verfügung. Der Rekordhalter hat etwa 4 Millionen Stellen, wollte man ihn in einem Buch abdrucken, käme ein dicker Wälzer heraus. Interessierte können zur Internetseite für Mersenne-Primzahlen weitersurfen oder sich die entsprechende Meldung ansehen.

Wir haben inzwischen 2010, auf http://www.mersenne.org/default.php kann die Rekordjagd verfolgt werden. Die aktuell größte bekannte Primzahl ist inzwischen 243.112.609-1 mit fast 13 Millionen Stellen. Wir berichteten 2008 hierüber auf mathematik.de.

Die Goldbach-Vermutung

Primzahlen sind durch eine multiplikative Eigenschaft defininiert. Damit ist zunächst unklar, was passiert, wenn man Fragen über Primzahlen stellt, bei denen es um Addition geht. Das berühmteste offene Problem in diesem Zusammenhang ist zweifellos die Goldbach-Vermutung, benannt nach dem Mathematiker Goldbach aus dem 18. Jahrhundert:

Stimmt es oder stimmt es nicht, dass jede gerade Zahl größer als 3 als Summe von zwei Primzahlen geschrieben werden kann?
(Zum Beispiel ist 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, ...; geht das immer??)

Bemerkungen dazu:

- Das Problem scheint sehr schwierig zu sein, viele haben sich schon vergeblich daran versucht.
- Wer es löst, wird schlagartig berühmt und reich.
- Es gibt einen Roman zum Problem, der sehr lesenswert ist.