Primzahlen für Einsteiger1 Alte und neue Ergebnisse.

transcript

Primzahlen für Einsteiger 1

Primzahlen für Einsteiger

Alte und neue Ergebnisse

Referenzen: Meine Hochschule

Mein Fachbereich

• 500 Studierende

• 2 Sekretärinnen

• 6 Assistenten

• 3 Professorinnen, 12 Professoren

• Viele Lehrbeauftragte aus der Wirtschaft

Referenzen: Meine Gemeinde

• Fritz-Herrmann Lutz,

bewundernswerter Kommunikator, aber:

• Er hat noch nie eine Matheveranstaltung in Eppelborn besucht. Mathephobie?

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

Haben Sie eine Lieblingsprimzahl?

Meine Lieblingsprimzahl: 1742 ist keine Primzahl!

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)

Die Geographie der Mathematik

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!

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

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

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.

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 ?

Teilbarkeitseigenschaften

Die Umkehrung ist falsch:

Aus a │ b ∙ c folgt nicht: a │b oder a │c

Gegenbeispiel:

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)

Einige Primzahlen

Die ersten Primzahlen:

2, 3, 5, 7, 11, 13, 17, …. (?)

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

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

Euklid

Euklid:

Geb. 325 v. Chr.

Gst: 265 v. Chr. in

Alexandria

Der Mathematiker des

Altertums

Wie zerlegt man in Primfaktoren?

Beispiele:

Z = 42Z = 182Z = 3553Z = 135014

Dies ist nicht einfach!

Warum Primzahlen wichtig sind(Praxis)

Große Primzahlen für

asymmetrische Verfahren der Kryptologie

Es ist schwierig, die Primfaktorzerlegung großer Zahlen herzustellen.

Wie viele Primzahlen gibt es?

Euklid:

Es gibt unendlich

viele Primzahlen

Schönheit in der Mathematik

Paul Erdös Idee:

Proofs from the Book

Eine Sammlung

schöner Beweise

Proofs from the Book

Start:

6 Beweise, dass es unendlich viele Primzahlen gibt

Euklids Beweis

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!

Beispiele:

p1 = 3, p2 = 5, p3 = 7

E = 3∙5∙7 + 1 = 106: Keine neue Primzahl!

E enthält eine neue Primzahl als Faktor, hier die Zahl 2. Keine der Zahlen 3,5,7 teilt 106

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.

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

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)

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:

π(x) = Anzahl der Primzahlen x

3, 29}| = 10

π(100) = 25; π(1000) = 168;

π(1 000 000) = 78 498

Der Primzahlensatz (1896)

Für große x: xπ(x)

Nicolas de la Vallee-

Poussin

(1866 – 1962)

Jacques Salomon

Hadamard

(1865 – 1962)

Wie viele Primzahlen bis 10300?

300 300300 297

10 10π(10 ) > 10

ln(10 ) 300 ln(10)

Bestimmung von Primzahlen

Verschiedene Vorgehensweisen:

– Siebe (Eratosthenes, quadratische Siebe)– Formeln (traurig und schön)– Monte-Carlo-Methoden für große Primzahlen

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

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

Mersenne Zahlen

Marin Mersenne

Geb.: 1588 in OizeGest.: 1648 in Paris

Mathematiker undPhysiker,suchte Formeln für Primzahlen

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

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)

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)

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

Fermat-Zahlen

Pierre der Fermat

Geb.: 1601 in

Beaumont de Lomagne

Gest.: 1665 in Castres

Genialer

Zahlentheoretiker

Fermat-Zahlen

n(2 )F(n) = 2 1Fermats Vermutung:

Alle Zahlen dieser Form sind Primzahlen.

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!

Eulers Antwort

Leonhard Euler

Geb.: 1707 in BaselGest.: 1783 in St. Petersburg

Einer der größtenMathematiker allerZeiten

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.

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)

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

Godfrey Harold Hardy

• Geb.: 1877 in Cranleigh

• Gest.: 1947 in Cambridge

• Einer der bedeutendsten Zahlentheoretiker des 20. Jahrhunderts

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€

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

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

Primzahlen für Einsteiger1 Alte und neue Ergebnisse.

Documents