Primzahlen für Einsteiger 1
Primzahlen für Einsteiger
Alte und neue Ergebnisse
Primzahlen für Einsteiger 2
Referenzen: Meine Hochschule
Primzahlen für Einsteiger 3
Mein Fachbereich
• 500 Studierende
• 2 Sekretärinnen
• 6 Assistenten
• 3 Professorinnen, 12 Professoren
• Viele Lehrbeauftragte aus der Wirtschaft
Primzahlen für Einsteiger 4
Referenzen: Meine Gemeinde
• Fritz-Herrmann Lutz,
bewundernswerter Kommunikator, aber:
• Er hat noch nie eine Matheveranstaltung in Eppelborn besucht. Mathephobie?
Primzahlen für Einsteiger 5
Der Plan
• Teilbarkeit • Was ist eine Primzahl• Warum Primzahlen interessant sind• Wie viele Primzahlen gibt es • Pause für notwendige körperliche Aktivitäten• Primzahlen finden• Rekorde• Kuriosa
Primzahlen für Einsteiger 6
Haben Sie eine Lieblingsprimzahl?
Meine Lieblingsprimzahl: 1742 ist keine Primzahl!
Primzahlen für Einsteiger 7
Der Anfang: Pythagoras
Pythagoras:Geboren: 569 v.Chr. In Samos, Ionien
Gestorben: 475 v. Chr.(in Kroton??)
Vor allem Philosoph, der erste reine MathematikerZahlenmystiker(Perfekte Zahlen, alles in Proportionen)
Primzahlen für Einsteiger 8
Die Geographie der Mathematik
Primzahlen für Einsteiger 9
Die Geographie der Mathematik
Primzahlen für Einsteiger 10
Was ist eine Primzahl?
Die Definition, die Sie kennen:Eine Zahl heißt Primzahl, wenn sie nur durch 1 und sich selbst teilbar ist.
Es geht um natürliche Zahlen, es geht um Teilbarkeit.
Schon jetzt: 1 ist keine Primzahl, sie macht nur unnötigen Ärger! Raus aus dem Primzahlenhimmel!
Primzahlen für Einsteiger 11
Teilbarkeit bei ganzen Zahlen
Beispiele:
7 teilt 42, 7|42, denn 42 ist Vielfaches von 7, d.h. 42 = 7 ∙ 6
8 teilt 42 nicht, 8 ┼ 42, denn 42 ist nicht Vielfaches von 8, d.h. es gibt keine Zahl c mit 42 = 8 ∙ c
Primzahlen für Einsteiger 12
Teilbarkeit bei ganzen Zahlen
Die grundlegende Definition:
a, b, c seien ganze Zahlen.
a │b bedeutet: b ist Vielfaches von a:
Es gibt eine Zahl c mit
b = a ∙ c
Primzahlen für Einsteiger 13
Teilbarkeitseigenschaften7 │ 42 und 7 │63, also auch 7 │ (42 + 63),7 │105
a │ b und a │c, dann auch a │ (b + c)
7 │ 42 und 7 │63, also auch 7 │ (42 - 63),7 │-21
a │ b und a │c, also auch a │ (b - c)
Satz: Teilt a die Zahlen b und c, dann auch deren Summe und Differenz.
Primzahlen für Einsteiger 14
Teilbarkeitseigenschaften
7 │ 42, also auch 7 │ 20 ∙ 42
a │ b, dann auch a │ c ∙ b
Satz:Teilt a die Zahl b, dann auch jedes Vielfache von b
Problem: Gilt das Folgende (eine Art Umkehrung):
Aus a │ b ∙ c folgt: a │b oder a │c ?
Primzahlen für Einsteiger 15
Teilbarkeitseigenschaften
Die Umkehrung ist falsch:
Aus a │ b ∙ c folgt nicht: a │b oder a │c
Gegenbeispiel:
Primzahlen für Einsteiger 16
Primzahlen
Die endgültige Definition:
Eine natürliche Zahl, von 1 verschieden, heißt Primzahl, wenn sie nur durch 1 und sich selbst teilbar ist.
1 ist keine Primzahl. (Eine Konvention der Mathematiker)
Primzahlen für Einsteiger 17
Einige Primzahlen
Die ersten Primzahlen:
2, 3, 5, 7, 11, 13, 17, …. (?)
Primzahlen für Einsteiger 18
Teilermengen
T(42) = {1, 2, 3, 4, 6, 7, 14, 21, 42}
T(105) = {1, 3, 5, 7, 15, 21, 35, 105}
T(43) = {1, 43}
T( 143) = {1, 11, 13, 143}
Die zweitkleinste Zahl ist stets Primzahl
Primzahlen für Einsteiger 19
Warum Primzahlen wichtig sind(Theorie)
Der Fundamentalsatz der Arithmetik:
Jede Zahl lässt sich eindeutig in Primfaktoren zerlegen
Beispiele:
42 = 2∙3∙7700 = 2∙2∙5∙5∙7 = 22∙52∙7
Sie finden dies bei Euklid
Primzahlen für Einsteiger 20
Euklid
Euklid:
Geb. 325 v. Chr.
Gst: 265 v. Chr. in
Alexandria
Der Mathematiker des
Altertums
Primzahlen für Einsteiger 21
Wie zerlegt man in Primfaktoren?
Beispiele:
Z = 42Z = 182Z = 3553Z = 135014
Dies ist nicht einfach!
Primzahlen für Einsteiger 22
Warum Primzahlen wichtig sind(Praxis)
Große Primzahlen für
asymmetrische Verfahren der Kryptologie
Es ist schwierig, die Primfaktorzerlegung großer Zahlen herzustellen.
Primzahlen für Einsteiger 23
Wie viele Primzahlen gibt es?
Euklid:
Es gibt unendlich
viele Primzahlen
Primzahlen für Einsteiger 24
Schönheit in der Mathematik
Paul Erdös Idee:
Proofs from the Book
Eine Sammlung
schöner Beweise
Primzahlen für Einsteiger 25
Proofs from the Book
Start:
6 Beweise, dass es unendlich viele Primzahlen gibt
Primzahlen für Einsteiger 26
Euklids Beweis
Primzahlen für Einsteiger 27
Euklids Beweis, ins Konstruktive gewendet
Die Idee:
Aus endlich vielen Primzahlen kann man eine neue konstruieren.
Beispiele:
p1 = 2, p2 = 3, p3 = 5
E = 2∙3∙5 + 1 = 31: Eine neue Primzahl!
Primzahlen für Einsteiger 28
Euklids Beweis, ins Konstruktive gewendet
Beispiele:
p1 = 3, p2 = 5, p3 = 7
E = 3∙5∙7 + 1 = 106: Keine neue Primzahl!
Aber:
E enthält eine neue Primzahl als Faktor, hier die Zahl 2. Keine der Zahlen 3,5,7 teilt 106
Primzahlen für Einsteiger 29
Euklids Beweis, ins Konstruktive gewendet
Allgemein:
p1, p2, p3, …, pn seien Primzahlen.
E = p1∙ p2 ∙ p3 ∙ … ∙ pn + 1 :
Keine der Zahlen p1, p2, p3, …, pn teilt E.
Die Primfaktoren von E sind neue Primzahlen.
Primzahlen für Einsteiger 30
Unendlich viele Primzahlen, ist das genug?
• In der Kryptologie interessant:
Primzahlen mit etwa 300 Stellen.
• Gibt es genügend viele davon?
• Es gibt unendlich viele Zahlen der Form nn, aber nur 139 mit weniger als 300 Stellen
Primzahlen für Einsteiger 31
Noch schlimmer: Primzahlenlücken
Es gibt beliebig große Primzahlenlücken.
Beweisidee: Eine Lücke der Länge 42
43! + 2, 43! + 3, 43! + 4, ….. , 43! + 43
(Aber: 43! = 6 ∙ 1052)
Primzahlen für Einsteiger 32
Die Verteilung der Primzahlen
π(10) = |{2, 3, 5, 7}| = 4
π(20) = |{2, 3, 5, 7, 11, 13, 17, 19}| = 8
π(30) = |{2, 3, 5, 7, 11, 13, 17, 19
Beispiele:
, 2
π(x) = Anzahl der Primzahlen x
3, 29}| = 10
π(100) = 25; π(1000) = 168;
π(1 000 000) = 78 498
Primzahlen für Einsteiger 33
Der Primzahlensatz (1896)
Satz:
Für große x: xπ(x)
ln(x)
Primzahlen für Einsteiger 34
Der Primzahlensatz (1896)
Nicolas de la Vallee-
Poussin
(1866 – 1962)
Primzahlen für Einsteiger 35
Der Primzahlensatz (1896)
Jacques Salomon
Hadamard
(1865 – 1962)
Primzahlen für Einsteiger 36
Wie viele Primzahlen bis 10300?
300 300300 297
300
10 10π(10 ) > 10
ln(10 ) 300 ln(10)
Primzahlen für Einsteiger 37
Bestimmung von Primzahlen
Verschiedene Vorgehensweisen:
– Siebe (Eratosthenes, quadratische Siebe)– Formeln (traurig und schön)– Monte-Carlo-Methoden für große Primzahlen
Primzahlen für Einsteiger 38
Das Sieb des Eratosthenes
Eratosthenes
Geb.: 276 v. Chr. in Cyrene (Libyen)
Gest.: 194 v. Chr. in Alexandria
Zahlentheoretiker.
Bestimmte den Erdumfang, ebenso die Abstände vonMond und Sonne
Primzahlen für Einsteiger 39
Sieb des Eratosthenes:Alle Primzahlen bis 50
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
Primzahlen für Einsteiger 40
Mersenne Zahlen
Marin Mersenne
Geb.: 1588 in OizeGest.: 1648 in Paris
Mathematiker undPhysiker,suchte Formeln für Primzahlen
Primzahlen für Einsteiger 41
Mersenne Zahlen
M(p) = 2p – 1, p Primzahl
M(2) = 3
M(3) = 7
M(5) = 31
M(7) = 127
M(11) = 2047 = 23*89, also keine Primzahl
Primzahlen für Einsteiger 42
Mersenne Zahlen
Der Stand der Kunst:
2000 waren 37 Mersenne-Primzahlen
bekannt.
Rekord-Mersenne-Primzahl:
M(3 021 377) (mit mehr als 2 Millionen Stellen)
Primzahlen für Einsteiger 43
Exkurs: Vollkommene Zahlen
x heißt vollkommen, wenn x gleich derSumme der echten Teiler von x ist.
Beispiele: 6 = 1 + 2 + 3 = 2 * 3 = 2(2-1) * M(2)
28 = 1 + 2 + 4 + 7 + 14 = 4 * 7 = 4 * M(3) = 2(3-1) * M(3)
Primzahlen für Einsteiger 44
Vollkommene gerade Zahlen
Satz von Euklid und Euler:
Eine gerade Zahl x ist genau dann
vollkommen, wenn sie von der Form
2(p-1) * M(p)
ist, wobei p und M(p) Primzahlen sind
Primzahlen für Einsteiger 45
Fermat-Zahlen
Pierre der Fermat
Geb.: 1601 in
Beaumont de Lomagne
Gest.: 1665 in Castres
Genialer
Zahlentheoretiker
Primzahlen für Einsteiger 46
Fermat-Zahlen
n(2 )F(n) = 2 1Fermats Vermutung:
Alle Zahlen dieser Form sind Primzahlen.
Primzahlen für Einsteiger 47
Fermat-Zahlen
F(0) = 21 + 1 = 3, PrimzahlF(1) = 22 + 1 = 5, PrimzahlF(2) = 24 + 1 = 17, PrimzahlF(3) = 28 + 1 = 257, PrimzahlF(4) = 216 + 1 = 65 537, Primzahl
Lauter Primzahlen!
Primzahlen für Einsteiger 48
Eulers Antwort
Leonhard Euler
Geb.: 1707 in BaselGest.: 1783 in St. Petersburg
Einer der größtenMathematiker allerZeiten
Primzahlen für Einsteiger 49
Eulers Antwort (genial)
F(5) = 232 + 1 = 4 294 967 297,
F(5) = 4 294 967 297 = 641 ∙ 6700417
Weitere Fermatsche Primzahlen sind
nicht bekannt.
Primzahlen für Einsteiger 50
Rekorde
• F(11): Größte Fermatzahl mit vollständiger Faktorisierung
• F(24): Kleinste Fermatzahl, von der nicht bekannt ist, ob sie Primzahl ist oder nicht
• F(303088): Größte Fermatzahl, für die „nicht prim“ bewiesen wurde (Ein Faktor ist 3 x 2303093 + 1, Young 1998)
Primzahlen für Einsteiger 51
Eine Formel für alle Primzahlen
• Hardy und Wrights Formel
• n Zweien bei f(n) • ω = 1.9287800…• Zur Berechnung von ω
benötigt man alle Primzahlen
• Nicht sehr praktisch!• Es gibt weitere solcher
Formeln
Primzahlen für Einsteiger 52
Godfrey Harold Hardy
• Geb.: 1877 in Cranleigh
• Gest.: 1947 in Cambridge
• Einer der bedeutendsten Zahlentheoretiker des 20. Jahrhunderts
Primzahlen für Einsteiger 53
Literaturtipps
• Harald Scheid: Zahlentheorie
Spektrum Verlag 2003, 49,95 €
• Paolo Ribenboim: My Numbers, my Friends
Springer Verlag 2000, 39,95 $
• Paolo Ribenboim: The New Book of Prime Number Records
Springer Verlag 1996, 40,41€
Primzahlen für Einsteiger 54
Offene Fragen
• Wie hoch ist der Aufwand, eine Zahl zu faktorisieren?
• Wie stellt man fest, ob eine Zahl Primzahl ist?
• Wie findet man große Primzahlen?
• Einfache Formeln für unendlich viele Primzahlen
Primzahlen für Einsteiger 55
Weitere Veranstaltungen
• Mathe für Alle in Eppelborn:
Am 15.12.2003 im Rathaus
• Schrecken der Unendlichkeit I:
Am 27.11.2003 um 19.30 in Tholey.
Ort: Sitzungsaal im Rathaus