Primzahl

Aus AnthroWiki
Wechseln zu: Navigation, Suche

Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist.

Das Wort „Primzahl“ kommt aus dem Lateinischen und bedeutet „erste Zahl“ oder eher „Zahl erster Klasse“ (numerus primus = die erste Zahl).

Die Menge der Primzahlen wird in der Regel mit dem Symbol LaTeX: \mathbb P bezeichnet. Mit LaTeX: \mathbb P verknüpft ist die Folge LaTeX: \left(p_n \right)_{n \in \N} der nach ihrer Größe geordneten Primzahlen, die man auch kurz die Primzahlfolge nennt. Es ist demnach

LaTeX: \N \supset \mathbb P = \{ p_n \mid n \in \N \}

mit

LaTeX: \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) (Folge A000040 in OEIS).
Die Zahl 12 ist keine Primzahl, die Zahl 11 hingegen schon.

Die Zahl 1 ist wegen ihrer Invertierbarkeit weder prim noch zusammengesetzt. Alle anderen natürlichen Zahlen sind eines von beiden, entweder prim (also Primzahl) oder zusammengesetzt.

Die Bedeutung der Primzahlen LaTeX: \mathbb P für viele Bereiche der Mathematik beruht auf drei Folgerungen aus ihrer 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 Verallgemeinerungen des Primzahlbegriffs genutzt.

Schon im 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 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 Primzahlzwillinge 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

Es gilt der Fundamentalsatz der Arithmetik: Jede positive ganze Zahl lässt sich als Produkt von Primzahlen darstellen, und diese Darstellung ist bis auf die Reihenfolge der Primzahlen eindeutig. Diese Primzahlen nennt man die Primfaktoren der Zahl. Die Eins wird dabei als leeres Produkt dargestellt.

Aufgrund dieses Satzes, also dass sich jede natürliche Zahl größer Null durch Multiplikation von Primzahlen eindeutig darstellen lässt, nehmen die Primzahlen eine besondere atomare Stellung in der Mathematik ein, sie „erzeugen“ gewissermaßen alle anderen natürlichen Zahlen. Alexander K. Dewdney bezeichnete sie als den Elementen der Chemie weitgehend ähnlich.

Daraus wird auch klar, warum es unzweckmäßig ist, die Eins als Primzahl zu definieren: Sie ist das neutrale Element der Multiplikation und kann somit multiplikativ keine weiteren Zahlen erzeugen. Sie wird für die Darstellung der Zahlen als Produkt von Primfaktoren nicht benötigt. Würde man die 1 zu den Primzahlen zählen, verlöre sich darüber hinaus die Eindeutigkeit der Primfaktorzerlegung, weil man an jede Zerlegung beliebig viele Einsen anhängen kann, ohne den Wert der Zahl zu ändern.

Man kennt bisher keine Methode, um die Primfaktorzerlegung einer beliebigen gegebenen Zahl effizient zu bestimmen, d. h. in einer Zeit, die polynomiell mit der Länge der Zahl wächst. Die Faktorisierungsannahme besagt, dass es eine solche Methode auch nicht gibt. Man hat eine Reihe von Faktorisierungsverfahren entwickelt, um allgemeine Zahlen oder auch solche von spezieller Form möglichst schnell zu zerlegen.

Eigenschaften von Primzahlen

Die Primzahlen sind innerhalb der Menge LaTeX: \N der natürlichen Zahlen dadurch charakterisiert, dass jede von ihnen genau zwei natürliche Zahlen als Teiler hat.[1]

Mit Ausnahme der Zahl 2 sind alle Primzahlen LaTeX: p 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 LaTeX: 2k+1 mit einer natürlichen Zahl LaTeX: k.

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

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

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

LaTeX: p=(a+b\mathrm i)(a-b\mathrm i)

im Ring der ganzen gaußschen Zahlen.

Die Zahl −1 ist ein quadratischer Rest modulo jeder Primzahl der Form LaTeX: 4k+1 und quadratischer Nichtrest modulo jeder Primzahl der Form LaTeX: 4k+3.

Der kleine Satz von Fermat

Es sei LaTeX: p eine Primzahl. Für jede ganze Zahl LaTeX: a, die nicht durch LaTeX: p teilbar ist, gilt (für die Notation siehe Kongruenz):

