WikiDer > Primzahl

EIN Primzahl ist ein natürliche Zahl größer als 1, die nur zwei natürliche Zahlen hat, wenn Divisor hat, nämlich 1 und sich selbst. Die kleinste Primzahl ist also 2, weil sie nur 1 und 2 als Teiler hat. Die nächste ist 3, mit nur den Teilern 1 und 3. Die Zahl 4 ist keine Primzahl, sie hat neben 1 und 4 auch 2 als Teiler. Eine Zahl größer als 1, die keine Primzahl ist, heißt a zusammengesetzte Zahl. Primzahlen sind ein wichtiges Thema im Teilgebiet der Mathematik Welche Zahlentheorie wird genannt.

Aufgrund der Übereinstimmung, dass die Zahl 1 keine Primzahl ist, Hauptsatz der Arithmetik einfacher formuliert werden.

Die ersten 30 Primzahlen sind 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 und 113.^[1]

Primzahlen wurden bereits von den Antike Griechen studiert. Es gibt unendlich viele Primzahlen. Es Beweis dafür ist gegeben durch die Satz von Euklid. Die älteste Methode zum Finden von Primzahlen ist die Sieb von Eratosthenes, die im Animation unten abgebildet.

Eine bestimmte Art von Primzahlen wird gebildet durch die Mersenne-Primzahlen. Von einer Mersenne-Zahl, also einer Zahl der Form ${Displaystil 2^{n}-1}$, ist es relativ einfach zu bestimmen, ob es eine Primzahl ist oder nicht.

Es gibt keine bekannte Formel für alle Primzahlen, aber nein Zusammengesetzte Zahlen ergibt. Die Verteilung der Primzahlen, also die statistisch Das Verhalten einer großen Anzahl von Primzahlen kann jedoch modelliert werden. Das erste Ergebnis in diese Richtung war der Primzahlsatz, die grob gesagt aussagt, dass die Wahrscheinlichkeit, dass eine zufällig gewählte Zahl ${displaystyle n}$ eine Primzahl ist, die umgekehrt proportional zur Anzahl der Stellen ist, oder die Logarithmus von ${displaystyle n}$. Dieser Satz wurde Ende des 19. Jahrhunderts bewiesen. das unbewiesene Riemann-Hypothese, aus dem Jahr 1859, impliziert eine ausgefeilte Erklärung dafür im Hinblick auf die Verteilung der Primzahlen.

Trotz intensiver Studien sind noch viele grundlegende Fragen zu Primzahlen offen. Zum Beispiel die Goldbachs Vermutung, die behauptet, dass jede gerade Zahl größer als zwei die Summe zweier Primzahlen ist, und die Vermutung von Zwillingsprimzahlen, die besagt, dass es unendlich viele Primzahlzwillinge (Primzahlenpaare, deren Unterschied gleich zwei) muss trotz der scheinbaren Einfachheit dieser Aussagen seit über einem Jahrhundert ungelöst existieren.

Primzahlen werden in verschiedenen Teilen des angewendet Informationstechnologie, auch bei der Sicherung digitaler Informationen, durch Kryptographie. Mit Hilfe von Primzahltest bestimmt, dass eine Zahl eine Primzahl ist. In dem asymmetrische Kryptographie Zum Beispiel nutzt es die Schwierigkeit aus, große Zahlen in ihre Primfaktoren zu Faktor. Die Suche nach extrem großen Primzahlen, oft mit verteiltes Rechnen, hat das Studium der Primzahlen angeregt. Anfang 2013 bestand die größte bekannte Primzahl aus 17 425 170 Stellen.^[2] Im Jahr 2018 wurde die bisher größte Primzahl entdeckt, die vollständig aus 24 862 048 ausgeschriebenen Ziffern besteht.^[3]

Das Sieb von Eratosthenes kann verwendet werden, um Primzahlen zu finden.

Primzahlen und der Fundamentalsatz der Arithmetik

sehen Hauptsatz der Arithmetik für den Hauptartikel zu diesem Thema.

Die entscheidende Bedeutung der Primzahlen für die Zahlentheorie und Mathematik im Allgemeinen stammt aus dem Fundamentalsatz der Arithmetik. Primzahlen können als die „Bausteine“ der natürlichen Zahlen betrachtet werden. Beispielsweise,

${displaystyle 23244=2cdot 2cdot 3cdot 13cdot 149=2^{2}cdot 3cdot 13cdot 149quad }$ (${Displaystil 2^{2}}$ bezeichnet es Quadrat von 2 bis).

Wie in diesem Beispiel zu sehen ist, kann dieselbe Primzahl mehr als einmal vorkommen. Die Reihenfolge der Primzahlen ist nicht wichtig. Umschreiben einer natürlichen Zahl ${displaystyle n}$ als Produkt der Primzahlen

${displaystyle n=p_{1}cdot p_{2}cdot ldots cdot p_{t}}$

heißt die Auflösung von ${displaystyle n}$ in Primfaktoren. Obwohl es verschiedene gibt Algorithmen um eine Zahl in Primfaktoren zu zerlegen, insbesondere bei größeren Zahlen, geben sie alle die gleichen Primzahlen.

Das Sammlung aller Primzahlen wird bezeichnet durch ${displaystyle mathbb {P} }$.

Beispiele und erste Eigenschaften

Abbildung zeigt, dass 11 eine Primzahl ist, während 12 keine Primzahl ist

Die einzige gerade Primzahl ist 2, da jede gerade Zahl größer als zwei per Definition durch 2 teilbar ist. Daher bezieht sich der Begriff ungerade Primzahl auf jede Primzahl größer als 2.

