Primzahlen -- von Euklid bis heute - Fachbereich Mathematik · Einleitung Primzahlen...

EinleitungPrimzahlen

PrimzahlverteilungDie Riemannsche Vermutung

Primzahlen – von Euklid bis heute

Jan H. Bruinier

Mathematisches InstitutUniversitat zu Koln

[email protected]

5. November 2004

Jan H. Bruinier Primzahlen – von Euklid bis heute



Pythagoras von Samos (ca. 570-480 v. Chr.)




Euklid von Alexandria (ca. 325-265 v. Chr.)




PrimzahlenTeilbarkeitSatz von EuklidBedeutung von Primzahlen

PrimzahlverteilungDie PrimzahlanzahlfunktionDer Primzahlsatz

Die Riemannsche VermutungDie Riemannsche ZetafunktionDer FehlertermDie Teilersummenvermutung




TeilbarkeitSatz von EuklidBedeutung von Primzahlen

Teilbarkeit

I Naturliche Zahlen: N = {1, 2, 3, . . . }.I Ganze Zahlen: Z = {0,±1,±2,±3, . . . }.

DefinitionEine naturliche Zahl a ∈ N teilt b ∈ Z,falls es ein c ∈ Z gibt mit ac = b.Mann sagt dann “a ist ein Teiler von b” und schreibt a | b.

Beispiel3 teilt 15, denn 3 · 5 = 15.





Teilbarkeit








Teilbarkeit








Grundlegende Eigenschaften

1. 1 | b und b | b fur alle b ∈ N.

2. a | b =⇒ 1 ≤ a ≤ |b|.3. a | 1 =⇒ a = 1.

4. a | b und a | b′ =⇒ a | (b ± b′).

5. a | b und b | c =⇒ a | c .

Folgerung (aus 1.)Jede naturliche Zahl n > 1 besitzt mindestens 2 Teiler.







2. a | b =⇒ 1 ≤ a ≤ |b|.3. a | 1 =⇒ a = 1.

4. a | b und a | b′ =⇒ a | (b ± b′).

5. a | b und b | c =⇒ a | c .








2. a | b =⇒ 1 ≤ a ≤ |b|.3. a | 1 =⇒ a = 1.

4. a | b und a | b′ =⇒ a | (b ± b′).

5. a | b und b | c =⇒ a | c .








2. a | b =⇒ 1 ≤ a ≤ |b|.3. a | 1 =⇒ a = 1.

4. a | b und a | b′ =⇒ a | (b ± b′).

5. a | b und b | c =⇒ a | c .






Primzahlen

DefinitionEine naturliche Zahl n > 1 heißt Primzahl,falls n genau 2 Teiler besitzt.

BeispielDie ersten Primzahlen sind: 2, 3, 5, 7, 11, 13, 17, . . . .





Primzahlen

DefinitionEine naturliche Zahl n > 1 heißt Primzahl,falls n genau 2 Teiler besitzt.

BeispielDie ersten Primzahlen sind: 2, 3, 5, 7, 11, 13, 17, . . . .





Mehr Primzahlen

2 3 5 7 11 13 17 19 23 2931 37 41 43 47 53 59 61 67 7173 79 83 89 97 101 103 107 109 113127 131 137 139 149 151 157 163 167 173179 181 191 193 197 199 211 223 227 229233 239 241 251 257 263 269 271 277 281283 293 307 311 313 317 331 337 347 349353 359 367 373 379 383 389 397 401 409419 421 431 433 439 443 449 457 461 463467 479 487 491 499 503 509 521 523 541547 557 563 569 571 577 587 593 599 601607 613 617 619 631 641 643 647 653 659661 673 677 683 691 701 709 719 727 733739 743 751 757 761 769 773 787 797 809811 821 823 827 829 839 853 857 859 863877 881 883 887 907 911 919 929 937 941947 953 967 971 977 983 991 997 1009 1013

