C1ph4: Die Seite wurde neu angelegt: „{{Zeichen| $\mathbb P$ }} Eine '''Primzahl''' (wörtlich „erste Zahl“ oder eher „Zahl erster Klasse“) ist eine natürliche Zahl, die grö…“

2017-11-17T20:48:43Z

Die Seite wurde neu angelegt: „{{Zeichen|<math>\mathbb P</math>}} Eine '''Primzahl''' (wörtlich „erste Zahl“ oder eher „Zahl erster Klasse“) ist eine natürliche Zahl, die grö…“

Neue Seite

{{Zeichen|<math>\mathbb P</math>}}

Eine '''Primzahl''' (wörtlich „erste Zahl“ oder eher „Zahl erster Klasse“) ist eine [[natürliche Zahl]], die größer als 1 und ausschließlich durch sich selbst und durch 1 [[Teilbarkeit|teilbar]] ist. Die Primzahlen sind damit innerhalb der [[Menge (Mathematik)|Menge]] <math>\N</math> der natürlichen Zahlen dadurch [[Merkmal|charakterisiert]], dass jede von ihnen genau zwei natürliche Zahlen als [[Teilermenge|Teiler]] hat.<ref>Armin Leutbecher: ''Zahlentheorie: Eine Einführung in die Algebra.'' Springer, 1996, ISBN 3-540-58791-8, S. 18, {{Google Buch|BuchID=DlgTIfMLdqMC|Seite=18|Hervorhebung=Definition Primzahl}}.</ref> Die aus allen Primzahlen bestehende [[Teilmenge]] von <math>\N</math> wird in der Regel mit dem [[Liste mathematischer Symbole|Symbol]] <math>\mathbb P</math> bezeichnet.

Unmittelbar mit <math>\mathbb P</math> verknüpft ist die [[Folge (Mathematik)|Folge]] <math>\left(p_n \right)_{n \in \N}</math> der nach ihrer Größe geordneten Primzahlen, die man auch kurz die ''Primzahlfolge'' nennt. Es ist demnach
:<math>\N \supsetneq \mathbb P = \{ p_n \mid n \in \N \}</math>

mit

: <math>\left(p_n \right)_{n \in \N} = \left( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, \dotsc \right)</math> ({{OEIS|A000040}}).

[[Datei:Prime rectangles.svg|mini|Die Zahl 12 ist keine Primzahl, die Zahl 11 hingegen schon.]]

Eine natürliche Zahl ist ''prim,'' wenn sie eine Primzahl ist. Andernfalls ist sie ''[[Zusammengesetzte Zahl|zusammengesetzt]].'' Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.

Das Wort „Primzahl“ kommt aus dem Lateinischen ''(numerus primus)'' und bedeutet „die erste Zahl“. Die Bedeutung der Primzahlen <math>\mathbb P</math> für viele Bereiche der [[Mathematik]] beruht auf drei Folgerungen aus dieser Definition:

* ''Existenz und Eindeutigkeit der [[Primfaktorzerlegung]]:'' Jede natürliche Zahl, die größer als 1 und selbst keine Primzahl ist, lässt sich als Produkt von mindestens zwei Primzahlen schreiben. Diese Produktdarstellung ist bis auf die Reihenfolge der Faktoren eindeutig. Zum Beweis dient das
* ''[[Lemma von Euklid]]:'' Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist mindestens einer der Faktoren durch sie teilbar.
* Primzahlen lassen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen.

