Eine ansprechende Zusammenstellung der wesentlichen Ergebnisse über Primzahlen und aktueller Primzahl-Rekorde nebst historischen Bezügen, grundlegenden Sätzen sowie den wichtigsten offenen Fragen und ungelösten Problemen.
/ AUS DEM INHALT: / / /
Vorwort zur zweiten Auflage vii
Vorwort zur ersten Auflage ix
Danksagungen xi
Anleitung für den Leser xvii
Erklärung der Symbole xix
Einleitung 1
1 Wie viele Primzahlen gibt es? 3
I Beweis von Euklid 3
II Ein Beweis von Goldbach! 6
III Beweis von Euler 8
IV Beweis von Thue 10
V Drei vergessene Beweise 10
A Beweis von Perott 11
B Beweis von Auric 11
C Beweis von Metrod 12
VI Beweis von Washington 12
VII Beweis von Furstenberg 13
2 Wie kann man Primzahlen erkennen? 15
I Das Sieb des Eratosthenes 16
II Einige grundlegende Sätze über Kongruenzen 17
A Der kleine Satz von Fermat und Primitivwurzeln modulo einer Primzahl 17
B Der Satz von Wilson 20
C Die Eigenschaften von Giuga und von Wolstenholme 22
D Primzahlpotenzen als Teiler der Fakultät einer Zahl 24
E Der chinesische Restsatz 27
F Die Eulersche ^-Funktion 28
G Folgen von Binomialzahlen 34
H Quadratische Reste 37
III Klassische Primzahltests auf der Grundlage von Kongruenzen
IV Lucas-Folgen 44
V Primzahltests auf der Grundlage von Lucas-Folgen 59
VI Fermat-Zahlen 71
VII Mersenne-Zahlen 76
VIII Pseudoprimzahlen 90
A Pseudoprimzahlen zur Basis 2 (psp) 90
B Pseudoprimzahlen zur Basis a (psp(a)) 94
C Euler-Pseudoprimzahlen zur Basis a (epsp(a)) 97
D Starke Pseudoprimzahlen zur Basis a (spsp(a)) 98
IX Carmichael-Zahlen 102
X Lucas-Pseudoprimzahlen 105
A Fibonacci-Pseudoprimzahlen 106
B Lucas-Pseudoprimzahlen (lpsp(P, Q)) 108
C Euler-Lucas-Pseudoprimzahlen (elpsp(P, Q)) und starke Lucas-Pseudoprimzahlen (slpsp(P, Q)) 109
D Carmichael-Lucas-Zahlen 110
XI Primzahltests und Faktorisierung 111
A Aufwand für einen Primzahltest 112
B Weitere Primzahltests 113
C Titanische und sonderbare Primzahlen 123
D Faktorisierung 126
E Kryptographie mit öffentlichem Schlüssel 132
3 Gibt es primzahldefinierende Funktionen? 137
I Funktionen mit der Eigenschaft (a) 137
II Funktionen mit der Eigenschaft (b) 143
III Primzahlerzeugende Polynome 144
A Primzahlwerte linearer Polynome 146
B Über quadratische Zahlkörper 146
C Primzahlerzeugende quadratische Polynome 151
D Der Wettlauf um Primzahlwerte und Primteiler 155
IV Funktionen mit der Eigenschaft (c) 158
4 Wie sind die Primzahlen verteilt? 163
I Die Funktion TT(S) 164
A Historische Entwicklung 165
B Summen unter Einschluss der Möbius-Funktion . 178
C Primzahltabellen 179
D Exakte Werte von ir(x) und Vergleiche mit x/ log x, Li(z) und R(x) 180
E Die nichttrivialen Nullstellen von £(s) 183
F Nullstellenfreie Bereiche von £(s) und das Fehlerglied im Primzahlsatz 187
G Einige Eigenschaften von ir(x) 188
H Die Verteilung der Werte von Eulers Funktion 190
II Die n-te Primzahl und Lücken zwischen Primzahlen 191
A Die n-te Primzahl 191
B Lücken zwischen Primzahlen 192
III Primzahlzwillinge 200
IV Primzahlmehrlinge 206
V Primzahlen in arithmetischer Folge 213
A Es gibt unendlich viele! 213
B Die kleinste Primzahl in einer arithmetischen Folge 215
C Primzahlreihen in arithmetischer Folge 217
VI Goldbachs berühmte Vermutung 220
VII Die Verteilung von Pseudoprimzahlen und Carmichael- Zahlen 226
A Verteilung von Pseudoprimzahlen 226
B Verteilung von Carmichael-Zahlen 228
C Verteilung von Lucas-Pseudoprimzahlen 230
5 Welche besonderen Arten von Primzahlen wurden untersucht? 233
I Reguläre Primzahlen 233
II Sophie-Germain-Primzahlen 237
III Wieferich-Primzahlen 240
IV Wilson-Primzahlen 245
V Repunit-Primzahlen 246
VI Zahlen der Form kxbn±l 248
VII Primzahlen und linear rekurrente Folgen zweiter Ordnung 256
6 Heuristische und probabilistische Betrachtungen 263
I Primzahlwerte linearer Polynome 264
II Primzahlwerte von Polynomen beliebigen Grades 267
III Polynome mit großen Bereichen zerlegbarer Werte 275
IV Partitio Numerorum 277
Anhang 283
Ausklang 287
Literatur 289
Webseiten 333
Primzahlen bis 10 000 337
Verzeichnis der Tabellen 341
Verzeichnis der Rekorde 343
Namensverzeichnis 345
Sachverzeichnis 359