\begin{comment}

1019 1021 1031 1033 1039 1049 1051 1061 1063 10691087 1091 1093 1097 1103 1109 1117 1123 1129 11511153 1163 1171 1181 1187 1193 1201 1213 1217 12231229 1231 1237 1249 1259 1277 1279 1283 1289 12911297 1301 1303 1307 1319 1321 1327 1361 1367 13731381 1399 1409 1423 1427 1429 1433 1439 1447 14511453 1459 1471 1481 1483 1487 1489 1493 1499 15111523 1531 1543 1549 1553 1559 1567 1571 1579 15831597 1601 1607 1609 1613 1619 1621 1627 1637 16571663 1667 1669 1693 1697 1699 1709 1721 1723 17331741 1747 1753 1759 1777 1783 1787 1789 1801 18111823 1831 1847 1861 1867 1871 1873 1877 1879 18891901 1907 1913 1931 1933 1949 1951 1973 1979 19871993 1997 1999 2003 2011 2017 2027 2029 2039 20532063 2069 2081 2083 2087 2089 2099 2111 2113 21292131 2137 2141 2143 2153 2161 2179 2203 2207 22132221 2237 2239 2243 2251 2267 2269 2273 2281 22872293 2297 2309 2311 2333 2339 2341 2347 2351 23572371 2377 2381 2383 2389 2393 2399 2411 2417 2423\end{comment}





Der Satz von Euklid

FrageGibt es unendlich viele Primzahlen?

LemmaSei n > 1 eine naturliche Zahl und

t(n) = min{a ∈ N; a > 1 und a | n}

“der kleinste nichttriviale Teiler von n”.Dann ist t(n) eine Primzahl.

FolgerungJede naturliche Zahl n > 1 ist durch eine Primzahl teilbar.





Der Satz von Euklid



t(n) = min{a ∈ N; a > 1 und a | n}







Der Satz von Euklid



t(n) = min{a ∈ N; a > 1 und a | n}







Der Satz von Euklid II

Satz (Euklid, ca. 300 v. Chr.)Es gibt unendlich viele Primzahlen.

Beweis.Angenommen es gibt nur endlich viele Primzahlen.Sei N ihr Produkt.Es gilt N + 1 > 1.Sei p eine Primzahl, die N + 1 teilt, z.B. p = t(N + 1).Weil p auch N teilt, folgt p|1, also ein Widerspruch.







Beweis.Angenommen es gibt nur endlich viele Primzahlen.

Sei N ihr Produkt.Es gilt N + 1 > 1.Sei p eine Primzahl, die N + 1 teilt, z.B. p = t(N + 1).Weil p auch N teilt, folgt p|1, also ein Widerspruch.







Beweis.Angenommen es gibt nur endlich viele Primzahlen.Sei N ihr Produkt.Es gilt N + 1 > 1.

Sei p eine Primzahl, die N + 1 teilt, z.B. p = t(N + 1).Weil p auch N teilt, folgt p|1, also ein Widerspruch.







Beweis.Angenommen es gibt nur endlich viele Primzahlen.Sei N ihr Produkt.Es gilt N + 1 > 1.Sei p eine Primzahl, die N + 1 teilt, z.B. p = t(N + 1).

Weil p auch N teilt, folgt p|1, also ein Widerspruch.







Beweis.Angenommen es gibt nur endlich viele Primzahlen.Sei N ihr Produkt.Es gilt N + 1 > 1.Sei p eine Primzahl, die N + 1 teilt, z.B. p = t(N + 1).Weil p auch N teilt, folgt p|1, also ein Widerspruch.





Warum interessiert man sich fur Primzahlen?

I Primzahlen sind die “Atome” der naturlichen Zahlen.

I Losung von Polynom-Gleichungen mit Koeffizienten in Z.

I Anwendungen in der Kryptographie.









Satz (Euklid)Jede naturliche Zahl n > 1 kann in eindeutiger Weise als Produktvon Primzahlen geschrieben werden.