Das Bild rechts zeigt grafisch, dass 12 keine Primzahl ist. Primzahlen, wie üblich geschrieben Dezimalsystem, mit Ausnahme von 2 und 5, enden mit einer 1, einer 3, einer 7 oder einer 9. Das ist nicht so seltsam, denn alle Zahlen, die auf 0, 2, 4, 6 oder 8 enden, haben a mehrere von 2 und alle Zahlen, die auf 0 oder 5 enden, sind ein Vielfaches von 5. Auch alle Primzahlen über 3 der Form ${Anzeigestil 6n-1}$ oder ${Anzeigestil 6n 1}$, weil alle anderen Zahlen durch 2 oder 3 teilbar sind. Alle Primzahlen größer als ${Anzeigestil q}$ sind von der bilden${displaystyle qnm}$, bei welchem ${Anzeigestil 0$ und ${displaystyle m}$ hat keinen Primfaktor gemeinsam mit ${Anzeigestil q}$ oder mit ${displaystyle n}$.

wenn ${displaystyle p}$ ist eine Primzahl und ${displaystyle p}$ Teiler eines Produkts ${displaystyle ab}$ von ganzen Zahlen, dann ist ${displaystyle p}$ Teiler von ${Anzeigestil a}$, von ${displaystyle b}$ oder von ${Anzeigestil a}$ und ${displaystyle b}$ beide. Dies ist bekannt als die Euklids Lemma. Es wird verwendet, um zu beweisen, dass eine Zahl nur auf eine Weise faktorisiert werden kann.

Die Pythagoräer entdeckten vor 400 v. etwas Besonderes an bestimmten Zahlen. Stellen Sie eine Zahl durch eine entsprechende Anzahl von Steinen dar, dann können die zusammengesetzten Zahlen als Rechteck angeordnet werden. Zum Beispiel kann die Zahl 12 als Rechteck von 3 mal 4 Steinen angeordnet werden. Eine Primzahl kann jedoch nicht als reelles Rechteck (im Gegensatz zu einer Zeile) angeordnet werden. Wie auch immer Sie es versuchen, 11 Steine ​​können nicht in einem Rechteck platziert werden.

1 ob Primzahl oder nicht not

Wäre 1 als Primzahl erlaubt, so Hauptsatz der Arithmetik sollte weniger einfach formuliert werden, weil dann eine beliebige Zahl von Einsen zur Primfaktorzerlegung einer Zahl hinzugefügt werden könnte.^[4][5]

Bis ins 19. Jahrhundert betrachteten die meisten Mathematiker die Zahl 1 als Primzahl. Die Definition war, dass eine Primzahl nur durch 1 und sich selbst teilbar sein darf, aber es gab keine Beschränkungen hinsichtlich der Anzahl der verschiedenen Teiler. Es gibt noch viele mathematische Arbeiten, die noch gültig sind, obwohl die Zahl 1 damals als Primzahl galt, wie etwa die Arbeit von Stern und Zeisel. Derrick Norman LehmersListe der Primzahlen bis 10.06.721, die erst 1956 nachgedruckt wurde^[6] begann mit 1 als erster Primzahl.^[7] Von Henri Lebesgue Er soll der letzte professionelle Mathematiker sein, der 1 unter den Primzahlen zählt.

Die Primzahlen haben Eigenschaften, die nicht für 1 gelten, wie zum Beispiel die Beziehung der Zahl zu ihrem entsprechenden Wert der Euler-Totient-Funktion, oder die "Summen-der-Teiler-Funktion".^[8]

Faktorisierung in Primfaktoren

Das Hauptsatz der Arithmetik sagt das jeder natürliche Zahl größer als 1 auf eine Weise in Primfaktoren ist zerlegbar, d.h. kann so geschrieben werden Produkt von Primzahlen. Es gibt verschiedene Algorithmen um eine Zahl zu faktorisieren, wie zum Beispiel:

• die Trial-Methode (manchmal auch "Trial-Division-Methode" genannt)
• Pollards p-1-Methode,
• es Algorithmus von Lenstra
• es Dixons Algorithmus.

Testmethode

Der einfachste Weg zu einer Nummer ${displaystyle n}$ Die Primfaktorzerlegung ist die Versuchsmethode, obwohl sie nicht sehr effizient ist. Die Methode läuft auf Primzahlen kleiner oder gleich hinaus ${displaystyle {sqrt {n}}}$, um vom kleinsten zum größten auf Teilbarkeit zu testen auf test ${displaystyle n}$. Es stellt sich heraus, dass es sich um eine bestimmte Primzahl handelt ${displaystyle p}$ teilbar auf ${displaystyle n}$, dann muss ${Anzeigestil n/p}$ weiter auf Teilbarkeit untersucht werden, beginnend mit der Primzahl ${displaystyle p}$ und weiter bis ${displaystyle {sqrt {n/p}}}$.

Beispiele

• Wenn wir 98 in Primfaktoren zerlegen, betrachten wir zuerst Primzahlen kleiner oder gleich ${displaystyle {sqrt {98}}}$ (also weniger als 10). 98 ist teilbar durch 2: 98 = 2 · 49. Dann betrachten wir Primzahlen kleiner oder gleich ${displaystyle {sqrt {49}}=7}$, als Teiler von 49. Dann stellt sich heraus, dass 49 = 7 · 7. In Primfaktoren zerlegt ist 98 = 2 · 7 · 7.
• Wenn 143 in Primfaktoren zerlegt wird, betrachten wir Primzahlen kleiner oder gleich ${displaystyle {sqrt {143}}}$, also Primzahlen bis 11. Es stellt sich heraus, dass 143 nicht durch 2, 3, 5 oder 7 teilbar ist, sondern durch 11 teilbar ist, denn 143 = 11 · 13. Die Zahl 13 ist auch eine Primzahl, also in Primfaktoren eingerechnet ist 143 = 11 · 13.

Die Zahl der Primzahlen

sehen Satz von Euklid für den Hauptartikel zu diesem Thema.

Es gibt unendlich viele Primzahlen. Der älteste bekannte Beweis für diese Aussage, die manchmal auch als bezeichnet wird Satz von Euklid, wird dem zugeschrieben Altgriechisch Mathematiker Euklid. Euklid drückte sein Ergebnis wie folgt aus: "Es gibt mehr als jede gegebene [endliche] Anzahl von Primzahlen". Sein Beweis sieht im Wesentlichen so aus:

Betrachten Sie a endliche Menge von Primzahlen, zum Beispiel 3, 5, 37. Multiplizieren Sie alle diese Primzahlen und addieren Sie 1 zu diesem Ergebnis. Die resultierende Zahl, 3×5×37 1=556, ist nun durch keine der Primzahlen aus der endlichen Menge teilbar, die mit begonnen hat, da dies immer einen Rest von 1 ergibt. Da alle Nicht-Primzahlen als Produkt von Primzahlen geschrieben werden können, ist entweder diese resultierende Zahl selbst eine Primzahl oder es muss eine Primzahl geben, die die resultierende Zahl teilbar macht, jedoch nicht in der ursprünglichen endlichen Menge von Primzahlen, die begann. Wie auch immer, es gibt immer noch mindestens eine Primzahl, die nicht Teil der endlichen Menge war, mit der wir begonnen haben. Dieses Argument gilt unabhängig von der endlichen Menge, mit der das Argument gestartet wird. Es gibt also immer mehr Primzahlen als jede endliche Zahl. (Euklid, Elemente: Buch IX, Proposition 20)

Euklids Argument besagt, dass wenn ${displaystyle p}$ ist das Produkt einer endlichen Anzahl von Primzahlen, die Zahl ${displaystyle p1}$ muss durch eine Primzahl (möglicherweise sich selbst) teilbar sein, die nicht Teil der ursprünglichen Zahl ist.

Die Beweise sind manchmal so formuliert, dass die Leser fälschlicherweise glauben, dass ${displaystyle p1}$ selbst muss prim sein. Sie glauben, dass Euklids Beweis besagt, dass das Primprodukt plus 1 selbst immer prim ist. Diese Verwirrung entsteht, wenn die Beweise als Beweis durch Widerspruch Angenommen, es gibt nur endlich viele Primzahlen. Die Nummer ${displaystyle p}$ ist das Produkt all dieser Primzahlen und daraus wird geschlossen, dass weil ${displaystyle p1}$ durch keine Primzahl teilbar ist, ist sie selbst eine Primzahl, was einen Widerspruch impliziert (Zitat G. H. winterhart^[9]). Dies führt manchmal zu der irrigen Schlussfolgerung, dass wenn ${displaystyle p}$ es Produkt der ersten ${displaystyle n}$ Primzahlen ist die Zahl ${displaystyle p1}$ ist auch eine Primzahl. Diese Schlussfolgerung beruht auf einer Hypothese, die sich später als falsch herausstellt und daher nicht als bewiesen gelten kann. Das kleinste Gegenbeispiel mit a zusammengesetzte Zahl${displaystyle p1}$ ist:

${Anzeigestil 2cdot 3cdot 5cdot 7cdot 11cdot 13 1=30031=59cdot 509}$

Die Zahlen 59 und 509 sind beides Primzahlen, die nicht in der Originalfolge vorkommen.

Es gibt noch viele weitere Beweise für die Unendlichkeit der Zahl der Primzahlen. Einer ist, dass die Summe der gegenseitig aller Primzahlen ergibt a abweichendSerie, also muss es mehr als endlich viele Primzahlen geben

${displaystyle sum _{p{ ext{ prime}}}{frac {1}{p}}={frac {1}{2}} {frac {1}{3}} {frac {1}{5}} {frac {1}{7}} ldots =infty }$

Der Beweis dafür kommt von Euler. Genauer gesagt: wenn ${Anzeigestil S(x)}$ bezeichnet die Summe der Kehrwerte aller Primzahlen ${displaystyle p}$ mit ${displaystyle pleq x}$, dann gilt das^[10]

${Anzeigestil S(x)=ln ln x O(1)}$ vor dem ${displaystyle x o infty quad }$ (${Anzeigestil O}$ steht für die Groß-O-Notation).

Ein weiterer Beweis, basierend auf Eigenschaften von Fermat-Primzahlen war von Goldbach^[11] gegeben.Kummers Beweis ist sehr elegant^[12] und Harry Fürstenberg gibt seine Nachweis von Fürstenberg über die Unendlichkeit der Anzahl der Primzahlen mit dem allgemeinen Topologie.^[13]

Es gibt nicht nur unendlich viele Primzahlen, die Satz von Dirichlet über arithmetische Folgen besagt, dass in jedem arithmetische Zeile${Anzeigestil a,a q,a 2q,a 3q,ldots }$ wobei die positiven ganzen Zahlen ${Anzeigestil a}$ und ${Anzeigestil q}$relativ prim es gibt unendlich viele Primzahlen. Das Kürzliche Grün-Tao .Theorem zeigt, dass es arithmetische Folgen von Primzahlen beliebiger Länge gibt.^[14]

Primzahlüberprüfung

sehen Primzahltest für den Hauptartikel zu diesem Thema.

Um Primzahlen zu verwenden, ist Überprüfung dass eine bestimmte Zahl nein ob es prim ist oder nicht, ist entscheidend. Es gibt mehrere Möglichkeiten, dieses Ziel zu erreichen. EIN Sieb ist ein Algorithmus das ergibt alle Primzahlen bis zu einem bestimmten Grenzwert. Das älteste derartige Sieb ist das Sieb von Eratosthenes (siehe oben). Das Sieb von Erasthones ist für relativ kleine Primzahlen nützlich. das moderne Sieb von Atkin ist komplizierter, aber bei richtiger Optimierung auch schneller. Vor dem Aufkommen der Computer wurden oft Listen von Primzahlen bis zu einer Grenze von 10 verwendet⁷.^[15]

In der Praxis möchte man oft direkt prüfen, ob eine gegebene Zahl eine Primzahl ist oder nicht, anstatt zuerst a Liste der Primzahlen wie bei den beiden oben erwähnten Siebalgorithmen. Die einfachste Methode dafür, besser bekannt als Probeabteilung, funktioniert so: mit einer Zahl ${displaystyle n}$, Teilen ${displaystyle n}$ durch alle Zahlen ${displaystyle m}$, kleiner oder gleich Wurzel der Zahl, ${displaystyle n}$. Wenn eine der Divisionen eine ganze Zahl ergibt, ist die ursprüngliche Zahl keine Primzahl, andernfalls ist sie eine Primzahl. In der Praxis reicht es aus, diese Testteilung für ${displaystyle m}$ Primzahlen zu machen. Obwohl es sich um einen einfachen Algorithmus handelt, wird es schnell unpraktisch zu testen, ob eine große Zahl eine Primzahl ist, da die Zahl der möglichen Faktoren mit zunehmender Größe der zu testenden Zahl zu schnell anwächst. Nach dem unten erläuterten Primzahlensatz ist die Anzahl der Primzahlen kleiner als ${displaystyle n}$ in der Nähe von ${Anzeigestil n/(ln(n)-1)}$. Zu ${displaystyle n}$ Um mit dem Primzahltest zu überprüfen, ist der größte benötigte Primfaktor etwas kleiner als ${displaystyle scriptstyle {sqrt {n}}}$ und die Zahl solcher Primfaktor-Kandidaten wäre nahe bei ${displaystyle {sqrt {n}}/(ln {sqrt {n}}-1)}$. Diese Zahl steigt langsamer, da ${displaystyle n}$ steigt, sondern weil Interesse an großen Werten von . besteht ${displaystyle n}$, die Zählung ist auch groß: für ${Anzeigestil n=10^{20}}$ es beläuft sich auf 450 Millionen.

Moderne Algorithmen zum Testen von Primzahlen lassen sich in zwei Hauptklassen einteilen: deterministisch- und Wahrscheinlichkeitsrechnung (oder "Monte Carlo") Algorithmen. Wahrscheinlichkeitsalgorithmen können feststellen, ob eine zusammengesetzte Zahl eine Primzahl ist, sind aber sicherlich nicht in der Lage, Primzahlen als zusammengesetzte Zahlen zu identifizieren; deterministische Algorithmen hingegen haben die Möglichkeit solcher Fehler nicht. Die Bedeutung probabilistischer Algorithmen liegt darin, dass sie oft schneller sind als deterministische Algorithmen; außerdem ist bei den meisten dieser Algorithmen die Wahrscheinlichkeit bekannt, eine zusammengesetzte Zahl fälschlicherweise als Primzahl zu identifizieren. Diese Algorithmen wählen normalerweise eine Zufallszahl ${Anzeigestil a}$, die als "Zeuge" bezeichnet wird, und überprüfen Sie dann eine Formel, in der sowohl der Zeuge als auch die potentielle Primzahl ${displaystyle n}$ Aussehen. Nach mehreren Iterationen erklären sie, dass entweder dat ${displaystyle n}$ "sicher komponiert" oder "wahrscheinlich prim" ist der Fermat-Prime-Test bezieht sich zum Beispiel auf die Der kleine Satz von Fermat (siehe oben). Wenn ja

${displaystyle a^{p}-1{pmod {p}}eq 1}$,

dann ist ${displaystyle p}$ definitiv komponiert. ${displaystyle p}$ kann aber auch zusammengesetzt sein, wenn ${displaystyle a^{p}-1{pmod {p}}=1}$ für alle Zeugen ${Anzeigestil a}$, nämlich wenn ${displaystyle p}$ ein Carmichael-Nummer ist. Im Allgemeinen werden zusammengesetzte Zahlen, die für den jeweiligen Test als „wahrscheinlich prim“ deklariert wurden, unabhängig vom gewählten Zeugen Pseudoprimzahlen werden genannt. Die gängigsten probabilistischen Tests weisen diesen Nachteil jedoch nicht auf. Die folgende Tabelle vergleicht eine Reihe von Primzahltests. Die Laufzeit wird in angegeben ${displaystyle n}$, die Zahl, gegen die getestet wird, und für probabilistische Algorithmen die Zahl ${displaystyle k}$ der durchgeführten Prüfungen.

Prüfung	Entwickelt in	deterministisch	Laufzeit	Anmerkungen
AKS-Test	2002	Ja	${displaystyle O(log ^{6 varepsilon}(n))}$
Fermat.-Prime-Test		Nein	${displaystyle O(kcdot log ^{2}(n)cdot log log(n)cdot log log log(n))}$	scheitert für Carmichael-Zahlen
Lucas-Primzahltest		Ja		erfordert Faktorisierung von ${Anzeigestil n-1}$
Solovay-Straßen-Primzahltest	1977	Nein, Fehlerwahrscheinlichkeit ${Displaystil 2^{-k}}$	${displaystyle O(kcdot log ^{3}(n))}$
Miller-Rabin-Primzahltest	1980	Nein, Fehlerwahrscheinlichkeit ${Displaystil 4^{-k}}$	${displaystyle O(kcdot log ^{2}(n)cdot log log(n)cdot log log log(n))}$
Elliptische Kurve Primzahltest	1977	Nein	${displaystyle O(log ^{5 varepsilon}(n))}$	heuristische Laufzeit

Besondere Arten von Primzahlen

Konstruktion mit Zirkel und Lineal von a regelmäßiges Fünfeck. 5 ist a fermat Primzahl.

Es gibt viele spezielle Arten von Primzahlen; es gibt solche, die beispielsweise durch unterschiedliche Formeln oder durch Berücksichtigung der Nachkommastellen qualifiziert werden. Primzahlen der Form ${Displaystil 2^{p}-1}$, in welchem ${displaystyle p}$ ist eine Primzahl bekannt als Mersenne-Primzahlen. Ihre Bedeutung liegt in der Tatsache, dass es relativ schnelle Algorithmen zum Testen von Primzahlen zum Testen von Mersenne-Primzahlen gibt.

Primzahlen der Form ${Displaystil 2^{2^{n}} 1}$ sind bekannt als Fermat-Primzahlen; ein regulär ${displaystyle n}$-Winkel ist dann und nur dannbaubar mit Zirkel und Lineal wenn

${Displaystil n=2^{i}cdot m}$,

in welchem ${displaystyle m}$ ein Produkt beliebig vieler verschiedener Fermat-Primzahlen und ${Anzeigestil i}$ ist eine beliebige natürliche Zahl, einschließlich Null. Es sind nur fünf Fermat-Primzahlen bekannt: 3, 5, 17, 257 und 65.537.

Primzahlen ${displaystyle p}$, bei welchem ${Anzeigestil 2p 1}$ ist auch prim, bekannt als die Sophie Germainprimes. Eine Primzahl ${displaystyle p}$ wird genannt primär oder Primfaktorfaktor, wenn für eine Zahl ${displaystyle n}$ diese Primzahl hat die Form

${displaystyle p=n#pm 1}$,

in welchem ${displaystyle n#}$ steht für das Produkt ${Displaystil 2cdot 3cdot 5cdot 7cdot ldots }$ aller Primzahlen ${displaystyle leq n}$. Eine Primzahl wird Fakultät benannt nach der Form ${displaystyle n!pm 1}$ ist. Es ist nicht bekannt, ob es unendlich viele primorale oder faktorielle Primzahlen gibt.

Die größte bekannte Primzahl

Seit der Erfindung der elektronischen Computer ist die größte bekannte Primzahl fast immer a Mersenne-Primzahl gewesen, dies weil es ein besonders schnelles gibt Primzahltest, das Lucas-Lehmer-Test für Mersenne-Zahlen, zum Finden von Zahlen dieser Form existiert. Die größte bekannte Primzahl (gefunden im Dezember 2018) ist die Zahl 2^82 589 933-1 und besteht aus 24 862 048 Stellen. Die folgende Tabelle listet die größten bekannten Primzahlen der genannten Arten auf:

Primzahl	Anzahl Dezimalstellen	Nett	Datum	Gefunden von
282 589 933 − 1	24 862 048	Mersenne-Primzahl	Dezember 2018	Patrick Laroche (Gimps)
277 232 917 − 1	23 249 425	Mersenne-Primzahl	26. Dezember 2017	Jon Pace
19 249 × 213 018 586 1	3 918 990	keine Mersenne-Primzahl (Proth-Nummer)	26. März 2007	Siebzehn oder Bust
150 209! 1	712 355	faktorielle Primzahl	Oktober 2012	PrimeGrid
1 098 133# - 1	476 311	primär Primzahl	März 2012	PrimeGrid
3 756 801 695 685 × 2666 669 ± 1	200 700	Zwillingsprime	Dezember 2011	PrimeGrid

Einige der größten Primzahlen, von denen nicht bekannt ist, ob sie eine bestimmte Form haben (d. h., sie wurden nicht durch eine einfache Formel gefunden, wie sie für die Mersenne-Primzahlen erzeugt wurde), indem man ein Stück halbzufälliger Binärdaten nimmt taking , diese zu einer Zahl, dies für einige positive ganze Zahlen ${displaystyle k}$ mit ${displaystyle 256^{k}}$ multiplizieren und dann nach möglichen Primzahlen innerhalb der suchen Intervall${Anzeigestil [256^{k}n 1, 256^{k}(n 1)-1]}$.

Das Electronic Frontier Foundation hat ein Preisgeld von 100.000 . im Jahr 2009 Dollar Zugewiesen an GIMPS für die erstmalige Entdeckung einer Primzahl mit mindestens 10 Millionen Ziffern.^[16] Preise in Höhe von 150.000 US-Dollar bzw. 250.000 US-Dollar wurden von derselben Organisation für Primzahlen von mindestens 100 Millionen bzw. 1 Milliarde Stellen ausgeschrieben.

Primzahlen generieren

Es gibt keine bekannte Formel zur Generierung von Primzahlen, die beim Auffinden von Primzahlen effizienter ist als die oben genannten Methoden.

Da ist ein Sammlung von diophantische Gleichungen in 9 Variablen und einem Parameter mit folgender Eigenschaft: der Parameter ist dann und nur dann eine Primzahl, wenn das resultierende Gleichungssystem eine Lösung über die natürlichen Zahlen hat. Diese Lösung kann verwendet werden, um eine einzige Formel mit der Eigenschaft zu erhalten, dass alle ihre positiven Werte Primzahlen sind.

Eine andere Formel basiert auf dem oben erwähnten Satz von Wilson und erzeugt die Zahl 2 viele Male und alle anderen Primzahlen genau einmal. Es gibt ähnliche Formeln, die auch Primzahlen erzeugen.

Geschichte

Es gibt im überlebenden Nachlass der Antikes Ägypten Hinweise, dass man etwas über Primzahlen wusste: die Ägyptische Fraktion Erweiterungen in der Rhind Papyrus, beispielsweise haben unterschiedliche Formen für Primzahlen und für zusammengesetzte Zahlen. Die ältesten erhaltenen Dokumente über das explizite Studium von Primzahlen stammen jedoch aus der Antike Griechen. Die ab etwa 300 v. Stammes Elemente von Euklid enthält wichtige Sätze über Primzahlen, einschließlich des Beweises für die Unendlichkeit der Zahl der Primzahlen und der Hauptsatz der Arithmetik. Euclid hat auch gezeigt, wie es geht perfekte Zahl von einem Mersenne-Primzahl konstruieren könnte. Das Sieb von Eratosthenes, die zugeschrieben wird Eratosthenes, ist eine einfache Methode zur Berechnung von Primzahlen, obwohl die großen Primzahlen, die heute mit Computern gefunden werden, auf andere Weise erzeugt werden.

Nach dem Antike Griechen Bis zum 17. Jahrhundert geschah nicht viel in Bezug auf das Studium der Primzahlen. 1640 . vorgeschlagen Pierre de Fermat (übrigens ohne Beweis) sind Der kleine Satz von Fermat (was später bewiesen wurde durch Leibniz und Euler). Ein Sonderfall des Satzes von Fermat dürfte den chinesischen Mathematikern schon früher bekannt gewesen sein. Fermat vermutete, dass alle Zahlen der Form ${Displaystil 2^{2^{n}} 1}$ prim sein (sie werden auf ihn bezogen Fermat-Zahlen erwähnt) und er hat dies bestätigt ${Anzeigestil n=4}$ (oder ${Displaystil 2^{16} 1}$). Die nächste Fermat-Zahl, ${Anzeigestil 2^{32} 1}$, stellte sich als zusammengesetzte Zahl heraus (einer der Primfaktoren ist 641), wie Euler später entdeckte, und wahrscheinlich gibt es auch keine größeren Fermat-Zahlen, die Primzahlen sind. Der französische Mönch Marin Mersenne studiert Primzahlen der Form ${Displaystil 2^{p}-1}$, in welchem ${displaystyle p}$ ist eine Primzahl. Diese Art von Primzahlen wird auf ihn bezogen Mersenne-Primzahlen erwähnt.

Eulers Arbeiten zur Zahlentheorie enthielten viele Ergebnisse zu Primzahlen. Er zeigte, dass die unendliche Serie1/2 1/3 1/5 1/7 1/11 ...divergiert.1747 zeigte er, dass die gerade perfekte Zahlen genau die ganzen Zahlen der Form ${Displaystil 2^{p-1}(2^{p}-1)}$ wobei der zweite Primfaktor eine Mersenne-Primzahl ist.

Zu Beginn des 19. Jahrhunderts uitten legendre und Gauss unabhängig von der Vermutung, dass wenn ${Anzeigestil x}$ zu unendlich nähert sich die Zahl der Primzahlen bis zu ${Anzeigestil x}$ asymptotisch zu ${Anzeigestil x/ln(x)}$ nähert, in dem ${Anzeigestil ln(x)}$ das natürlicher Logarithmus von ${Anzeigestil x}$ ist. Ideen von Riemann in seinem Artikel von 1859 über die Zeta-Funktion skizzierte die Umrisse eines Programms, das zum Nachweis der Primzahlsatz. Diese Konturen wurden 1896 von beiden erstellt Hadamard wenn de la Vallée Poussin gefärbt und fertig. Im selben Jahr fanden beide Mathematiker unabhängig voneinander den Beweis für die Primzahlsatz.

Um zu beweisen, dass eine Zahl eine Primzahl ist, werden keine Beweise verwendet (für große Zahlen). Viele Mathematiker haben Primzahltests arbeitete für große Zahlen, beschränkte sich oft auf bestimmte Zahlenformen Pepin-Teststest für Fermat-Zahlen (1877), de Theorem von Proth (um 1878) und die Lucas-Lehmer-Primzahltest (ursprünglich aus dem Jahr 1856),^[17] und das verallgemeinerte Lucas-Primzahltest. Neuere Algorithmen wie der APRT-CL, es ECPP und der AKS-Test an Zufallszahlen arbeiten, sich aber als viel langsamer erweisen als spezifischere Primzahlentests.

Lange Zeit dachte man, Primzahlen hätten nur eine sehr begrenzte Anwendung außerhalb reine Mathematik Vielleicht finden; Dies änderte sich jedoch in den 1970er Jahren, als die Konzepte der asymmetrische Kryptographie wurden erfunden. Dabei bildeten Primzahlen die Grundlage für die ersten Algorithmen, wie den RSAKryptographie-Algorithmus.

Seit 1951 alle größte bekannte Primzahl gefunden mit Computers. Die Suche nach immer größeren Primzahlen hat auch außerhalb mathematischer Kreise großes Interesse geweckt. Das Großartige Internet-Mersenne-Prime-Suche und andere verteiltes RechnenProjekte zur Ermittlung großer Primzahlen sind in den letzten zehn bis fünfzehn Jahren populär geworden, da sich die Mathematiker selbst weiterhin mit der Zahlentheorie hinter den Primzahlen auseinandersetzen.

Verteilung der Primzahlen

sehen Primzahlsatz für den Hauptartikel zu diesem Thema.

Das Ulam-Spirale. Schwarze Pixel zeigen Primzahlen.

Da es unendlich viele Primzahlen gibt, ist es naheliegend, nach Mustern oder Unregelmäßigkeiten in der Verteilung der Primzahlen zu suchen. Das Problem der Modellierung der Verteilung von Primzahlen ist ein beliebtes Forschungsthema für Zahlentheoretiker. Das Auftreten einzelner Primzahlen zwischen den natürliche Zahlen ist (bislang) unberechenbar, obwohl es Gesetze gibt (wie z Primzahlsatz und der Postulat von Bertrand), die ihre mittlere Verteilung bestimmen.^[18]Leonhard Euler sprach darüber vor mehr als 200 Jahren folgende Worte:

Mathematiker haben bis heute vergeblich versucht, irgendeine Regelmäßigkeit in der Reihenfolge der Primzahlen zu entdecken, und wir haben Grund zu der Annahme, dass [die Verteilung der Primzahlen] ein Mysterium ist, in das der Verstand niemals eindringen wird.^[19]

1975 bemerkt Don Zagier während einer Vorlesung folgendes über

Es gibt zwei Tatsachen über die Verteilung von Primzahlen, von denen ich hoffe, dass sie Sie so überwältigend davon überzeugen, dass sie sich dauerhaft in Ihrem Gedächtnis einprägen. Der erste ist, dass die Primzahlen zwischen den natürlichen Zahlen trotz ihrer einfachen Definition und Rolle als Bausteine ​​der natürlichen Zahlen wie Unkraut wachsen, scheinbar keinem Gesetz außer den Gesetzen des Zufalls gehorchen, und niemand kann vorhersagen, wo die nächste Primzahl sein wird aufpoppen. Die zweite Tatsache ist umso erstaunlicher, denn sie besagt genau das Gegenteil: Die Primzahlen weisen eine erstaunliche Regelmäßigkeit auf, es gibt Gesetze, die ihr Verhalten bestimmen, und die Primzahlen gehorchen diesen Gesetzen mit fast militärischer Präzision.^[20]

Euler stellte fest, dass die Funktion ${displaystyle n^{2} n41}$ Primzahlen repräsentiert ${Anzeigestil n<40}$ (aber nicht unbedingt für einen größeren) ${displaystyle n}$), eine bemerkenswerte Tatsache, die bei näherer Betrachtung zu tiefen algebraische Zahlentheorie, genauer gesagt die Heegner-Zahlen, führt. Das Spirale von Ulam zeigt alle natürlichen Zahlen spiralförmig an. Überraschenderweise gruppieren sich Primzahlen auf einigen Diagonalen, auf anderen jedoch nicht.^[21]

Die Anzahl der Primzahlen unter einer gegebenen Zahl

sehen Funktion zum Zählen von Primzahlen für den Hauptartikel zu diesem Thema.

Ein Diagramm, das ${Anzeigestil pi(n)}$ (Blau), ${Anzeigestil n/ln(n)}$ (grün) und ${displaystyle mathrm {Li} (n)}$, das logarithmische Integralfunktion (rot) angezeigt.

Das Primzahlenzählfunktion prime${Anzeigestil pi(n)}$ ist definiert als die Anzahl der Primzahlen bis einschließlich ${displaystyle n}$. Beispielsweise: ${Displaystil pi(11)=5}$, da es fünf Primzahlen kleiner oder gleich 11 gibt. Es sind bekannt Algorithmen um genaue Werte von zu erhalten ${Anzeigestil pi(n)}$ schneller als es möglich ist, eine Primzahl einer beliebigen Zahl bis zu zu sein ${displaystyle n}$ berechnen. Werte so groß wie ${displaystyle pi(10^{20})}$ können mit modernen Computern schnell und genau berechnet werden.

Für größere Werte von ${displaystyle n}$, jenseits der Reichweite moderner Computerausrüstung, die Primzahlsatz eine Schätzung: ${Anzeigestil pi(n)}$ ist ungefähr gleich ${Anzeigestil n/ln(n)}$. Met andere woorden, als ${displaystyle n}$ zeer groot wordt, is de waarschijnlijkheid dat een getal kleiner dan ${displaystyle n}$ een priemgetal is, omgekeerd evenredig aan het aantal cijfers van dit getal ${displaystyle n}$. Er zijn nog betere schattingen bekend; zie bijvoorbeeld Priemgetalstelling#De priemgetal-telfunctie in termen van de logaritmische integraalfunctie.

Als ${displaystyle n}$ een positief geheel getal groter dan 1 is, bestaat er altijd een priemgetal ${displaystyle p}$, zodanig dat ${displaystyle n$ (postulaat van Bertrand).

Hiaten tussen priemgetallen

Zie Priemgetalhiaat voor het hoofdartikel over dit onderwerp.

Een reeks van opeenvolgende gehele getallen, die geen van allen een priemgetal zijn, noemt men priemgetalhiaat. Er bestaan priemgetalhiaten van willekeurige lengte: voor elk natuurlijk getal ${displaystyle n}$ groter dan 1 is de rij (voor een uitleg over de notatie ${displaystyle n!}$ lees het artikel faculteit)

${displaystyle n! 2,n! 3,ldots ,n! n}$

een rij van ${displaystyle n-1}$ opeenvolgende samengestelde gehele getallen, omdat

${displaystyle n! m=mcdot (n!/m 1)=mcdot [(1cdot 2cdot ldots cdot (m-1)cdot (m 1)cdot ldots cdot n) 1]}$

samengesteld is voor elke ${displaystyle 2leq mleq n}$.

Aan de andere kant kunnen priemgetalhiaten ook willekeurig klein worden in verhouding tot de priemgetallen: het quotiënt

${displaystyle (p_{i 1}-p_{i})/p_{i}}$,

waarin ${displaystyle p_{i}}$ het ${displaystyle i}$-de priemgetal aanduidt (dat wil zeggen dat ${displaystyle p_{1}=2, p_{2}=3,}$ enz.), benadert nul als ${displaystyle i}$ naar oneindig nadert.

Open vragen

De Riemann-hypothese

Zie Riemann-hypothese voor het hoofdartikel over dit onderwerp.

De riemann-hypothese is een van de oudste vermoedens waarvoor nog geen wiskundig bewijs is gevonden. Bernhard Riemann schreef het in 1859 op. Om de riemann-hypothese te kunnen formuleren is het noodzakelijk eerst de riemann-zèta-functie te begrijpen, die voor een complex getal${displaystyle s}$ met het reële deel groter dan 1 gedefinieerd is als:

${displaystyle zeta (s)=sum _{n=1}^{infty }{frac {1}{n^{s}}}=prod _{p{ ext{ priem}}}{frac {1}{1-p^{-s}}}}$

De tweede gelijkheid is een gevolg van de hoofdstelling van de rekenkunde en laat zien dat er een nauw verband tussen zèta-functie en de verdeling van de priemgetallen is. Het hierboven genoemde feit bijvoorbeeld, dat er oneindig veel priemgetallen bestaan, kan worden afgelezen uit de divergentie van de harmonische rijen:

${displaystyle zeta (1)=sum _{n=1}^{infty }{frac {1}{n}}=prod _{p{ ext{ priem}}}{frac {1}{1-p^{-1}}}=infty }$

Een ander voorbeeld van de rijkdom van de zèta-functie en een glimp van de moderne algebraïsche getaltheorie is de volgende identiteit, het Bazel-probleem, opgesteld door Euler,

${displaystyle zeta (2)=prod _{p{ ext{ priem}}}{frac {1}{1-p^{-2}}}={frac {pi ^{2}}{6}}}$

De riemann-hypothese gaat over de nulpunten van de zèta-functie. De verbinding met priemgetallen is dat de riemann-hypothese in essentie zegt dat de priemgetallen zo regelmatig verdeeld zijn als mogelijk is. Het vermoeden stelt natuurkundig ruwweg, dat de onregelmatigheid in de verdeling van priemgetallen alleen afkomstig is van willekeurige ruis. De priemgetalstelling zegt dat ongeveer ${displaystyle 1/log x}$ van alle getallen kleiner dan ${displaystyle x}$ priemgetallen zijn, maar de riemann-hypothese stelt dat de asymptotische verdeling van priemgetallen ook geldig is voor veel kortere intervallen over de vierkantswortel van ${displaystyle x}$, voor de intervallen in de buurt van ${displaystyle x}$. De riemann-hypothese wordt algemeen verondersteld waar te zijn.

Andere vermoedens

Naast de riemann-hypothese zijn er veel meer vermoedens over priemgetallen, waarvan velen al heel oud zijn: bijvoorbeeld alle vier de problemen van Landau uit 1912 (het vermoeden van Goldbach, priemtweelingen, vermoeden van Legendre en het vermoeden over ${displaystyle n^{2} 1}$ priemgetallen) zijn tot op heden nog steeds onopgelost.

Veel vermoedens gaan over de vraag of, als er sprake is van bepaalde additionele eigenschappen, er oneindig veel priemgetallen bestaan die deze eigenschappen hebben. Het wordt vermoed dat er bijvoorbeeld oneindig veel fibonacci-priemgetallen^[22] en oneindig veel mersennepriemgetallen bestaan, maar men vermoedt dat het aantal fermat-priemgetallen niet oneindig is.^[23] Het is niet bekend of er oneindig veel priem-euclides-getallen bestaan.

Een aantal vermoedens heeft betrekking op aspecten van de verdeling van priemgetallen. Men vermoedt dat er oneindig veel priemtweelingen, paren van priemgetallen met verschil 2, (priemtweelingvermoeden) bestaan. Het vermoeden van Polignac is een aanscherping van dat vermoeden, in die zin dat dit vermoeden uitspreekt dat voor elk positief geheel getal ${displaystyle n}$, er oneindig veel paren van opeenvolgende priemgetallen bestaan, die van elkaar met ${displaystyle 2n}$ afwijken. Het vermoeden van Brocard zegt dat er altijd ten minste vier priemgetallen tussen de kwadraten van opeenvolgende priemgetallen groter dan 2 zitten. Het vermoeden van Legendre stelt dat er een priemgetal tussen ${displaystyle n^{2}}$ en ${displaystyle (n 1)^{2}}$ bestaat voor elk positief geheel getal ${displaystyle n}$. Dit laatste vermoeden wordt geïmpliceerd door het sterkere vermoeden van Cramér.

Andere vermoedens hebben betrekking op additieve aspecten van getallen en priemgetallen: het vermoeden van Goldbach stelt dat elk even getal groter dan 2 geschreven kan worden als een som van twee priemgetallen, terwijl de zwakke versie vermoedt dat elk oneven geheel getal groter dan 5 geschreven kan worden als een som van drie priemgetallen.

Toepassingen

Voor een lange tijd werd de getaltheorie, en in het bijzonder de studie van priemgetallen, gezien als het kanonieke voorbeeld van de zuivere wiskunde, met geen enkele toepassingen buiten het belang van het bestuderen van het onderwerp zelf. In het bijzonder waren getaltheoretici, zoals de Britse wiskundige G. H. Hardy er trots op werk te doen, dat absoluut geen enkele militaire betekenis had^[24] Deze visie werd echter in de jaren 1970 verbrijzeld toen in het openbaar werd aangekondigd dat priemgetallen konden worden gebruikt als basis voor de creatie van asymmetrische cryptografie-algoritmen. Priemgetallen worden nu ook gebruikt voor hashtabellen en pseudowillekeurigegetallengeneratoren.

Sommige rotormachines werden met een verschillend aantal pinnen op elke rotor ontworpen, waarbij het aantal pinnen op elke rotor ofwel priem ofwel relatief priem ten opzichte van het aantal pinnen op elke andere rotor was. Deze ontwerpbeslissing hielp de volledige cyclus van mogelijke rotorposities te genereren voordat enige positie herhaald wordt.

Modulair rekenen met priemgetal

Zie Modulair rekenen voor het hoofdartikel over dit onderwerp.

Modulair rekenen is een variant van de gebruikelijke rekenkunde. Bij het "rekenen modulo" een vast getal ${displaystyle n}$ vinden de berekeningen plaats in de eindige verzameling${displaystyle {overline {n}}={1,2,ldots ,n-1}}$ en worden resultaten steeds gereduceerd met zoveel veelvouden van ${displaystyle n}$ dat het eindresultaat in deze verzameling ligt.

In het algemeen is echter niet mogelijk om in deze setting te delen. Voor bijvoorbeeld ${displaystyle n=6}$ heeft de vergelijking

${displaystyle 3x=2{pmod {6}}}$

geen oplossing ${displaystyle xin {overline {n}}}$, die het analogon zou zijn van 2/3. Het onderscheidend kenmerk is dat in de modulaire rekenkunde dan en slechts dan deling modulo ${displaystyle n}$ mogelijk is als ${displaystyle n}$ een priemgetal is. Zo heeft de vergelijking

${displaystyle 3x=2{pmod {7}}}$

de unieke oplossing ${displaystyle x=3}$. Op equivalent wijze is ${displaystyle n}$ dan en slechts dan een priemgetal, als alle gehele getallen ${displaystyle 2leq mleq n-1}$relatief priem zijn ten opzichte van ${displaystyle n}$, dat wil zeggen dat hun grootste gemene deler gelijk is aan 1.

De verzameling ${displaystyle {overline {n}}}$ met optellen en vermenigvuldigen wordt aangeduid als ${displaystyle mathbb {Z} /nmathbb {Z} }$. Sommige stellingen kunnen op een abstracte manier worden afgeleid uit de beschouwing van ${displaystyle mathbb {Z} /pmathbb {Z} }$. De kleine stelling van Fermat bijvoorbeeld, waarin wordt gesteld dat ${displaystyle a^{p}-a}$ voor elk geheel getal${displaystyle a}$ deelbaar is door ${displaystyle p}$, kan met behulp van deze worden bewezen. Een gevolg hiervan is het volgende: als ${displaystyle p}$ een priemgetal anders dan 2 en 5 is, dan is ${displaystyle 1/p}$ een repeterende breuk, waarvan de periode gelijk is aan ${displaystyle p-1}$ of een deler van ${displaystyle p-1}$. De breuk ${displaystyle 1/p}$, uitgedrukt met het grondtal ${displaystyle q}$ (in plaats van 10), heeft dezelfde eigenschap, op voorwaarde dat ${displaystyle p}$ geen priemfactor van ${displaystyle q}$ is. De stelling van Wilson zegt dat een geheel getal ${displaystyle p>1}$ dan en slechts dan een priemgetal is, als de faculteit${displaystyle (p-1)! 1}$ deelbaar is door ${displaystyle p}$. Bovendien is een geheel getal ${displaystyle n>4}$ dan en slechts dan een samengesteld getal, als ${displaystyle (n-1)!}$ deelbaar is door ${displaystyle n}$.

Groepentheorie

Veel wiskundige deelgebieden maken intensief gebruik van priemgetallen. Een voorbeeld uit de theorie van de eindige groepen zijn de stellingen van Sylow: als ${displaystyle G}$ een eindige groep is en ${displaystyle p^{n}}$ de hoogste macht van het priemgetal${displaystyle p}$ is, die de orde van ${displaystyle G}$ deelt, dan heeft ${displaystyle G}$ een deelgroep van orde ${displaystyle p^{n}}$. Elke groep met een priemorde is dus cyclisch (stelling van Lagrange).Als ${displaystyle G}$ een eindige groep is en ${displaystyle p}$ een priemgetal is, dat de orde van ${displaystyle G}$ deelt, dan bevat ${displaystyle G}$ een element van orde ${displaystyle p}$ (stelling van Cauchy).

Publiekesleutelcryptografie

Zie asymmetrische cryptografie voor het hoofdartikel over dit onderwerp.

Verschillende publiekesleutelcryptografie-algoritmen, zoals RSA of het Diffie-Hellman-sleuteluitwisselingsprotocol zijn gebaseerd op zeer grote priemgetallen (die bijvoorbeeld uit 512 bits bestaan). Deze algoritmen vertrouwen op het feit dat het veel gemakkelijker is om twee heel grote getallen, ${displaystyle x}$ en ${displaystyle y}$ met elkaar te vermenigvuldigen, met als resultaat ${displaystyle p}$, dan om het omgekeerde te doen, en uit ${displaystyle p}$ de waarde van ${displaystyle x}$ en ${displaystyle y}$ terug te rekenen, indien deze ${displaystyle x}$ en ${displaystyle y}$relatief priem zijn.

Priemgetallen in de natuur

Onvermijdelijk zijn enkele van de getallen die in de natuur voorkomen priemgetallen. Er zijn echter relatief weinig voorbeelden van getallen die in de natuur voorkomen juist omdat zij priemgetallen zijn.

Een voorbeeld van het gebruik van priemgetallen in de natuur is als een evolutionaire strategie die door cicaden van het geslacht Magicicada^[25] lijkt te worden gebruikt. Deze insecten brengen het grootste deel van hun leven als larven ondergronds door. Ze verpoppen zich en komen vervolgens pas na 13 of 17 jaar uit hun holen, waarna zij rondvliegen, paren en dan na hoogstens een paar weken sterven. De logica van de 13- en 17-jarige cyclus is dat men veronderstelt dat deze priemgetalintervallen het voor roofdieren erg moeilijk maken zich in een richting te ontwikkelen dat zij zich in enige mate als roofdieren op Magicicadas kunnen specialiseren^[26] Als Magicicadas met niet-priemgetal-tussenpozen zou verschijnen, zeg elke 12 jaar, dan zouden roofdieren, die elke 2, 3, 4, 6 of 12 jaar zouden verschijnen er zeker van kunnen zijn om Magicicades exemplaren tegen te komen om deze vervolgens te verorberen. Door natuurlijke selectie zouden zij hier langzamerhand beter in kunnen worden. Over een 200-jarige periode zou de gemiddelde roofdierbevolking tijdens hypothetische uitbraken van 14- en 15-jaar cicaden tot 2% hoger zijn dan tijdens uitbraken van 13- en 17-jaar cicaden.^[27] Hoewel klein lijkt dit voordeel genoeg te zijn om de natuurlijke selectie in de richting van een priem-genummerde levenscyclus van deze insecten te sturen.

Er wordt gespeculeerd dat de nulpunten van de zèta-functie verbonden zijn met de energieniveaus van complexe kwantumsystemen.^[28]

Priemgetallen in de techniek

Bij de aandrijving met behulp van kamwielen, zoals toegepast in windmolens, zou het aantal kammen in een kamwiel een priemgetal moeten zijn. Hierdoor raken dezelfde kammen van de twee wielen elkaar pas weer na het aantal omwentelingen van de as dat het product van de twee aantallen kammen is. Hierdoor treedt een lagere en gelijkmatigere slijtage op.

Enkele eigenschappen van priemgetallen

• Als ${displaystyle p}$ een priemgetal is en ${displaystyle p}$ deelt een product ${displaystyle ab}$ van natuurlijke getallen, dan is ${displaystyle p}$ een deler van ${displaystyle a}$ of van ${displaystyle b}$ (zie ook hierboven). Deze eigenschap werd bewezen door Euclides en is bekend als Het lemma van Euclides. Het is gebruikt in sommige bewijzen van de uniciteit van de ontbinding in priemfactoren.
• De ring${displaystyle mathbb {Z} /nmathbb {Z} }$ (zie modulair rekenen) is een lichaam (in België: veld) ofwel eindig lichaam dan en slechts dan als ${displaystyle n}$ een priemgetal is. Anders gezegd: ${displaystyle n}$ is een priemgetal dan en slechts dan als de totiëntfunctie${displaystyle varphi (n)=n-1}$.
• Als ${displaystyle p}$ een priemgetal is en ${displaystyle a}$ is een willekeurig geheel getal, dan is ${displaystyle a^{p}-a}$ deelbaar door ${displaystyle p}$ (kleine stelling van Fermat).
• Als ${displaystyle p}$ een priemgetal is anders dan 2 en 5, dan is ${displaystyle 1/p}$ altijd een repeterende breuk, met een periode van ${displaystyle p-1}$ of een deler van ${displaystyle p-1}$. Deze kan direct van de kleine stelling van Fermat afgeleid worden. ${displaystyle 1/p}$ uitgedrukt in een ander grondtal ${displaystyle q}$ (dus anders dan grondtal 10) heeft het vergelijkbare effect, gegeven dat ${displaystyle p}$ geen priemfactor is van ${displaystyle q}$ (zie repeterende breuk voor enkele interessante eigenschappen).
• Een geheel getal ${displaystyle p>1}$ is een priemgetal dan en slechts dan als ${displaystyle (p-1)! 1}$ deelbaar is door ${displaystyle p}$ (stelling van Wilson); hierbij staat het uitroepteken voor de faculteit. Omgekeerd, een geheel getal ${displaystyle n>4}$ is samengesteld dan en slechts dan als ${displaystyle (n-1)!}$ deelbaar is door ${displaystyle n}$.
• Als ${displaystyle n}$ een positief geheel getal is, dan is er altijd een priemgetal ${displaystyle p}$ met ${displaystyle n$ (Postulaat van Bertrand).
• Sommering van de omgekeerden van alle priemgetallen resulteert in een divergente reeks. Meer precies, als ${displaystyle S(x)}$ de som van de omgekeerden van alle priemgetallen ${displaystyle p}$ is met ${displaystyle pleq x}$, dan ${displaystyle S(x)=O(ln ln x)}$ voor ${displaystyle x o infty }$ (zie Grote-O-notatie).
• Alle priemgetallen hebben de vorm ${displaystyle 6n 1}$ of ${displaystyle 6n-1}$, met als enige uitzonderingen 2 en 3, omdat de andere mogelijkheden alle deelbaar zijn door 2 of 3.
• Voor ieder priemgetal ${displaystyle p>2}$, bestaat er een natuurlijk getal${displaystyle n}$ zodat ${displaystyle p=4npm 1}$.
• Voor ieder priemgetal ${displaystyle p>3}$, bestaat er een natuurlijk getal ${displaystyle n}$ zodat ${displaystyle p=6npm 1}$.
• Voor ieder priemgetal ${displaystyle p>3}$, bestaat er een natuurlijk getal ${displaystyle n}$ zodat ${displaystyle p=24n 1}$.
• De karakteristiek van ieder lichaam (in België: veld) is nul of een priemgetal.
• Als ${displaystyle G}$ een eindige groep is en ${displaystyle p^{n}}$ is de hoogste macht van het priemgetal ${displaystyle p}$ dat de orde van ${displaystyle G}$ deelt, dan heeft ${displaystyle G}$ een subgroep van orde ${displaystyle p^{n}}$ (Stellingen van Sylow).
• Als ${displaystyle p}$ een priemgetal is en ${displaystyle G}$ is een groep met ${displaystyle p^{n}}$ elementen, dan bevat ${displaystyle G}$ een element van de orde ${displaystyle p}$.
• De priemgetalstelling zegt dat het aantal priemgetallen kleiner dan ${displaystyle x}$ asymptotisch ${displaystyle x/ln(x)}$ nadert.

Onbeantwoorde vragen over priemgetallen

Er zijn veel onbeantwoorde vragen op het gebied van priemgetallen:

• Het vermoeden van Goldbach: Kan ieder even getal geschreven worden als de som van twee priemgetallen?
• Priemtweelingvermoeden: Een priemtweeling is een paar priemgetallen dat twee verschilt, zoals 11 en 13. Zijn er oneindig veel priemtweelingen?
• Bevat de rij van Fibonacci oneindig veel priemgetallen?
• Zijn er oneindig veel fermat-priemgetallen?
• Is er een priemgetal tussen ${displaystyle n^{2}}$ en ${displaystyle (n 1)^{2}}$ voor elke ${displaystyle n>0}$?
• Zijn er oneindig veel priemgetallen van de vorm ${displaystyle n^{2} 1}$?
• Is het mogelijk een getal efficiënt (dat wil zeggen in polynomiale tijd) in priemfactoren te ontbinden?
• Waarom komen priemgetallen vaker voor op bepaalde diagonalen in de spiraal van Ulam dan op andere?

Generalisaties

Het concept van priemgetal is zo belangrijk dat het in verschillende deelgebieden van de wiskunde een algemene vorm heeft gekregen. In het algemeen geeft "priem" op toepasselijke wijze aan dat een wiskundig object niet verder ontleedbaar is. Het priemlichaam bijvoorbeeld is het kleinste deellichaam van een lichaam (in België: veld) ${displaystyle F}$. Het is ofwel ${displaystyle mathbb {Q} }$ of het eindige lichaam met ${displaystyle p}$ elementen, vandaar de naam. Vaak wordt er een tweede, extra betekenis bedoeld met het woord priem, namelijk dat elk object, op een in essentie unieke wijze, kan worden uitgesplitst in haar priemcomponenten. In de knopentheorie bijvoorbeeld is een priemknoop een knoop die niet kan worden geschreven als de verbonden som van twee triviale knopen. Elke knoop kan uniek worden uitgedrukt als een verbonden som van priemknopen.^[29][30]Priemmodellen en priem 3-variëteiten zijn andere voorbeelden van dit type.

Ringtheorie

In de ringtheorie beschouwt men als priemelement van een ring het element ${displaystyle p}$ dat de eigenschap heeft dat voor willekeurige elementen${displaystyle a}$ en ${displaystyle b}$ geldt dat wanneer ${displaystyle acdot b}$ deelbaar is door ${displaystyle p}$, er moet gelden dat ${displaystyle a}$ of ${displaystyle b}$ deelbaar is door ${displaystyle p}$ (of allebei). Uit deze definitie volgt dat een additieve inverse van een priemelement eveneens een priemelement is. Het is echter bewijsbaar dat in gangbare getallenverzamelingen, zoals de gehele getallen, een getal een priemgetal is dan en slechts dan als het irreducibel is.

Priemidealen

Zie Priemideaal voor het hoofdartikel over dit onderwerp.

In de ringtheorie wordt de notie van getal in het algemeen vervangen door die van een ideaal. Priemidealen, die priemelementen in die zin veralgemenen dat de hoofdideaal, die door een priemelement wordt gegenereerd een priemideaal is, zijn een belangrijk instrument en object van studie in de commutatieve algebra, de algebraïsche getaltheorie en de algebraïsche meetkunde. De hoofdidealen van de ring van de gehele getallen zijn de idealen (0), (2), (3), (5), (7), (11), ... De hoofdstelling van de rekenkunde veralgemeent naar de stelling van Lasker-Noether die ieder ideaal uitdrukt in een Noethersecommutatieve ring als de doorsnede van priemidealen, met de juiste veralgemeningen van priemmachten.^[31]

Priemidealen zijn de punten van algebro-meetkundige objecten, via de notie van het spectrum van een ring. De rekenkundige meetkunde profiteert ook van deze notie, en veel concepten bestaan zowel in de meetkunde als de getaltheorie. Factorisatie van vertakkingen van priemidealen, vertonen bijvoorbeeld bij het opheffen van een uitbreidingslichaam (in België: uitbreidingsveld), een fundamenteel probleem van de algebraïsche getaltheorie, enige gelijkenis met vertakking in de meetkunde.

Kunst en literatuur

Priemgetallen hebben invloed uitgeoefend op veel kunstenaars en schrijvers. De Franse componistOlivier Messiaen gebruikte priemgetallen om zijn ametrische muziek via "natuurlijke fenomenen" te creëren. In werken zoals La Nativite du Seigneur (1935) en Quatre etudes de rythme (1949-50) maakte hij tegelijkertijd gebruik van motieven, waarvan de lengte werd gegeven door verschillende priemgetallen om zo onvoorspelbare ritmes te creëren: de priemgetallen 41, 43, 47 en 53 komen in een van zijn études voor. Volgens Messiaen werd deze manier van componeren "geïnspireerd door de bewegingen van de natuur, de bewegingen van vrije en ongelijke duur".^[32]

In zijn sciencefictionnovelleContact, later omgewerkt tot de film met dezelfde naam, stelde de NASA-wetenschapper Carl Sagan voor dat priemgetallen gebruikt konden worden als een middel om met buitenaardse wezens te communiceren, een idee dat hij informeel in 1975 voor het eerst samen had ontwikkeld met de Amerikaanse astronoom Frank Drake.^[33]

Veel films weerspiegelen een populaire fascinatie voor de geheimen van de priemgetallen en de cryptografie: films zoals Cube, Sneakers, The Mirror Has Two Faces en A Beautiful Mind, waarvan de laatste gebaseerd is op de biografie door Sylvia Nasar van de wiskundige en Nobelprijswinnaar John Forbes Nash.^[34] Priemgetallen worden ook gebruikt als een metafoor voor eenzaamheid en isolement in de roman van Paolo GiordanoDe eenzaamheid van de priemgetallen, waarin priemgetallen worden afgeschilderd als de "buitenstaanders" onder de gehele getallen.

Opmerkelijke citaten

"Wiskundigen hebben tot de dag van vandaag vergeefs geprobeerd enige orde te ontdekken in de rij van priemgetallen, en we hebben reden te geloven dat het een mysterie is waartoe de menselijke geest nooit zal doordringen." — Leonhard Euler

"God dobbelt misschien niet met het heelal, maar er is iets vreemds aan de hand met de priemgetallen." — Paul Erdős

Trivia

Het jaartal 2020 is een optelsom van de kwadraten van vier opeenvolgende priemgetallen: 17² 19² 23² 29².

Zie ook

• Lijst van priemgetallen

Voetnoten

Externe link

• (en) Chris K. Caldwell: "The prime pages"

Zie de categorie Prime numbers van Wikimedia Commons voor mediabestanden over dit onderwerp.