LaTeX: a^{p-1} \equiv 1 \mod p.

Für nicht durch LaTeX: p teilbare Zahlen LaTeX: a ist die folgende Formulierung äquivalent:

LaTeX: a^p\equiv a\mod p.

Es gibt Zahlen, die keine Primzahlen sind, sich aber dennoch zu einer Basis LaTeX: a wie Primzahlen verhalten und somit den kleinen Satz von Fermat erfüllen. Solche zusammengesetzten Zahlen nennt man fermatsche Pseudoprimzahlen zur Basis LaTeX: a. Eine fermatsche Pseudoprimzahl LaTeX: n, die pseudoprim bezüglich aller zu ihr teilerfremden Basen LaTeX: a 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 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 LaTeX: p und jede ganze Zahl LaTeX: a, die nicht durch LaTeX: p teilbar ist, gilt entweder

LaTeX: a^{\frac{p-1}{2}} \equiv 1 \mod p

oder

LaTeX: a^{\frac{p-1}{2}} \equiv -1 \mod p.

Man kann zeigen, dass der erste Fall genau dann eintritt, wenn es eine Quadratzahl LaTeX: m^2 gibt, die kongruent zu LaTeX: a modulo LaTeX: p ist, siehe Legendre-Symbol.

Binomialkoeffizient

Für Primzahlen LaTeX: p und LaTeX: 1\leq k < p gilt

LaTeX: p\,\Big|{p\choose k};

zusammen mit dem binomischen Satz folgt daraus

LaTeX: (a+b)^p\equiv a^p+b^p\mod p.

Für ganze Zahlen LaTeX: a, b 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 LaTeX: x\mapsto x^p in Ringen der Charakteristik LaTeX: p ein Homomorphismus ist, der sogenannte Frobenius-Homomorphismus.

Aus dem Satz von Wilson (LaTeX: p ist genau dann eine Primzahl, wenn LaTeX: (p-1)! \equiv -1 \pmod p ist) folgt, dass für jede Primzahl LaTeX: p und jede natürliche Zahl LaTeX: p die Kongruenz

LaTeX: {{np-1}\choose{p-1}} \equiv 1 \pmod{p}

erfüllt ist.

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

LaTeX: {{2p-1}\choose{p-1}} \equiv 1 \pmod{p^2}

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

LaTeX: {{2p-1}\choose{p-1}} \equiv 1 \pmod{p^3}

Giuga

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

LaTeX: 1^{p-1} + 2^{p-1} + \dotsb + (p-1)^{p-1} \equiv -1 \pmod{p}

Beispiel LaTeX: p = 5:

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

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-Zahlen untersucht.

Lineare Rekursionen

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

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

das Legendre-Symbol.

Divergenz der Summe der Kehrwerte

Die Reihe der Kehrwerte der Primzahlen ist divergent. Somit gilt:

LaTeX: \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.

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

Primzahltests

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 ohne Gefahr eines Irrtums in polynomieller 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.[2][3] Ein solcher Beleg wird Zertifikat (engl. primality certificate) genannt.[4]

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.[5]

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: Januar 2018) ist es LaTeX: 2^{77.232.917}-1, eine Zahl mit 23.249.425 (dezimalen) Stellen, die am 26. Dezember 2017 berechnet wurde. Für den Entdecker Jonathan Pace gab es für den Fund 3.000 US-Dollar vom Projekt Great Internet Mersenne Prime Search, das Mersenne-Primzahlen mittels verteiltem Rechnen sucht.[6]

Die größte bekannte Primzahl war fast immer eine Mersenne-Primzahl, also von der Form LaTeX: 2^n-1, 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

Zahl Anzahl der
Dezimalziffern
Jahr Entdecker (genutzter Computer)
217−1 6 1588 Cataldi
219−1 6 1588 Cataldi
231−1 10 1772 Euler
(259−1)/179951 13 1867 Landry
2127−1 39 1876 Lucas
(2148+1)/17 44 1951 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 (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, Core2 Duo E8400 @ 3,00 GHz)
274.207.281−1 22.338.618 2016 Cooper, Woltman, Kurowski et al. (GIMPS, Intel i7-4790 @ 3,60 GHz)
277.232.917–1 23.249.425 2017 Jonathan Pace et al. (GIMPS, Intel i5-6600 @ 3,30 GHz)