n Zerlegung n Zerlegung n Zerlegung

2 2 10 2 · 5 18 2 · 3 · 33 3 11 11 19 194 2 · 2 12 2 · 2 · 3 20 2 · 2 · 55 5 13 13 21 3 · 76 2 · 3 14 2 · 7 22 2 · 117 7 15 3 · 5 23 238 2 · 2 · 2 16 2 · 2 · 2 · 2 24 2 · 2 · 2 · 39 3 · 3 17 17 25 5 · 5

















I Beispiel: Elliptische Kurve

E : y2 = x3 + ax + b.

I Betrachte E (Fp), die Reduktion modulo p.

I Birch-Swinnerton-Dyer-Vermutung sagt tiefliegendeZusammenhange voraus mit E (Q).

















I Multiplikation zweier Primzahlen ist “einfach”.

I Faktorisierung von ganzen Zahlen ist “hart”.




Die PrimzahlanzahlfunktionDer Primzahlsatz

Die Primzahlanzahlfunktion π(x)

FrageWie sind die Primzahlen in den naturlichen Zahlen verteilt?

Primzahlen

Betrachte dazu die Primzahlanzahlfunktion

π(x) = #{p ∈ N prim; p ≤ x}.

Tabelle:

x 1 2 3 4 5 6 7 8 9 10 11 . . .

π(x) 0 1 2 2 3 3 4 4 4 4 5 . . .







Primzahlen


π(x) = #{p ∈ N prim; p ≤ x}.

Tabelle:

x 1 2 3 4 5 6 7 8 9 10 11 . . .

π(x) 0 1 2 2 3 3 4 4 4 4 5 . . .







Primzahlen


π(x) = #{p ∈ N prim; p ≤ x}.

Tabelle:

x 1 2 3 4 5 6 7 8 9 10 11 . . .

π(x) 0 1 2 2 3 3 4 4 4 4 5 . . .





Der Graph von π(x)

pi(x)

0

1

2

3

4

2 4 6 8 10x





Der Graph von π(x)

pi(x)

0

20

40

60

80

100

120

140

160

200 400 600 800 1000x





Der Graph von π(x)

pi(x)

0

2000

4000

6000

8000

20000 40000 60000 80000 100000x





Approximation von π(x)

FrageLaßt sich π(x) durch eine “einfache” Funktion approximieren?

DefinitionZwei Funktionen f (x), g(x) heißen asymptotisch gleich, falls

limx→∞

f (x)

g(x)= 1.

Schreibe f (x) ∼ g(x), x →∞.

Beispiel

I x ∼ x + 1,

I x ∼ x +√

x .








limx→∞

f (x)

g(x)= 1.


Beispiel

I x ∼ x + 1,

I x ∼ x +√

x .








limx→∞

f (x)

g(x)= 1.


Beispiel

I x ∼ x + 1,

I x ∼ x +√

x .





Die Vermutung von Gauss und Legendre

Vermutung (Gauss 1792, Legendre 1798)

π(x) ∼ x

log(x), x →∞.

I Gauss erkannte bereits, daß

π(x) ∼ Li(x), x →∞,

eine bessere Approximation sein sollte.

I Dabei ist Li(x) =∫ x2

dtlog(t) der Integrallogarithmus.

I Beachte Li(x) ∼ xlog(x) .







π(x) ∼ x

log(x), x →∞.


π(x) ∼ Li(x), x →∞,











π(x) ∼ x

log(x), x →∞.


π(x) ∼ Li(x), x →∞,









Gute der Approximation

x π(x) [Li(x)] [Li(x)]/π(x)− 1

10 4 5 0.25102 25 29 0.16103 168 176 0.048104 1 229 1 245 0.013105 9 592 9 628 3.8 · 10−3

106 78 498 78 626 1.6 · 10−3

108 5 761 455 5 762 208 1.3 · 10−4