Diese Eigenschaften werden in der [[Algebra]] für [[#Verallgemeinerung|Verallgemeinerungen des Primzahlbegriffs]] genutzt.

Schon im [[Antikes Griechenland|antiken Griechenland]] interessierte man sich für die Primzahlen und entdeckte einige ihrer Eigenschaften. Obwohl Primzahlen seit damals stets einen großen Reiz auf die Menschen ausübten, sind viele die Primzahlen betreffenden Fragen bis heute [[Ungelöste Probleme der Mathematik|ungeklärt]], darunter solche, die mehr als hundert Jahre alt und leicht verständlich formulierbar sind. Dazu gehören die [[Goldbachsche Vermutung]], wonach außer 2 jede gerade Zahl als Summe zweier Primzahlen darstellbar ist, und die Vermutung, dass es unendlich viele [[Primzahlzwilling]]e gibt (das sind Paare von Primzahlen, deren Differenz gleich 2 ist).

Über 2000 Jahre lang konnte man keinen praktischen Nutzen aus dem Wissen über die Primzahlen ziehen. Dies änderte sich erst mit dem Aufkommen elektronischer Rechenmaschinen, bei denen die Primzahlen beispielsweise in der [[Kryptographie]] eine zentrale Rolle spielen.

== Primfaktorzerlegung ==
{{Hauptartikel|Primfaktorzerlegung}}
Es gilt der [[Fundamentalsatz der Arithmetik]]: Jede [[Positive Zahl|positive]] [[ganze Zahl]] lässt sich als (ggf. [[Leeres Produkt|leeres]]) [[Produkt (Mathematik)|Produkt]] von Primzahlen darstellen, und diese Darstellung ist bis auf die Reihenfolge der Primzahlen eindeutig. Diese Primzahlen nennt man die ''Primfaktoren'' der Zahl. Man kennt bisher keine Methode, um die Primfaktorzerlegung einer beliebigen gegebenen Zahl effizient zu bestimmen, d. h. in einer Zeit, die [[Polynomialzeit|polynomiell]] mit der Länge der Zahl wächst. Die ''Faktorisierungsannahme'' besagt, dass es eine solche Methode auch nicht gibt. Man versucht, die Zeit mit geeigneten [[Faktorisierungsverfahren]] zu minimieren.

Aufgrund dieses Satzes, also dass sich jede natürliche Zahl größer 0 durch [[Multiplikation]] von Primzahlen eindeutig darstellen lässt, nehmen die Primzahlen eine besondere atomare Stellung in der Mathematik ein. [[Alexander K. Dewdney]] bezeichnete diese als den [[Chemisches Element|Elementen]] der [[Chemie]] weitgehend ähnlich.

== Eigenschaften von Primzahlen ==

Mit Ausnahme der Zahl 2 sind alle Primzahlen <math>p</math> ungerade, denn alle größeren geraden Zahlen lassen sich außer durch sich selbst und 1 auch noch (mindestens) durch 2 teilen. Damit hat jede Primzahl außer 2 die Form <math>2k+1</math> mit einer natürlichen Zahl <math>k</math>.

Jede Primzahl <math>p \neq 2</math> lässt sich einer der beiden Klassen „Primzahl der Form <math>4k+1</math>“ oder „Primzahl der Form <math>4k+3</math>“ zuordnen, wobei <math>k</math> eine natürliche Zahl ist. Darüber hinaus hat jede Primzahl <math>p > 3</math> die Form <math>p = 6k+1</math> oder <math>p = 6k-1</math>, wobei <math>k</math> eine natürliche Zahl ist. Nach dem [[Dirichletscher Primzahlsatz|dirichletschen Primzahlsatz]] gibt es in jeder dieser vier Klassen unendlich viele Primzahlen.

Jede natürliche Zahl der Form <math>4m+3</math> mit einer nichtnegativen ganzen Zahl <math>m</math> enthält mindestens einen Primfaktor der Form <math>4k+3</math>. Eine entsprechende Aussage über Zahlen der Form <math>4m+1</math> oder Primfaktoren der Form <math>4k+1</math> ist nicht möglich.

Eine Primzahl <math>p>2</math> lässt sich genau dann in der Form <math>a^2+b^2</math> mit ganzen Zahlen <math>a,b</math> schreiben, wenn <math>p</math> die Form <math>4k+1</math> hat. In diesem Fall ist die Darstellung im Wesentlichen eindeutig, d. h. bis auf Reihenfolge und [[Vorzeichen (Zahl)|Vorzeichen]] von <math>a,b</math>. Diese Darstellung entspricht der Primfaktorzerlegung

: <math>p=(a+b\mathrm i)(a-b\mathrm i)</math>

im [[Ring (Algebra)|Ring]] der ganzen [[Gaußsche Zahl|gaußschen Zahlen]].

Die Zahl −1 ist ein [[quadratischer Rest]] modulo jeder Primzahl der Form <math>4k+1</math> und quadratischer Nichtrest modulo jeder Primzahl der Form <math>4k+3</math>.

=== Der kleine Satz von Fermat ===

Es sei <math>p</math> eine Primzahl. Für jede ganze Zahl <math>a</math>, die nicht durch <math>p</math> teilbar ist, gilt (für die Notation siehe [[Kongruenz (Zahlentheorie)|Kongruenz]]):

: <math>a^{p-1} \equiv 1 \mod p.</math>

Für nicht durch <math>p</math> teilbare Zahlen <math>a</math> ist die folgende Formulierung äquivalent:

: <math>a^p\equiv a\mod p.</math>

Es gibt Zahlen, die keine Primzahlen sind, sich aber dennoch zu einer Basis <math>a</math> wie Primzahlen verhalten und somit den [[Kleiner fermatscher Satz|kleinen Satz von Fermat]] erfüllen. Solche zusammengesetzten Zahlen nennt man [[fermatsche Pseudoprimzahl]]en zur Basis <math>a</math>. Eine fermatsche Pseudoprimzahl ''n,'' die pseudoprim bezüglich ''aller'' zu ihr teilerfremden Basen <math>a</math> ist, nennt man [[Carmichael-Zahl]].

In diesem Zusammenhang zeigt sich die Problematik fermatscher Pseudoprimzahlen: sie werden von einem [[Primzahltest]], der den kleinen Satz von Fermat nutzt ([[Fermatscher Primzahltest]]), fälschlicherweise für Primzahlen gehalten. Wenn allerdings ein Verschlüsselungsverfahren wie [[RSA-Kryptosystem|RSA]] eine zusammengesetzte Zahl statt einer Primzahl verwendet, ist die Verschlüsselung nicht mehr sicher. Deshalb müssen bei solchen Verfahren bessere Primzahltests verwendet werden.

=== Euler und das Legendre-Symbol ===

Eine einfache Folge aus dem kleinen Satz von Fermat ist die folgende Aussage: Für jede ungerade Primzahl <math>p</math> und jede ganze Zahl <math>a</math>, die nicht durch <math>p</math> teilbar ist, gilt entweder

: <math>a^{\frac{p-1}{2}} \equiv 1 \mod p</math>

oder

: <math>a^{\frac{p-1}{2}} \equiv -1 \mod p.</math>

Man kann zeigen, dass der erste Fall genau dann eintritt, wenn es eine Quadratzahl <math>m^2</math> gibt, die kongruent zu <math>a</math> modulo <math>p</math> ist, ''siehe'' [[Legendre-Symbol]].

=== Binomialkoeffizient ===

Für Primzahlen <math>p</math> und <math>1\leq k < p</math> gilt

: <math>p\,\Big|{p\choose k};</math>

zusammen mit dem [[Binomischer Satz|binomischen Satz]] folgt daraus

: <math>(a+b)^p\equiv a^p+b^p\mod p.</math>

Für ganze Zahlen <math>a, b</math> folgt diese Aussage auch direkt aus dem kleinen fermatschen Satz, aber sie ist beispielsweise auch für Polynome mit ganzzahligen Koeffizienten anwendbar; im allgemeinen Kontext entspricht sie der Tatsache, dass die Abbildung <math>x\mapsto x^p</math> in Ringen der [[Charakteristik (Algebra)|Charakteristik]] <math>p</math> ein Homomorphismus ist, der sogenannte [[Frobenius-Homomorphismus]].

Aus dem [[Satz von Wilson]] (''p'' ist genau dann eine Primzahl, wenn <math>(p-1)! \equiv -1 \pmod p</math> ist) folgt, dass für jede Primzahl ''p'' und jede natürliche Zahl ''n'' die Kongruenz

: <math>{{np-1}\choose{p-1}} \equiv 1 \pmod{p}</math>

erfüllt ist.

[[Charles Babbage]] bewies 1819, dass für jede Primzahl ''p'' > 2 diese Kongruenz gilt:

: <math>{{2p-1}\choose{p-1}} \equiv 1 \pmod{p^2}</math>

Der Mathematiker [[Joseph Wolstenholme]] (1829–1891) bewies dann 1862, dass für jede Primzahl ''p'' > 3 die folgende Kongruenz gilt:

: <math>{{2p-1}\choose{p-1}} \equiv 1 \pmod{p^3}</math>

=== Giuga ===

Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl ''p'' gilt:

: <math>1^{p-1} + 2^{p-1} + \dotsb + (p-1)^{p-1} \equiv -1 \pmod{p}</math>

Beispiel <math>p = 5</math>:

: <math>1^4 + 2^4 + 3^4 + 4^4 = 1 + 16 + 81 + 256 = 354 = 71\cdot 5 - 1\equiv -1 \pmod{5}</math>

[[Giuseppe Giuga]] vermutete, dass auch die umgekehrte Schlussrichtung gilt, dass also eine Zahl mit dieser Eigenschaft stets prim ist. Es ist nicht geklärt, ob diese Vermutung richtig ist. Bekannt ist aber, dass ein Gegenbeispiel mehr als 10.000 Dezimalstellen haben müsste. Im Zusammenhang mit [[Giugas Vermutung]] werden die [[Giuga-Zahl]]en untersucht.

=== Lineare Rekursionen ===

Den kleinen fermatschen Satz kann man auch in der Form lesen: In der Folge <math>a^n-a</math> ist das <math>p</math>-te Folgenglied für eine Primzahl <math>p</math> stets durch <math>p</math> teilbar. Ähnliche Eigenschaften besitzen auch andere Folgen von exponentiellem Charakter, wie die [[Lucas-Folge]] (<math>p\mid L_p-1</math>) und die [[Perrin-Folge]] (<math>p\mid P_p</math>). Für andere lineare Rekursionen gelten analoge, aber kompliziertere Aussagen, beispielsweise für die [[Fibonacci-Folge]] <math>(f_n)_{n=0, 1, 2, \dotsc} = 0, 1, 1, 2, 3, 5, \dotsc</math>: Ist <math>p</math> eine Primzahl, so ist <math>f_p-\Big(\frac p5\Big)</math> durch <math>p</math> teilbar; dabei ist

: <math>\Big(\frac p5\Big)=\begin{cases}1&p\equiv 1,4\mod 5\\-1&p\equiv2,3\mod 5\\0&p=5\end{cases}</math>

das [[Legendre-Symbol]].

=== Divergenz der Summe der Kehrwerte ===

{{Hauptartikel|Satz von Euler (Primzahlen)}}

Die [[Reihe (Mathematik)|Reihe]] der Kehrwerte der Primzahlen ist divergent. Somit gilt:

: <math>\sum_{i=1}^\infty \frac{1}{p_i} = \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \dotsb = \infty</math>.

Das ist gleichbedeutend mit der Aussage, dass die durch <math>\textstyle a_n = \sum_{i=1}^{n} \frac{1}{p_i}</math> definierte [[Folge (Mathematik)|Folge]] keinen endlichen Grenzwert besitzt, was wiederum bedeutet, dass sich für ein genügend groß gewähltes ''n'' jede erdenkliche reelle Zahl übertreffen lässt. Dies ist zunächst einmal verblüffend, da die [[Primzahllücke]]n im Schnitt immer weiter zunehmen. Der [[Satz von Mertens (Zahlentheorie)|Satz von Mertens]] trifft eine Aussage über das genaue Wachstumsverhalten dieser divergenten Reihe.

== Primzahltests ==

{{Hauptartikel|Primzahltest}}

Ob eine beliebige natürliche Zahl prim ist, kann mit einem Primzahltest herausgefunden werden. Es gibt mehrere solcher Verfahren, die sich auf besondere Eigenschaften von Primzahlen stützen. In der Praxis wird der [[Miller-Rabin-Test]] am häufigsten verwendet, der eine extrem kurze Laufzeit hat, allerdings mit kleiner Wahrscheinlichkeit falsch-positive Ergebnisse liefert. Mit dem [[AKS-Primzahltest]] ist es möglich, über die Primalität in polynomialer Laufzeit zu entscheiden. Allerdings ist er in der Praxis deutlich langsamer als der Miller-Rabin-Test.

== Primzahlzertifikat ==

Herauszufinden, ob eine natürliche Zahl prim ist oder nicht, kann sehr aufwändig sein. Zu jeder Primzahl lässt sich aber eine Kette von Behauptungen angeben, die alle unmittelbar nachvollziehbar sind, zusammen die Primalität belegen und deren Gesamtlänge höchstens proportional ist zum Quadrat der Länge der Primzahl.<ref>Vaughan R. Pratt: ''[http://boole.stanford.edu/pub/SucCert.pdf Every Prime has a Succinct Certificate.]'' PDF.</ref><ref>[[Vašek Chvátal]]: ''[http://www.cs.concordia.ca/~chvatal/notes/ppp.pdf Lecture notes on Pratt’s Primality Proofs.]'' PDF.</ref> Ein solcher Beleg wird ''Zertifikat'' (engl. ''primality certificate'') genannt.<ref>''[http://www.theoremoftheday.org/LogicAndComputerScience/Pratt/TotDPratt.pdf Der Satz von Vaughan Pratt als Theorem des Tages.]'' PDF.</ref>

Bei der Zusammengesetztheit (Nichtprimalität) einer Zahl ist der Unterschied zwischen Beleg und Finden eines Belegs noch augenfälliger: Als Beleg genügen zwei Faktoren, deren Produkt die zusammengesetzte Zahl ergibt; das Finden eines echten Teilers kann aber sehr viel Aufwand bedeuten.

== Größte bekannte Primzahl ==

Der Grieche [[Euklid]] hat im vierten Jahrhundert vor Christus logisch geschlussfolgert, dass es unendlich viele Primzahlen gibt; diese Aussage wird als ''[[Satz von Euklid]]'' bezeichnet. Euklid führte einen [[Widerspruchsbeweis]] für die Richtigkeit dieses Satzes (''Elemente,'' Buch IX, § 20): Ausgehend von der Annahme, dass es nur endlich viele Primzahlen gibt, lässt sich eine weitere Zahl konstruieren, die eine bisher nicht bekannte Primzahl als Teiler hat oder selbst eine Primzahl ist, was einen Widerspruch zur Annahme darstellt. Somit kann eine endliche Menge niemals alle Primzahlen enthalten, also gibt es unendlich viele. Heute kennt man eine ganze Reihe von Beweisen für den Satz von Euklid.<ref>Für Beweise des Satzes von Euklid siehe [[b:Beweisarchiv: Zahlentheorie: Elementare Zahlentheorie: Satz von Euklid|Beweisarchiv]].</ref>

Der Satz von Euklid besagt, dass es keine größte Primzahl gibt. Es ist jedoch kein Verfahren bekannt, das effizient beliebig große Primzahlen generiert – deshalb gab es stets eine jeweils ''größte bekannte'' Primzahl, seitdem sich die Menschen mit Primzahlen befassen. Derzeit (Stand: April 2017) ist es <math>2^{74.207.281}-1,</math> eine Zahl mit 22.338.618 (dezimalen) Stellen, die am 7. Januar 2016 mit einem CPU-Cluster der mathematischen Fakultät an der [[University of Central Missouri]] berechnet wurde. Für den Entdecker Curtis Cooper gab es für den Fund 3.000 US-Dollar vom Projekt [[Great Internet Mersenne Prime Search]], das [[Mersenne-Primzahl]]en mittels [[Verteiltes Rechnen|verteiltem Rechnen]] sucht.<ref name="Gimps Projekt">''[http://www.mersenne.org/primes/?press=M74207281 GIMPS Project Discovers Largest Known Prime Number, 274.207.281−1.]'' Bei: ''mersenne.org.'' Abgerufen am 20. Januar 2016.</ref><ref>''[http://www.spiegel.de/wissenschaft/mensch/primzahlen-neue-rekord-zahl-mit-22-33-millionen-stellen-gefunden-a-1072883.html 22,34 Millionen Stellen lang: Neue Rekord-Primzahl entdeckt.]'' Bei: ''Spiegel.de.'' 20. Januar 2016, abgerufen am 20. Januar 2016.</ref>

Die größte bekannte Primzahl war fast immer eine [[Mersenne-Primzahl]], also von der Form <math>2^n-1,</math> da in diesem Spezialfall der [[Lucas-Lehmer-Test]] angewendet werden kann, ein im Vergleich zur allgemeinen Situation sehr schneller Primzahltest. Bei der Suche nach großen Primzahlen werden deshalb nur Zahlen dieses oder eines ähnlich geeigneten Typs auf Primalität untersucht.

== Liste der Rekordprimzahlen nach Jahren ==

{| class="wikitable" style="text-align:right;"
|- class="hintergrundfarbe6"
! Zahl
! Anzahl der [[Dezimalsystem|Dezimalziffern]]
! Jahr
! Entdecker (genutzter Computer)
|-
| 217−1
| 6
| 1588
| [[Pietro Cataldi|Cataldi]]
|-
| 219−1
| 6
| 1588
| [[Pietro Cataldi|Cataldi]]
|-
| 231−1
| 10
| 1772
| [[Leonhard Euler|Euler]]
|-
| (259−1)/179951
| 13
| 1867
| [[Fortuné Landry|Landry]]
|-
| 2127−1
| 39
| 1876
| [[Édouard Lucas|Lucas]]
|-
| (2148+1)/17
| 44
| 1951
| [[Aimé Ferrier|Ferrier]]
|-
| 180·(2127−1)2+1
| 79
| 1951
| Miller & Wheeler (EDSAC1)
|-
| 2521−1
| 157
| 1952
| Robinson (SWAC)
|-
| 2607−1
| 183
| 1952
| Robinson (SWAC)
|-
| 21.279−1
| 386
| 1952
| Robinson (SWAC)
|-
| 22.203−1
| 664
| 1952
| Robinson (SWAC)
|-
| 22.281−1
| 687
| 1952
| Robinson (SWAC)
|-
| 23.217−1
| 969
| 1957
| Riesel (BESK)
|-
| 24.423−1
| 1.332
| 1961
| Hurwitz (IBM7090)
|-
| 29.689−1
| 2.917
| 1963
| Gillies (ILLIAC 2)
|-
| 29.941−1
| 2.993
| 1963
| Gillies (ILLIAC 2)
|-
| 211.213−1
| 3.376
| 1963
| Gillies (ILLIAC 2)
|-
| 219.937−1
| 6.002
| 1971
| Tuckerman (IBM360/91)
|-
| 221.701−1
| 6.533
| 1978
| Noll & Nickel (CDC Cyber 174)
|-
| 223.209−1
| 6.987
| 1979
| Noll (CDC Cyber 174)
|-
| 244.497−1
| 13.395
| 1979
| Nelson & Slowinski (Cray 1)
|-
| 286.243−1
| 25.962
| 1982
| Slowinski (Cray 1)
|-
| 2132.049−1
| 39.751
| 1983
| Slowinski (Cray X-MP)
|-
| 2216.091−1
| 65.050
| 1985
| Slowinski (Cray X-MP/24)
|-
| 391581·2216.193−1
| 65.087
| 1989
| „Amdahler Sechs“ (Amdahl 1200)
|-
| 2756.839−1
| 227.832
| 1992
| Slowinski & Gage (Cray 2)
|-
| 2859.433−1
| 258.716
| 1994
| Slowinski & Gage (Cray C90)
|-
| 21.257.787−1
| 378.632
| 1996
| Slowinski & Gage (Cray T94)
|-
| 21.398.269−1
| 420.921
| 1996
| Armengaud, Woltman ([[Great Internet Mersenne Prime Search|GIMPS]], Pentium 90 MHz)
|-
| 22.976.221−1
| 895.932
| 1997
| Spence, Woltman (GIMPS, Pentium 100 MHz)
|-
| 23.021.377−1
| 909.526
| 1998
| Clarkson, Woltman, Kurowski (GIMPS, Pentium 200 MHz)
|-
| 26.972.593−1
| 2.098.960
| 1999
| Hajratwala, Woltman, Kurowski (GIMPS, Pentium 350 MHz)
|-
| 213.466.917−1
| 4.053.946
| 2001
| Cameron, Woltman, Kurowski (GIMPS, Athlon 800 MHz)
|-
| 220.996.011−1
| 6.320.430
| 2003
| Shafer (GIMPS, Pentium 4 2 GHz)
|-
| 224.036.583−1
| 7.235.733
| 2004
| Findley (GIMPS, Pentium 4 2,4 GHz)
|-
| 225.964.951−1
| 7.816.230
| 2005
| Nowak (GIMPS, Pentium 4 2,4 GHz)
|-
| 230.402.457−1
| 9.152.052
| 2005
| Cooper, Boone (GIMPS, Pentium 4 3 GHz)
|-
| 232.582.657−1
| 9.808.358
| 2006
| Cooper, Boone (GIMPS, Pentium 4 3 GHz)

|-
| 243.112.609−1
| 12.978.189
| 2008
| Smith, Woltman, Kurowski et al. (GIMPS, Core 2 Duo 2,4 GHz)
|-
| 257.885.161−1
| 17.425.170
| 2013
| Cooper, Woltman, Kurowski et al. (GIMPS)
|-
| 274.207.281−1
| 22.338.618
| 2016
| Cooper, Woltman, Kurowski et al. (GIMPS)
|}

== Verteilung und Wachstum ==

=== Pi-Funktion und Primzahlsatz ===

{{Hauptartikel|Primzahlsatz}}
[[Datei:PrimeNumberTheorem.svg|mini|In der Grafik wird die π-Funktion in blau dargestellt. Die Funktion ''n''/ln(''n'') in grün und der [[Integrallogarithmus]] Li(''n'') in rot sind Approximationen der π-Funktion.]]

Zur Untersuchung der Verteilung der Primzahlen betrachtet man unter anderem die Funktion

: <math>\pi \colon \Bbb N\to \Bbb N,\;n\mapsto\pi(n)</math>,

die die Anzahl der Primzahlen <math>\leq n</math> angibt und auch ''Primzahlzählfunktion'' genannt wird.
Zum Beispiel ist

: <math>\pi(1)=0\ ;\ \pi(10) = 4\ ;\ \pi(100) = 25\ ;\ \pi(1000) = 168; \ \pi(1000000)=78498</math>.

Diese Funktion und ihr Wachstumsverhalten ist ein beliebter Forschungsgegenstand in der Zahlentheorie. Mit der Zeit wurden einige Näherungsformeln entwickelt und verbessert.

Der Primzahlsatz besagt, dass

: <math>\pi(x) \sim \frac{x}{\ln x}</math>

gilt, das heißt, dass der Quotient von linker und rechter Seite für <math>x\to\infty</math> gegen 1 strebt:

: <math>\lim_{x \to \infty} \frac{\pi(x)} {\frac{x}{\ln x}} = 1</math> (siehe [[Asymptotische Analyse]])

Der [[Dirichletscher Primzahlsatz|dirichletsche Primzahlsatz]] dagegen schränkt die Betrachtung auf [[Restklasse]]n ein: Es sei <math>m</math> eine natürliche Zahl. Ist <math>a</math> eine ganze Zahl, die zu <math>m</math> nicht [[teilerfremd]] ist, so kann die [[arithmetische Folge]]

: <math>a, a+m, a+2m, a+3m, \dotsc</math>

höchstens eine Primzahl enthalten, weil alle Folgenglieder durch den größten gemeinsamen Teiler von <math>a</math> und <math>m</math> teilbar sind. Ist <math>a</math> aber teilerfremd zu <math>m</math>, so besagt der dirichletsche Primzahlsatz, dass die Folge unendlich viele Primzahlen enthält. Beispielsweise gibt es unendlich viele Primzahlen der Form <math>4k+1</math> und unendlich viele der Form <math>4k+3</math> (<math>k</math> durchläuft jeweils die nichtnegativen natürlichen Zahlen).

Diese Aussage kann noch in der folgenden Form präzisiert werden: Es gilt

: <math>\lim_{x\to\infty}\frac{\#\{p \ \mid \ \mathrm{prim},\ p\leq x\ \mathrm{und}\ p\equiv a\pmod m\}}{\#\{p \ \mid \ \mathrm{prim},\ p\leq x\}}=\frac1{\varphi(m)};</math>

dabei ist <math>\varphi(m)</math> die [[eulersche Phi-Funktion]]. In diesem Sinne liegen also für ein festes <math>m</math> in den Restklassen <math>a+m\mathbb Z</math> mit <math>\mathrm{ggT}(a,m)=1</math> jeweils „gleich viele“ Primzahlen.

{{Siehe auch|Ulam-Spirale}}

=== Schranken ===

Die (bewiesene) [[Bonsesche Ungleichung]] garantiert, dass das Quadrat einer Primzahl kleiner ist als das Produkt aller kleineren Primzahlen (ab der fünften Primzahl).

Nach der (unbewiesenen) [[Andricasche Vermutung|Andricaschen Vermutung]] ist die Differenz der Wurzeln der <math>n</math>-ten und der <math>(n+1)</math>-ten Primzahl kleiner als 1.

=== Primzahllücken ===

{{Hauptartikel|Primzahllücke}}

Die Differenz zwischen zwei benachbarten Primzahlen heißt Primzahllücke. Diese Differenz schwankt, und es gibt Primzahllücken beliebiger Größe. Es gibt aber auch Beschränkungen für die Lückengröße in Abhängigkeit von ihrer Lage:

Der [[Bertrandsches Postulat|Satz von Bertrand]] sichert die Existenz einer Primzahl zwischen jeder natürlichen Zahl <math>n</math> und ihrem Doppelten <math>2n</math>.

Nach der (unbewiesenen) [[Legendresche Vermutung|Legendreschen Vermutung]] gibt es stets mindestens eine Primzahl zwischen <math>n^2</math> und <math>(n+1)^2</math>.

=== Abschätzungen zu Primzahlen und Folgerungen aus dem Primzahlsatz ===

Im Folgenden sei die [[Folge (Mathematik)|Folge]] der Primzahlen mit <math>(p_n)_{n \in \N}</math> bezeichnet.

==== Abschätzungen ====

Für [[Indexmenge (Mathematik)|Indizes]] <math>n \in \N</math> gelten folgende [[Abschätzung]]en:
;(1a)
: <math>p_n < p_{n+1} < 2 \cdot p_n</math><ref>Rademacher-Toeplitz: S. 164.</ref><ref>Sierpiński: S. 146.</ref>

;(1b)
: <math>{p_{n+1}}^2 < 2 \cdot {p_n}^2</math> für <math>n \ge 5</math><ref>{{Literatur |Autor=Dressler-Pigno-Young |Titel=Nordisk Mat. Tidskr |Band=24 |Seiten=39}}</ref><ref>Sándor-Mitrinović-Crstici: S. 247.</ref>

;(1c)
: <math>p_n < 2^n</math> für <math>n \ge 2</math><ref>Sierpiński: S. 145.</ref>

;(1d)
: <math>p_n > n \cdot \ln(n)</math><ref>Die Abschätzung '''(1d)''' wurde zuerst von [[John Barkley Rosser]] gefunden (s. Rosser in: Proc. London Math. Soc., Bd. 45, S. 21 ff. / Sierpiński, S. 163 / Sándor-Mitrinović-Crstici, S. 247).</ref>

;(1e)
: <math>\sum_{k=2}^n{\frac{1}{p_k}} > \frac{1}{36} \cdot {\ln{\ln (n+1)}}</math> für <math>n \ge 2</math><ref>Sierpiński: S. 162.</ref><ref>Aus '''(1e)''' ergibt sich, wie Sierpiński anmerkt, unmittelbar die [[Reihe (Mathematik)#Auswertung und Einteilung|Divergenz]] der Reihe <math>\textstyle \sum_{k=1}^{\infty}{\frac{1}{p_k}}</math>.</ref>

==== Folgerungen aus dem Primzahlsatz ====

Mit dem Primzahlsatz ergeben sich folgende Resultate:

;(2a)
: <math>\lim_{n \rightarrow \infty} \frac{p_{n+1}}{p_n} = 1</math><ref>Sierpiński: S. 163.</ref>

;(2b)
: <math>\frac{n}{\ln(n) - \frac{1}{2}} < \pi(n) < \frac{n}{\ln(n) - \frac{3}{2}}</math> für <math>n \ge 67</math><ref>{{Literatur |Autor=Rosser-Schoenfeld |Titel=Illinois J. Math |Band=6 |Seiten=64 ff.}}</ref><ref>Sierpiński: S. 163.</ref><ref>Wie Sierpiński anmerkt, gelangt man mit '''(2b)''' unmittelbar zum Primzahlsatz.</ref>

;(2c)
Für jede [[Positive Zahl|positive]] [[reelle Zahl]] <math>x</math> existiert eine [[Folge (Mathematik)|Folge]] <math>(q_n)_{n \in \N}</math> von Primzahlen mit
: <math>\lim_{n \rightarrow \infty} \frac{q_n}{n} = x</math>.<ref>Sierpiński: S. 165.</ref><ref>Dieses Ergebnis wurde gemäß Sierpiński zuerst von dem polnischen Mathematiker [[Hugo Steinhaus]] gewonnen.</ref>

;(2d)
Die [[Menge (Mathematik)|Menge]] der aus allen Primzahlen gebildeten [[Quotient]]en ist eine [[dichte Teilmenge]] der Menge aller positiven reellen Zahlen. D. h.: Für beliebige positive reelle Zahlen <math>a, b</math> mit <math>0 < a < b</math> existieren stets Primzahlen <math>p, q</math>, sodass
: <math>a < \frac{p}{q} < b</math>

erfüllt ist.<ref>Sierpiński: S. 165.</ref>

== Generierung von Primzahlen ==

{{Hauptartikel|Primzahlgenerator}}
[[Datei:Sieve of Eratosthenes animation.gif|mini|Veranschaulichung des Algorithmus ''Sieb des Eratosthenes'']]

Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das [[Sieb des Eratosthenes]]. Bis heute ist kein effizienter Primzahlgenerator bekannt. Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen prim sind. Solche Zahlen müssen nachträglich noch auf ihre Primalität getestet werden.

== Spezielle Primzahlen und Primzahlkonstellationen ==

* [[Cullen-Zahl|Cullen- und Woodall-Zahlen]]
* [[Cunningham-Kette]]n
* [[Elitäre Primzahl]]en
* [[Fastprimzahl]]en
* [[Glückliche Zahl|glückliche Primzahlen]]
* [[Gute Primzahl]]en
* [[Mersenne-Primzahl]]en
* [[Mills-Primzahl]]en
* [[Pierpont-Primzahl]]en
* [[Primzahlencousin]]
* [[Primzahltupel]]
* [[Primzahlzwilling]]e
* [[Prothsche Primzahl]]en
* [[Schwache Primzahl]]en
* [[Sexy Primzahl]]en
* [[Sophie-Germain-Primzahl]]en
* [[Streng nicht-palindromische Zahl]]en
* [[Ulam-Spirale]]
* [[Wall-Sun-Sun-Primzahl]]en

Weitere spezielle Arten von Primzahlen finden sich in der [[:Kategorie:Primzahl]].

== Verallgemeinerung ==

In der Ringtheorie wird das Konzept der ''Primzahl'' auf die Elemente eines beliebigen kommutativen unitären Rings verallgemeinert. Die entsprechenden Begriffe sind ''[[Primelement]]'' und ''[[irreduzibles Element]].''

Die Primzahlen und deren Negative sind dann genau die Primelemente und auch genau die irreduziblen Elemente des Rings der [[Ganze Zahl|ganzen Zahlen]]. In [[Faktorieller Ring|faktoriellen Ringen]], das sind Ringe mit eindeutiger Primfaktorisierung, fallen die Begriffe ''Primelement'' und ''irreduzibles Element'' zusammen; im Allgemeinen ist die Menge der Primelemente jedoch nur eine [[Teilmenge]] der Menge der irreduziblen Elemente.

Insbesondere im zahlentheoretisch bedeutsamen Fall der [[Dedekindring]]e übernehmen [[Primideal]]e die Rolle der Primzahlen.

== Primzahlen in der Natur ==

In Nordamerika weisen manche [[Zikade#Fortpflanzung und Entwicklung|Zikadenarten]] einen besonders langen Fortpflanzungsrhythmus von genau 13 oder 17 Jahren auf, mit dem sie den 2-, 4- und 6-jährigen Entwicklungsrhythmen ihrer Fressfeinde ausweichen.

== Siehe auch ==

* [[Gilbreaths Vermutung]]
* [[Illegale Primzahl]]
* [[Permutierbare Primzahl]]
* [[Relativ prim]]

== Literatur ==

* [[Peter Bundschuh]]: ''Einführung in die Zahlentheorie.'' 6. Auflage. Springer, Berlin 2008, ISBN 978-3-540-76490-8.
* [[Marcus du Sautoy]]: ''Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik.'' Beck, München 2004, ISBN 3-406-52320-X.
* [[Władysław Narkiewicz]]: ''The Development of Prime Number Theory. From Euclid to Hardy and Littlewood.'' Springer, Berlin 2000, ISBN 3-540-66289-8.
* [[Paulo Ribenboim]]: ''The New Book of Prime Number Records.'' Springer, New York 1996, ISBN 0-387-94457-5.

* {{Literatur
|Autor=Robert E. Dressler, Louis Pigno, Robert Young
|Titel=Sums of squares of primes
|Sammelwerk=[[Nordisk Matematisk Tidskrift|Nordisk Mat. Tidskr]]
|Band=24
|Datum=1976
|Seiten=39–40
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=JOUR&pg7=ALLF&pg8=ET&review_format=html&s4=Dressler%2C%20Robert%20E.&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=10&mx-pid=419352 MR0419352]}}
* {{Literatur
|Autor=[[Hans Rademacher]], [[Otto Toeplitz]]
|Titel=Von Zahlen und Figuren. Proben mathematischen Denkens für Liebhaber der Mathematik
|Reihe=Heidelberger Taschenbücher
|Band=50
|Verlag=Springer Verlag
|Ort=Berlin (u. a.)
|Datum=1968
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=AUCN&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Toeplitz&s5=Rademacher&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=4&mx-pid=252141 MR0252141]}}
* {{Literatur
|Autor=[[John Barkley Rosser|J. B. Rosser]]
|Titel=The n-th prime is greater than n log n
|Sammelwerk=[[London Mathematical Society|Proc. London Math. Soc]]
|Band=45
|Datum=1939
|Seiten=21–44}}
* {{Literatur
|Autor=[[John Barkley Rosser|J. Barkley Rosser]], [[Lowell Schoenfeld|L. Schoenfeld]]
|Titel=Approximate formulas for some functions of prime numbers
|Sammelwerk=[[Illinois Journal of Mathematics|Illinois J. Math]]
|Band=6
|Datum=1962
|Seiten=64–94
|Online=[http://www.projecteuclid.org/download/pdf_1/euclid.ijm/1255631807 projecteuclid.org]}} [http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Schoenfeld&s5=&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=66&mx-pid=137689 MR0137689]
* {{Literatur
|Autor=[[Wacław Sierpiński]]
|Titel=Elementary Theory of Numbers
|Reihe=North-Holland Mathematical Library
|Band=31
|Auflage=2. überarbeitete und erweiterte
|Verlag=North-Holland (u. a.)
|Ort=Amsterdam (u. a.)
|Datum=1988
|ISBN=0-444-86662-0}}
* {{Literatur
|Autor=[[József Sándor]], [[Dragoslav Mitrinović|Dragoslav S. Mitrinović]], [[Borislav Crstici]]
|Titel=Handbook of Number Theory.
|Band=Band I
|Auflage=2.
|Verlag=Springer-Verlag
|Ort=Dordrecht, NL
|Datum=2006
|ISBN=978-1-4020-4215-7
|Online=[http://www.ams.org/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=AUCN&pg6=PC&pg7=ALLF&pg8=ET&review_format=html&s4=Sandor&s5=Crstici&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq&r=1&mx-pid=2186914 MR2186914]}}

== Externe Links ==

{{Commonscat|Prime numbers|Primzahlen}}
{{Wiktionary}}
{{Wikibooks|Mathematik: Zahlentheorie: Fundamentalsatz der Arithmetik|Fundamentalsatz der Arithmetik}}
{{Wikibooks|Primzahlen: Tabelle der Primzahlen (2 - 100.000)|Primzahlen von 2 bis 100.000}}
* [http://www.utm.edu/research/primes/ The Prime Pages] (englisch)
* [http://www.primzahlen.de/ Die Primzahlenseite]
* {{MathWorld |id=RossersTheorem |title=Rosser’s Theorem}}
* [http://www.dasinternet.net/liste_primzahlen_1_bis_1mio.php Liste der Primzahlen zwischen 1 und 1.000.000]

== Einzelnachweise ==

<references />

[[Kategorie:Ganzzahlmenge]]
[[Kategorie:Primzahl| ]]
[[Kategorie:Zahlentheorie]]

Primzahl - Versionsgeschichte

C1ph4: Die Seite wurde neu angelegt: „{{Zeichen|\mathbb P}} Eine '''Primzahl''' (wörtlich „erste Zahl“ oder eher „Zahl erster Klasse“) ist eine natürliche Zahl, die grö…“

C1ph4: Die Seite wurde neu angelegt: „{{Zeichen| $\mathbb P$ }} Eine '''Primzahl''' (wörtlich „erste Zahl“ oder eher „Zahl erster Klasse“) ist eine natürliche Zahl, die grö…“