Verteilung und Wachstum

Pi-Funktion und Primzahlsatz

Primzahlsatz - Artikel in der deutschen Wikipedia

In der Grafik wird die LaTeX: \pi-Funktion in blau dargestellt. Die Funktion LaTeX: n/\ln(n) in grün und der Integrallogarithmus LaTeX: \operatorname{Li}(n) in rot sind Approximationen der LaTeX: \pi-Funktion.

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

LaTeX: \pi \colon \Bbb N\to \Bbb N,\;n\mapsto\pi(n),

die die Anzahl der Primzahlen LaTeX: \leq n angibt und auch Primzahlzählfunktion genannt wird. Zum Beispiel ist

LaTeX: \pi(1)=0\ ;\ \pi(10) = 4\ ;\ \pi(100) = 25\ ;\ \pi(1000) = 168; \ \pi(1000000)=78498.

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

LaTeX: \pi(x) \sim \frac{x}{\ln x}

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

LaTeX: \lim_{x \to \infty} \frac{\pi(x)} {\frac{x}{\ln x}} = 1 (siehe Asymptotische Analyse)

Der dirichletsche Primzahlsatz dagegen schränkt die Betrachtung auf Restklassen ein: Es sei LaTeX: m eine natürliche Zahl. Ist LaTeX: a eine ganze Zahl, die zu LaTeX: m nicht teilerfremd ist, so kann die arithmetische Folge

LaTeX: a, a+m, a+2m, a+3m, \dotsc

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

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

LaTeX: \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)};

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

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) Andricaschen Vermutung ist die Differenz der Wurzeln der LaTeX: n-ten und der LaTeX: (n+1)-ten Primzahl kleiner als 1.

Primzahllücken

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 Satz von Bertrand sichert die Existenz einer Primzahl zwischen jeder natürlichen Zahl LaTeX: n und ihrem Doppelten LaTeX: 2n.

Nach der (unbewiesenen) Legendreschen Vermutung gibt es stets mindestens eine Primzahl zwischen LaTeX: n^2 und LaTeX: (n+1)^2.

Abschätzungen zu Primzahlen und Folgerungen aus dem Primzahlsatz

Im Folgenden sei die Folge der Primzahlen mit LaTeX: (p_n)_{n \in \N} bezeichnet.

Abschätzungen

Für Indizes LaTeX: n \in \N gelten folgende Abschätzungen:

(1a)
LaTeX: p_n < p_{n+1} < 2 \cdot p_n[7][8]
(1b)
LaTeX: {p_{n+1}}^2 < 2 \cdot {p_n}^2 für LaTeX: n \ge 5[9][10]
(1c)
LaTeX: p_n < 2^n für LaTeX: n \ge 2[11]
(1d)
LaTeX: p_n > n \cdot \ln(n)[12]
(1e)
LaTeX: \sum_{k=2}^n{\frac{1}{p_k}} > \frac{1}{36} \cdot {\ln{\ln (n+1)}} für LaTeX: n \ge 2[13][14]

Folgerungen aus dem Primzahlsatz

Mit dem Primzahlsatz ergeben sich folgende Resultate:

(2a)
LaTeX: \lim_{n \rightarrow \infty} \frac{p_{n+1}}{p_n} = 1[15]
(2b)
LaTeX: \frac{n}{\ln(n) - \frac{1}{2}} < \pi(n) < \frac{n}{\ln(n) - \frac{3}{2}} für LaTeX: n \ge 67[16][17][18]
(2c)

Für jede positive reelle Zahl LaTeX: x existiert eine Folge LaTeX: (q_n)_{n \in \N} von Primzahlen mit

LaTeX: \lim_{n \rightarrow \infty} \frac{q_n}{n} = x.[19][20]
(2d)

Die Menge der aus allen Primzahlen gebildeten Quotienten ist eine dichte Teilmenge der Menge aller positiven reellen Zahlen. D. h.: Für beliebige positive reelle Zahlen LaTeX: a, b mit LaTeX: 0 < a < b existieren stets Primzahlen LaTeX: p, q, sodass

LaTeX: a < \frac{p}{q} < b