1010 455 052 511 455 055 613 6.8 · 10−6

1012 37 607 912 018 37 607 950 279 1.0 · 10−6





Approximationen von π(x)

pi(x)x/log(x)Li(x)

Approximationen von pi(x)

0

20

40

60

80

100

120

140

160

180

200 400 600 800 1000x





Approximationen von π(x)

pi(x)x/log(x)Li(x)

Approximationen von pi(x)

0

2000

4000

6000

8000

20000 40000 60000 80000 100000x





Der Primzahlsatz

I Tschebyscheff (1850): Fur große x gilt

0.9212 · x

log(x)< π(x) < 1.1056 · x

log(x).

I Hadamard und de la Vallee-Poussin (1896) bewiesen denPrimzahlsatz:

π(x) ∼ x

log(x), x →∞.

Folgerungen

I Ungefahr 1log(x) aller naturlichen Zahlen ≤ x sind prim.

I Die k-te Primzahl hat ungefahr die Große k log(k).





Der Primzahlsatz


0.9212 · x

log(x)< π(x) < 1.1056 · x

log(x).


π(x) ∼ x

log(x), x →∞.

Folgerungen







Der Primzahlsatz


0.9212 · x

log(x)< π(x) < 1.1056 · x

log(x).


π(x) ∼ x

log(x), x →∞.

Folgerungen







Der Primzahlsatz


0.9212 · x

log(x)< π(x) < 1.1056 · x

log(x).


π(x) ∼ x

log(x), x →∞.

Folgerungen






Die Riemannsche ZetafunktionDer FehlertermDie Teilersummenvermutung

Bernhard Riemann (1826-1866)





Die Riemannsche Zetafunktion

I Der Beweis des Primzahlsatzes benutzt dieRiemannsche Zetafunktion

ζ(s) =∞∑

n=1

1

ns(s ∈ C, Re(s) > 1).

I Hat Fortsetzung auf ganz C.

I Pol bei s = 1 (⇔ es gibt unendlich viele Primzahlen).

I Eulerproduktdarstellung ⇒ ζ(s) 6= 0 fur Re(s) > 1.

I Primzahlsatz ⇔ ζ(s) 6= 0 fur Re(s) = 1.







ζ(s) =∞∑

n=1

1

ns(s ∈ C, Re(s) > 1).











ζ(s) =∞∑

n=1

1

ns(s ∈ C, Re(s) > 1).











ζ(s) =∞∑

n=1

1

ns(s ∈ C, Re(s) > 1).











ζ(s) =∞∑

n=1

1

ns(s ∈ C, Re(s) > 1).









Die Riemannsche Zetafunktion ζ(s) =∑∞

n=11ns

–1

0

1

2

3

4

Re(s)

–20

–10

0

10

20

Im(s)

0

1

2

3

4





Gute der Approximation von π(x)

FrageWas ist der Fehler der Approximation π(x) ∼ Li(x)?

Tabelle

Vermutung (FV)

π(x) = Li(x) + O(√

x log x), x →∞.

Satz (Koch 1901)Die Vermutung (FV) ist aquivalent zur Riemannschen Vermutung.







Tabelle

Vermutung (FV)

π(x) = Li(x) + O(√

x log x), x →∞.








Tabelle

Vermutung (FV)

π(x) = Li(x) + O(√

x log x), x →∞.






Die Riemannsche Vermutung

Vermutung (Riemann 1859)Fur alle s ∈ C mit Re(s) > 1/2 ist ζ(s) 6= 0.

Genauer gilt sogar:

SatzFur α ≥ 1/2 sind aquivalent:

(i) π(x) = Li(x) + O(xα log x).

(ii) ζ(s) 6= 0 fur alle s ∈ C mit Re(s) > α.

I Diese Aussage ist gegenwartig fur kein α < 1 bekannt!

I Man weiß immerhin, daß π(x) = Li(x) + O(x/ log2 x).

