Primzahlen - Was ist das eigentlich?
Guten Abend miteinander ! :-)
Meine Tochter hat ja Teiler und Vielfache in der Schule. Ich habe sie dann mal gefragt, was Primzahlen eigentlich sind. Sie hat es mir erklärt, aber typisch ich, hab wieder die hälfte nicht vestanden. :-D
Könnt ihr mir vielleicht erklären, was Primzahlen sind?
Beste und Liebe Grüsse Bonniehit
14 Antworten
![](https://images.gutefrage.net/media/user/summerdream/1444744081_nmmslarge.jpg?v=1444744081000)
das sind zahlen,d ie nur durch 1 und sich selber teilbar sind. z.b 3, 7, 11, 13 (es zählen keine kommazahlen als teiler)
![](https://images.gutefrage.net/media/default/user/8_nmmslarge.png?v=1551279448000)
Ich will hier niemanden beleidigen; das Nachfolgende ist ein Fakt: Ihr habt keine Ahnung.
In einem Körper sind Zahlen wie 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... durch unendlich viele Zahlen teilbar. Wenn ihr nun sagt, dass Kommazahlen nicht als Teiler zählen oder von natürlichen Teilern spricht, ist die Definition immer noch falsch. Warum? Das beantworten euch folgende Antworten zu folgenden Fragen.
Was heißt teilbar?
Eine Zahl a ist durch b teilbar, falls a : b existiert. Man kann also sagen, dass 2 durch 3 teilbar ist, da 2 : 3 = 0,Periode 6 existiert.
Was ist eine Kommazahl?
Eine Kommazahl ist jede Zahl, die ein Komma besitzt. Ganze Zahlen gehören auch zu den Kommazahlen, da 1 zum Beispiel identisch mit 1,0 oder 0,Periode 9 ist.
Worauf will ich hinaus?
Wir müssen uns bei der Definition einer Primzahl auf einen Bereich beschränken. Die üblichste Definition einer Primzahl, beschränkt sich auf die Menge der natürlichen Zahlen.
Die Definition lautet: Eine Primzahl ist eine Zahl, die in Bezug auf die Teilbarkeit in der Menge der natürlichen Zahlen nur zwei Teiler besitzt.
Es gibt aber auch eine Verallgemeinerung der Definition, damit die Rede von Primzahlen in beliebigen Ringen sein kann: Eine Primzahl ist eine Zahl, falls sie die Faktoren a oder b teilt, wenn sie das Produkt aus diesen teilt und keine Einheit ist. Allerdings sprechen die meisten dann nicht mehr von den Primzahlen, sondern von den Primelementen. Aus morphologischer Sicht, sind beide Begriffe aber identisch, da Primelemente Zahlen sind und prim sind. Man kann also sagen: Primelemente sind prime Zahlen. Wie heißt der Begriff prime Zahlen aber als Adjektiv-Substantiv-Kompositum? Ganz genau: Primzahlen
Ob nun 2 eine Primzahl ist, hängt davon ab, wie man eine Primzahl definiert. Falls die übliche Definition zutrifft, dann ist sie eine Primzahl. Falls jedoch die verallgemeinerte Definition zutrifft, hängt es davon ab, auf welchen Bereich man sich beschränkt. In der Menge der natürlichen Zahlen ist die Zahl prim, in der Menge der ganzen gaußschen Zahlen jedoch nicht, da sie durch 1 + i und 1 - i teilbar ist. In einem Körper gibt es sogar keine Primzahlen. Wieso? Zur Beantwortung dieser Frage, verweise ich auf die Antwort auf die Frage Was heißt teilbar?.
![](https://images.gutefrage.net/media/user/toastbrot95/1444744043_nmmslarge.jpg?v=1444744043000)
Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst. Die kleinsten Primzahlen sind
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … (Folge A000040 in OEIS)
Das Wort „Primzahl“ kommt aus dem Französischen (nombre premier) und bedeutet „die erste Zahl“. Die fundamentale Bedeutung der Primzahlen für viele Bereiche der Mathematik beruht auf den folgenden drei Konsequenzen aus dieser Definition:
* Primzahlen lassen sich nicht als Produkt zweier natürlicher Zahlen, die beide größer als 1 sind, darstellen. Diese Eigenschaft kann auch als Definition des Begriffes Primzahl verwendet werden.
* Lemma von Euklid: Ist ein Produkt zweier natürlicher Zahlen durch eine Primzahl teilbar, so ist bereits einer der Faktoren durch sie teilbar.
* Eindeutigkeit der Primfaktorzerlegung: Jede natürliche Zahl lässt sich als Produkt von Primzahlen schreiben. Diese Produktdarstellung ist bis auf die Reihenfolge der Faktoren eindeutig.
Eine natürliche Zahl größer als 1 heißt prim, wenn sie eine Primzahl ist, andernfalls heißt sie zusammengesetzt. Die Zahlen 0 und 1 sind weder prim noch zusammengesetzt.
Bereits die antiken Griechen interessierten sich für die Primzahlen und entdeckten einige ihrer Eigenschaften. Obwohl sie über die Jahrhunderte stets einen großen Reiz auf die Menschen ausübten, sind bis heute viele die Primzahlen betreffenden Fragen ungeklärt.
Über zweitausend Jahre lang konnte man keinen praktischen Nutzen aus dem Wissen über die Primzahlen ziehen. Dies änderte sich erst mit dem Aufkommen elektronischer Rechenmaschinen, wo die Primzahlen beispielsweise in der Kryptographie eine zentrale Rolle spielen. Inhaltsverzeichnis [Verbergen]
* 1 Primfaktorzerlegung
o 1.1 Praktische Anwendung
o 1.2 Kryptographie
* 2 Eigenschaften von Primzahlen
o 2.1 Der kleine Satz von Fermat
o 2.2 Euler und das Legendre-Symbol
o 2.3 Binomialkoeffizient
o 2.4 Giuga
o 2.5 Lineare Rekursionen
o 2.6 Divergenz der Summe der Kehrwerte
o 2.7 Weiteres
* 3 Primzahltests
* 4 Größte bekannte Primzahl
* 5 Liste der Rekordprimzahlen nach Jahren
* 6 Verteilung der Primzahlen
* 7 Formeln zur Generierung von Primzahlen
* 8 Spezielle Primzahlen und Primzahlkonstellationen
* 9 Warum ist die Zahl 1 keine Primzahl?
* 10 Primzahllücken
* 11 Verallgemeinerung
* 12 Literatur
* 13 Weblinks
Primfaktorzerlegung [Bearbeiten]
→ Hauptartikel: Primfaktorzerlegung
Es gilt der Fundamentalsatz der Arithmetik: Jede positive ganze Zahl lässt sich bis auf die Reihenfolge eindeutig als Produkt von Primzahlen darstellen. Die in dieser Darstellung auftretenden Primzahlen nennt man die Primfaktoren der Zahl. Die Schwierigkeiten bei der Primfaktorzerlegung bezeichnet man als Faktorisierungsprobleme. Man versucht, sie mit geeigneten Faktorisierungsverfahren zu minimieren.
Aufgrund dieses Satzes, also dass sich jede natürliche Zahl 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 Elementen der Chemie weitgehend ähnlich.
Praktische Anwendung [Bearbeiten]
Aus der Primfaktorenzerlegung lässt sich erkennen, ob eine Zahl durch eine andere teilbar ist. Das kleinste gemeinsame Vielfache kgV und der größte gemeinsame Teiler ggT können leicht aus der Primfaktorenzerlegung bestimmt werden. In der Bruchrechnung können Brüche durch den ggT von Zähler und Nenner gekürzt werden, und zwei Brüche können auf den kleinsten gemeinsamen Nenner erweitert werden, um leichter addieren oder subtrahieren zu können.
Kryptographie [Bearbeiten]
Eine wichtige Rolle spielen Primzahlen in der Kryptographie. Verschlüsselungssysteme wie RSA basieren darauf, dass kein effizientes Faktorisierungsverfahren bekannt ist. So ist es innerhalb von Sekunden problemlos möglich, zwei 500-stellige Primzahlen zu finden und miteinander zu multiplizieren. Mit den heutigen Methoden würde die Rückgewinnung der beiden Primfaktoren aus diesem 999-stelligen oder 1000-stelligen Produkt dagegen sehr lange Zeit dauern. Primzahlen werden auch bei der Programmierung von Hashtabellen verwendet.
Eigenschaften von Primzahlen [Bearbeiten]
Mit Ausnahme der Zahl 2 sind alle Primzahlen 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 2k + 1 mit einer natürlichen Zahl k.
Jede Primzahl mit Ausnahme der 2 lässt sich einer der beiden Klassen „Primzahl der Form 4k + 1“ oder „Primzahl der Form 4k + 3“ zuordnen, wobei k eine natürliche Zahl ist. Darüber hinaus hat jede Primzahl p > 3 die Form p = 6k + 1 oder p = 6k − 1, wobei 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 4m + 3 mit einer nichtnegativen ganzen Zahl m enthält mindestens einen Primfaktor der Form 4k + 3. Eine entsprechende Aussage über Zahlen der Form 4m + 1 oder Primfaktoren der Form 4k + 1 ist nicht möglich.
Eine Primzahl p > 2 lässt sich genau dann in der Form a2 + b2 mit ganzen Zahlen a,b schreiben, wenn p die Form 4k + 1 hat. In diesem Fall ist die Darstellung im wesentlichen eindeutig, d.h. bis auf Reihenfolge und Vorzeichen von a,b. Diese Darstellung entspricht der Primfaktorzerlegung
p = (a + bi)(a − bi)
im Ring der ganzen gaußschen Zahlen.
Die Zahl −1 ist ein quadratischer Rest modulo jeder Primzahl der Form 4k + 1 und quadratischer Nichtrest modulo jeder Primzahl der Form 4k + 3.
Der kleine Satz von Fermat [Bearbeiten]
Es sei p eine Primzahl. Für jede ganze Zahl a, die nicht durch p teilbar ist, gilt (für die Notation siehe Kongruenz):
a^{p-1} \equiv 1 \mod p.
Eine äquivalente Formulierung lautet: Für jede ganze Zahl a gilt
a^p\equiv a\mod p.
Es gibt Zahlen, die keine Primzahlen sind, sich aber dennoch zu einem Teil der Basen a wie Primzahlen verhalten und somit den kleinen Satz von Fermat erfüllen. Solche Nichtprimzahlen nennt man fermatsche Pseudoprimzahlen. Pseudoprimzahlen, die pseudoprim zu allen Basen a sind, welche nicht Teiler dieser Pseudoprimzahlen sind, nennt man Carmichael-Zahlen.
Besonders in diesem Zusammenhang zeigt sich die Problematik von Pseudoprimzahlen: Sie werden von Algorithmen, die den kleinen Satz von Fermat nutzen, um festzustellen, ob eine bestimmte Zahl prim ist, 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 Primzahltests verwendet werden, die mit einer sehr hohen Wahrscheinlichkeit Primzahlen von zusammengesetzten Zahlen unterscheiden können. Diese Wahrscheinlichkeit ist bei Verwendung des kleinen Satzes von Fermat als Basis allein nicht hoch genug, es gibt aber sicherere Primzahltests.
Euler und das Legendre-Symbol [Bearbeiten]
Eine einfache Folge aus dem kleinen Satz von Fermat ist die folgende Aussage: Für jede ungerade Primzahl p und jede ganze Zahl a, die nicht durch p teilbar ist, gilt entweder
a^{\frac{p-1}{2}} \equiv 1 \mod p
oder
a^{\frac{p-1}{2}} \equiv -1 \mod p.
Man kann zeigen, dass der erste Fall genau dann eintritt, wenn es eine Quadratzahl m2 gibt, die kongruent zu a modulo p ist, siehe Legendre-Symbol.
Binomialkoeffizient [Bearbeiten]
Für Primzahlen p und 1\leq k\leq p-1 gilt
p\,\Big|{p\choose k};
zusammen mit dem binomischen Satz folgt daraus
(a+b)^p\equiv a^p+b^p\mod p.
Für ganze Zahlen 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 x\mapsto x^p in Ringen der Charakteristik p ein Homomorphismus ist, der so genannte Frobenius-Homomorphismus.
Aus dem Satz von Wilson (p ist genau dann eine Primzahl, wenn (p-1)! \equiv -1 \pmod p ist) folgt, dass für jede Primzahl p und jede natürliche Zahl n die Kongruenz
{{np-1}\choose{p-1}} \equiv 1 \pmod{p}
erfüllt ist.
Charles Babbage bewies 1819, dass für jede Primzahl p > 2 diese Kongruenz gilt:
{{2p-1}\choose{p-1}} \equiv 1 \pmod{p^2}
Der Mathematiker Joseph Wolstenholme (1829–1891) bewies dann 1862, dass für jede Primzahl p > 3 die folgende Kongruenz gilt:
{{2p-1}\choose{p-1}} \equiv 1 \pmod{p^3}
Giuga [Bearbeiten]
Aus dem kleinen Satz von Fermat folgt, dass für eine Primzahl p gilt: 1^{p-1} + 2^{p-1} + ... + (p-1)^{p-1} \equiv -1 \pmod{p}
Beispiel p = 5:
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 [Bearbeiten]
Den kleinen fermatschen Satz kann man auch in der Form lesen: In der Folge an − a ist das p-te Folgenglied für eine Primzahl p stets durch p teilbar. Ähnliche Eigenschaften besitzen auch andere Folgen von exponentiellem Charakter, wie die Lucas-Folge (p\mid Lp-1) und die Perrin-Folge (p\mid Pp). Für andere lineare Rekursionen gelten analoge, aber kompliziertere Aussagen, beispielsweise für die Fibonacci-Folge (fn){n=0,1,2,\ldots}=0,1,1,2,3,5,\ldots: Ist p eine Primzahl, so ist f_p-\Big(\frac p5\Big) durch p teilbar; dabei ist
\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 [Bearbeiten]
Die Folge der Summe der Kehrwerte der Primzahlen bis hin zu einer bestimmten Primzahl pn (an=\sum{i=1}^{n} \frac{1}{p_i}) hat keinen Grenzwert. Das bedeutet, für ein genügend großes n lässt sich jede erdenkliche reelle Zahl übertreffen. Dies ist zunächst einmal verblüffend, da die Primzahllücken im Schnitt immer weiter zunehmen.
Weiteres [Bearbeiten]
Zwei natürliche Zahlen, deren Summe eine Primzahl ergibt, sind immer teilerfremd. Umgekehrt zeigt jedoch das einfache Gegenbeispiel 3 + 5 = 8, dass die Summe zweier teilerfremder Zahlen nicht zwingend eine Primzahl ergibt.
Primzahltests [Bearbeiten]
→ Hauptartikel: Primzahltest
Ob eine Zahl eine Primzahl ist, kann man mit einem Primzahltest entscheiden. Es gibt mehrere solcher Verfahren, deren Grundlagen meist besondere Eigenschaften von Primzahlen sind. 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, Zahlen in polynomialer Laufzeit zu testen. Allerdings ist er in der Praxis deutlich langsamer als der Miller-Rabin-Test.
Größte bekannte Primzahl [Bearbeiten]
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: Ausgehend von der Annahme, dass es nur endlich viele Primzahlen gibt, lässt sich die Existenz weiterer folgern, 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, siehe Beweisarchiv.
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, so dass es stets eine größte bekannte Primzahl gab, seitdem sich die Menschen mit Primzahlen befassen. Derzeit ist es 243.112.609 − 1, eine Zahl mit 12.978.189 (dezimalen) Stellen, die am 23. August 2008 auf einem Computer der mathematischen Fakultät an der University of California, Los Angeles, gefunden wurde. Der Verantwortliche für die Computer der Fakultät, Edson Smith, hatte das Programm des GIMPS-Projekts als Bildschirmschoner auf den Rechnern der Fakultät eingerichtet. Die Entdeckung dieser Primzahl qualifiziert sich mit mehr als 10 Millionen Dezimalstellen für den von den von der Electronic Frontier Foundation ausgeschriebenen Preis von 100.000 US-Dollar.
Die größte bekannte Primzahl war fast immer eine Mersenne-Primzahl, also von der Form 2n − 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 diesen oder eines ähnlich geeigneten Typs auf Primalität untersucht.
Liste der Rekordprimzahlen nach Jahren [Bearbeiten] Zahl Ziffernanzahl (im Dezimalsystem) 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) 21279-1 386 1952 Robinson (SWAC) 22203-1 664 1952 Robinson (SWAC) 22281-1 687 1952 Robinson (SWAC) 23217-1 969 1957 Riesel (BESK) 24423-1 1332 1961 Hurwitz (IBM7090) 29689-1 2917 1963 Gillies (ILLIAC 2) 29941-1 2993 1963 Gillies (ILLIAC 2) 211213-1 3376 1963 Gillies (ILLIAC 2) 219937-1 6002 1971 Tuckerman (IBM360/91) 221701-1 6533 1978 Noll & Nickel (CDC Cyber 174) 223209-1 6987 1979 Noll (CDC Cyber 174) 244497-1 13395 1979 Nelson & Slowinski (Cray 1) 286243-1 25962 1982 Slowinski (Cray 1) 2132049-1 39751 1983 Slowinski (Cray X-MP) 2216091-1 65050 1985 Slowinski (Cray X-MP/24) 2216193-1 65087 1989 „Amdahler Sechs“ (Amdahl 1200) 2756839-1 227832 1992 Slowinski & Gage (Cray 2) 2859433-1 258716 1994 Slowinski & Gage (Cray C90) 21257787-1 378632 1996 Slowinski & Gage (Cray T94) 21398269-1 420921 1996 Armengaud, Woltman (GIMPS, Pentium 90 MHz) 22976221-1 895932 1997 Spence, Woltman (GIMPS, Pentium 100 MHz) 23021377-1 909526 1998 Clarkson, Woltman, Kurowski (GIMPS, Pentium 200 MHz) 26972593-1 2098960 1999 Hajratwala, Woltman, Kurowski (GIMPS, Pentium 350 MHz) 213466917-1 4053946 2001 Cameron, Woltman, Kurowski (GIMPS, Athlon 800 MHz) 220996011-1 6320430 2003 Shafer (GIMPS, Pentium 4 2 GHz) 224036583-1 7235733 2004 Findley (GIMPS, Pentium 4 2,4 GHz) 225964951-1 7816230 2005 Nowak (GIMPS, Pentium 4 2,4 GHz) 230402457-1 9152052 2005 Cooper, Boone (GIMPS, Pentium 4 3 GHz) 232582657-1 9808358 2006 Cooper, Boone (GIMPS) 243112609-1 12978189 2008 Smith, Woltman, Kurowski, et al (GIMPS)
Verteilung der Primzahlen [Bearbeiten]
Zur Untersuchung der Verteilung der Primzahlen betrachtet man unter anderem die Funktion
\pi:\Bbb N\to \Bbb N,\;n\mapsto\pi(n),
die die Anzahl der Primzahlen \leq n angibt. Zum Beispiel ist
\pi(10) = 4\ ;\ \pi(100) = 25\ ;\ \pi(1000) = 168 .
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
\pi(x) \sim \frac{x}{\ln x}
gilt, d.h. dass der Quotient von linker und rechter Seite für x\to\infty gegen 1 strebt.
Der dirichletsche Primzahlsatz dagegen schränkt die Betrachtung auf Restklassen ein: Es sei m eine natürliche Zahl. Ist a eine ganze Zahl, die zu m nicht teilerfremd ist, so kann die arithmetische Folge
a,a+m,a+2m,a+3m,\ldots
höchstens eine Primzahl enthalten, weil alle Folgenglieder durch den größten gemeinsamen Teiler von a und m teilbar sind. Ist a aber teilerfremd zu m, so besagt der dirichletsche Primzahlsatz, dass die Folge unendlich viele Primzahlen enthält. Beispielsweise gibt es unendlich viele Primzahlen der Form 4k + 1 und unendlich viele der Form 4k + 3 (k durchläuft jeweils die nichtnegativen natürlichen Zahlen).
Diese Aussage kann noch in der folgenden Form präzisiert werden: Es gilt
\lim_{x\to\infty}\frac{\#\{p\ \mathrm{prim},\ p\leq x\ \mathrm{und}\ p\equiv a\pmod m\}}{\#\{p\ \mathrm{prim},\ p\leq x\}}=\frac1{\phi(m)};
dabei ist φ(m) die eulersche φ-Funktion. In diesem Sinne liegen also für ein festes m in den Restklassen a+m\mathbb Z mit ggT(a,m) = 1 jeweils „gleich viele“ Primzahlen.
Siehe auch: Ulam-Spirale
Formeln zur Generierung von Primzahlen [Bearbeiten]
Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes, bei dem nacheinander aus einer Liste der natürlichen Zahlen >1 die Zahlen gestrichen werden, die Vielfache der jeweils kleinsten noch nicht gestrichenen Zahl sind. Dadurch bleiben die Primzahlen innerhalb der Ausgangsliste übrig.
Man kennt keine Formel, die eine effiziente, direkte Berechnung der n-ten Primzahl ermöglichen würde. Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen eine Primzahl sein könnten. Trotzdem müssen die erzeugten Zahlen auf ihre Eigenschaft als Primzahl getestet werden.
Schon Euler gab die Formeln n2 + n + 17 und n2 − n + 41 an, die für 0 < n < 16 bzw. 0 < n < 41 Primzahlen liefern. Auch für größere Werte von n liefern die beiden Formeln viele Primzahlen, weil das Ergebnis nie durch Primzahlen p < 17 bzw. p < 41 ganzzahlig teilbar ist. Allgemein gibt es viele solche Formeln an2 + bn + c, wodurch sich die auffällige Ulam-Spirale erklärt.
Die beliebteste ist die der Mersenne-Zahl Mn = 2n − 1 bei der Mn eine Primzahl ist. Durch die besonderen Eigenschaften der Teiler von Mersenne-Zahlen eignen sie sich für die Suche nach möglichst großen Primzahlen.
Fermat vermutete, dass alle Zahlen der Form 2^{2^n}+1 prim sind; man nennt sie Fermat-Zahlen. Tatsächlich ist aber für n > 4 keine derartige Primzahl bekannt.
Auch bekannt ist eine Anwendung des Satzes von Euklid, bei der auf das Primorial eine 1 aufaddiert wird:
p\# + 1 = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1
Hierbei werden alle aufeinanderfolgenden Primzahlen von 2 bis pn = p miteinander multipliziert.
p# + 1 ist prim für p = 2, 3, 5, 7, 11, 31, 379, 1019, 1021, …
Weitere Formeln:
* n! − 1 ist prim für n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, … (Folge A002982 in OEIS)
* n! + 1 ist prim für n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154 …
* Primzahlen der Form kgV(1,…,n)+1 sind: 2, 3, 7, 13, 61, 421, 2521, 232792561, …
Spezielle Primzahlen und Primzahlkonstellationen [Bearbeiten]
* Primzahlzwillinge
* Primzahldrillinge
* Primzahlvierlinge
* Primzahlsechslinge
* Wall-Sun-Sun-Primzahlen
* Cullen- und Woodall-Zahlen
* Cunningham-Ketten
* Prothsche Primzahlen
* glückliche Primzahlen
* Mersenne-Primzahlen
* Sophie-Germain-Primzahlen
Weitere spezielle Arten von Primzahlen finden sich in der Kategorie:Primzahl.
Warum ist die Zahl 1 keine Primzahl? [Bearbeiten]
Die einfachste Antwort auf die Frage, warum die 1 keine Primzahl ist, folgt aus der Definition:
* Eine natürliche Zahl wird dann Primzahl genannt, wenn sie durch genau zwei natürliche Zahlen teilbar ist. Die Zahl 1 ist aber nur durch eine natürliche Zahl, nämlich die Zahl 1, teilbar. Deshalb ist sie per definitionem keine Primzahl.
Die folgenden Antworten gehen auf den Zweck dieser Definition ein:
* Damit man eine eindeutige Primfaktorzerlegung bekommt (man hätte sonst beliebig viele 1-Faktoren darin).
* Weil 1 eine Einheit ist (siehe den Artikel Primelement).
* Weil man ansonsten bei nahezu allen Aussagen über Primzahlen schreiben müsste: „Für alle Primzahlen mit Ausnahme der 1 gilt…“. Beispielsweise in der Theorie der endlichen Körper.
Die Frage, ob 1 eine Primzahl ist, ist aber letztlich keine Frage von wahr oder von falsch, sondern von zweckmäßig oder nicht zweckmäßig, so wie beispielsweise auch die Frage, ob „Null hoch null“ definiert ist.
Siehe hierzu auch: Wikibooks: Warum 1 keine Primzahl ist
Primzahllücken [Bearbeiten]
→ Hauptartikel: Primzahllücke
Die Differenz zwischen zwei benachbarten Primzahlen heißt Primzahllücke. Diese Differenz schwankt, und obwohl es unendlich viele Primzahlen gibt, lassen sich Primzahllücken mit einer frei wählbaren Mindestgröße finden.
Verallgemeinerung [Bearbeiten]
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.
Literatur [Bearbeiten]
* Paulo Ribenboim: The New Book of Prime Number Records. 3. Aufl., Springer Verlag, New York 1996, ISBN 0-387-94457-5.
* Marcus du Sautoy: Die Musik der Primzahlen. Auf den Spuren des größten Rätsels der Mathematik. Verlag C.H.Beck, München 2004, ISBN 3-406-52320-X.
* Władysław Narkiewicz: The Development of Prime Number Theory. Springer-Verlag, Berlin 2000, ISBN 3-540-66289-8.
dürfte reichen^^
![](https://images.gutefrage.net/media/default/user/9_nmmslarge.png?v=1551279448000)
Wenn Du schon kopierst, dann gib doch bitte den Link an und formatiere so, dass alles problemlos lesbar ist, hm? :-)
![](https://images.gutefrage.net/media/default/user/8_nmmslarge.png?v=1551279448000)
Eine Zahl, die nur durch sich selbst und durch 1 zu dividieren ist.
![](https://images.gutefrage.net/media/default/user/10_nmmslarge.png?v=1551279448000)
Eine Zahl die nur durch 1 und sich selbst teilbar ist. Sprich: 2 Teiler hat. Die Eins jedoch hat nur eins in ihrer Teilermenge und ist somit keine Primzahl.
Die ersten Primzahlen bis 10 000:
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999,
2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999,
3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989,
4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999,
5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987,
6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997,
7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993,
8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999,
9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973.
Aus http://primzahlen.zeta24.com/de/primzahltabelle100-000.php