erfüllt ist.[21]

Generierung von Primzahlen

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

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 ganzen Zahlen. In 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 Dedekindringe übernehmen Primideale die Rolle der Primzahlen.

Primzahlen in der Natur

In Nordamerika weisen manche 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

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.
  •  Robert E. Dressler, Louis Pigno, Robert Young: Sums of squares of primes. In: Nordisk Mat. Tidskr. 24, 1976, S. 39–40 (MR0419352).
  •  Hans Rademacher, Otto Toeplitz: Von Zahlen und Figuren. Proben mathematischen Denkens für Liebhaber der Mathematik (= Heidelberger Taschenbücher. 50). Springer Verlag, Berlin (u. a.) 1968 (MR0252141).
  •  J. B. Rosser: The n-th prime is greater than n log n. In: Proc. London Math. Soc. 45, 1939, S. 21–44.
  •  J. Barkley Rosser, L. Schoenfeld: Approximate formulas for some functions of prime numbers. In: Illinois J. Math. 6, 1962, S. 64–94 (projecteuclid.org). MR0137689
  •  Wacław Sierpiński: Elementary Theory of Numbers (= North-Holland Mathematical Library. 31). 2. überarbeitete und erweiterte Auflage. North-Holland (u. a.), Amsterdam (u. a.) 1988, ISBN 0-444-86662-0.
  •  József Sándor, Dragoslav S. Mitrinović, Borislav Crstici: Handbook of Number Theory.. 2. Auflage. Band I, Springer-Verlag, Dordrecht, NL 2006, ISBN 978-1-4020-4215-7 (MR2186914).
  • Joachim Stiller: Materialien zur Mathematik VII - Prinzahlen PDF
  • Gerhard Kowol: Primzahlen
  • Lotte Volkmer: Zahlenphänomene

Weblinks

Commons-logo.png Commons: Primzahlen - Weitere Bilder oder Audiodateien zum Thema
 Wiktionary: Primzahl – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
 Wikibooks: Fundamentalsatz der Arithmetik – Lern- und Lehrmaterialien
 Wikibooks: Primzahlen von 2 bis 100.000 – Lern- und Lehrmaterialien

Einzelnachweise

  1. Armin Leutbecher: Zahlentheorie: Eine Einführung in die Algebra. Springer, 1996, ISBN 3-540-58791-8, S. 18, eingeschränkte Vorschau in der Google Buchsuche.
  2. Vaughan R. Pratt: Every Prime has a Succinct Certificate. PDF.
  3. Vašek Chvátal: Lecture notes on Pratt’s Primality Proofs. PDF.
  4. Der Satz von Vaughan Pratt als Theorem des Tages. PDF.
  5. Für Beweise des Satzes von Euklid siehe Beweisarchiv.
  6. Mersenne Prime Discovery – 277232917-1 is Prime! Abgerufen am 5. Januar 2018 (english).
  7. Rademacher-Toeplitz: S. 164.
  8. Sierpiński: S. 146.
  9.  Dressler-Pigno-Young: Nordisk Mat. Tidskr. 24, S. 39.
  10. Sándor-Mitrinović-Crstici: S. 247.
  11. Sierpiński: S. 145.
  12. 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).
  13. Sierpiński: S. 162.
  14. Aus (1e) ergibt sich, wie Sierpiński anmerkt, unmittelbar die Divergenz der Reihe LaTeX: \textstyle \sum_{k=1}^{\infty}{\frac{1}{p_k}}.
  15. Sierpiński: S. 163.
  16.  Rosser-Schoenfeld: Illinois J. Math. 6, S. 64 ff..
  17. Sierpiński: S. 163.
  18. Wie Sierpiński anmerkt, gelangt man mit (2b) unmittelbar zum Primzahlsatz.
  19. Sierpiński: S. 165.
  20. Dieses Ergebnis wurde gemäß Sierpiński zuerst von dem polnischen Mathematiker Hugo Steinhaus gewonnen.
  21. Sierpiński: S. 165.
Dieser Artikel basiert (teilweise) auf dem Artikel Primzahl aus der freien Enzyklopädie Wikipedia und steht unter der Lizenz Creative Commons Attribution/Share Alike. In Wikipedia ist eine Liste der Autoren verfügbar.