I Auf Re(s) = 1/2 liegen unendlich viele Nullstellen von ζ(s)(Hardy, 1914).







Genauer gilt sogar:













Genauer gilt sogar:













Genauer gilt sogar:













Genauer gilt sogar:











FAQ’s

FrageWarum sollte die Riemannsche Vermutung stimmen?

I Die ersten 1013 Nullstellen von ζ(s) liegen auf Re(s) = 1/2(Gourdon-Demichel, 2004).

FrageIst die Riemannsche Vermutung ein schwieriges Problem?

I Ja!

I Sie gehort zu den Millionen-Dollar-Problemen desClay Mathematics Institute.

I Dennoch laßt sie sich vollkommen elementar formulieren.





FAQ’s




I Ja!







FAQ’s




I Ja!







FAQ’s




I Ja!







FAQ’s




I Ja!







FAQ’s




I Ja!







Die Teilersummenvermutung

Fur n ∈ N sei

I σ(n) =∑

d |n d die Summe der Teiler von n,

I h(n) =∑n

k=11k die n-te harmonische Zahl.

Satz (Lagarias, 2000)RV ist aquivalent zur folgenden Teilersummenvermutung.

Vermutung (Lagarias, 2000)

σ(n) ≤ h(n) + exp(h(n)) log(h(n)), fur alle n ∈ N.






Fur n ∈ N sei

I σ(n) =∑


I h(n) =∑n










Fur n ∈ N sei

I σ(n) =∑


I h(n) =∑n









Die Teilersummenvermutung fur kleine n

n σ(n) h(n) + eh(n) log(h(n))

1 1 12 3 3.31716854. . .3 4 5.62453152. . .4 7 7.97798290. . .5 6 10.38226769. . .6 12 12.83417872. . .7 8 15.32927365. . .8 15 17.86331817. . .9 13 20.43258568. . .

10 18 23.03386680. . .11 12 25.66440756. . .12 28 28.32183725. . .





Graphische Darstellung der Ungleichung

0

50

100

150

200

250

300

20 40 60 80 100

n





Graphische Darstellung der Ungleichung

0

500

1000

1500

2000

2500

3000

3500

200 400 600 800 1000

n


Mersenne-PrimzahlenZusammenfassung

Mersenne-Primzahlen

FrageWas ist die großte bekannte Primzahl?

I Die Mersenne-Primzahl 224 036 583 − 1.

I Entdeckt am 15.5.2004 durch GIMPS (www.mersenne.org).

I Sie hat 7 235 733 Dezimalstellen.

I Marin Mersenne (1588-1648) studiertePrimzahlen der Form 2n − 1.

I 2n − 1 prim =⇒ n prim.

I Beispiel: 3, 7, 31, 127.

FrageGibt es unendlich viele Mersenne-Primzahlen?



Mersenne-Primzahlen







I Beispiel: 3, 7, 31, 127.




Mersenne-Primzahlen







I Beispiel: 3, 7, 31, 127.




Mersenne-Primzahlen







I Beispiel: 3, 7, 31, 127.




Mersenne-Primzahlen







I Beispiel: 3, 7, 31, 127.




Mersenne-Primzahlen







I Beispiel: 3, 7, 31, 127.




Zusammenfassung

I Primzahlen werden seit den alten Griechen intensiv studiert.

I Sie sind die “Atome” der naturlichen Zahlen.

I Informationen zur Primzahlverteilung sind in derRiemannschen Zetafunktion codiert.

I Ihr Studium fuhrt zu fundamentalen offenen Fragen derZahlentheorie.



Zusammenfassung







Zusammenfassung







Zusammenfassung






Date post:	06-Sep-2019
Category:	Documents
Upload:	others
View:	13 times
Download:	1 times

Primzahlen -- von Euklid bis heute - Fachbereich Mathematik · Einleitung Primzahlen...

Documents