Primzahl ist eine natürliche (positive ganze) Zahl, die ohne Rest durch nur zwei natürliche Zahlen teilbar ist: durch sich selbst. Mit anderen Worten: Eine Primzahl hat genau zwei natürliche Teiler: und die Zahl selbst.

Per Definition ist die Menge aller Teiler einer Primzahl zweielementig, d.h. stellt eine Menge dar.

Die Menge aller Primzahlen wird mit dem Symbol bezeichnet. Aufgrund der Definition der Menge der Primzahlen können wir also schreiben: .

Die Folge der Primzahlen sieht folgendermaßen aus:

Grundsatz der Arithmetik

Grundsatz der Arithmetik besagt, dass jede natürliche Zahl größer als eins als Produkt von Primzahlen dargestellt werden kann, und zwar auf eindeutige Weise, bis hin zur Reihenfolge der Faktoren. Somit sind Primzahlen die elementaren „Bausteine“ der Menge der natürlichen Zahlen.

Erweiterung natürlicher Zahlen title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} kanonisch:

wo ist eine Primzahl und . Die kanonische Entwicklung einer natürlichen Zahl sieht beispielsweise so aus: .

Man nennt auch die Darstellung einer natürlichen Zahl als Produkt von Primzahlen Faktorisierung einer Zahl.

Eigenschaften von Primzahlen

Sieb des Eratosthenes

Einer der bekanntesten Algorithmen zum Suchen und Erkennen von Primzahlen ist Sieb des Eratosthenes. Daher wurde dieser Algorithmus nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt, der als Autor des Algorithmus gilt.

Um alle Primzahlen zu finden, die kleiner als eine bestimmte Zahl sind, folgen Sie der Methode von Eratosthenes und gehen Sie folgendermaßen vor:

Schritt 1. Schreiben Sie alle natürlichen Zahlen von zwei bis auf, d. h. .
Schritt 2. Weisen Sie der Variablen den Wert zu, also den Wert, der der kleinsten Primzahl entspricht.
Schritt 3. Streichen Sie in der Liste alle Zahlen von bis durch, die ein Vielfaches von sind, also die Zahlen: .
Schritt 4. Suchen Sie die erste ungekreuzte Zahl in der Liste, die größer als ist, und weisen Sie den Wert dieser Zahl einer Variablen zu.
Schritt 5. Wiederholen Sie die Schritte 3 und 4, bis die Zahl erreicht ist.

Der Prozess der Anwendung des Algorithmus sieht folgendermaßen aus:

Alle verbleibenden ungekreuzten Zahlen in der Liste am Ende der Anwendung des Algorithmus sind die Menge der Primzahlen von bis .

Goldbach-Vermutung

Cover des Buches „Onkel Petros und die Goldbach-Hypothese“

Obwohl sich Mathematiker schon seit geraumer Zeit mit Primzahlen beschäftigen, sind viele damit zusammenhängende Probleme bis heute ungelöst. Eines der bekanntesten ungelösten Probleme ist Goldbachs Hypothese, die wie folgt formuliert ist:

• Stimmt es, dass jede gerade Zahl größer als zwei als Summe zweier Primzahlen dargestellt werden kann (Goldbachs Binärhypothese)?
• Stimmt es, dass jede ungerade Zahl größer als 5 als Summe von drei Primzahlen dargestellt werden kann (Goldbachs Ternärhypothese)?

Es sollte gesagt werden, dass die ternäre Goldbach-Hypothese ein Sonderfall der binären Goldbach-Hypothese ist, oder wie Mathematiker sagen, die ternäre Goldbach-Hypothese ist schwächer als die binäre Goldbach-Hypothese.

Goldbachs Vermutung wurde im Jahr 2000 dank eines Werbegags der Verlage Bloomsbury USA (USA) und Faber and Faber (Großbritannien) außerhalb der mathematischen Gemeinschaft weithin bekannt. Diese Verlage versprachen nach der Veröffentlichung des Buches „Onkel Petros und Goldbachs Vermutung“, jedem, der Goldbachs Hypothese innerhalb von zwei Jahren nach Veröffentlichung des Buches beweist, einen Preis von 1 Million US-Dollar zu zahlen. Manchmal wird der erwähnte Verlagspreis mit Preisen zur Lösung der Millenniumspreisprobleme verwechselt. Täuschen Sie sich nicht, Goldbachs Hypothese wird vom Clay Institute nicht als „Millenniumsherausforderung“ eingestuft, obwohl sie eng damit verbunden ist Riemann-Hypothese- eine der „Millenniums-Herausforderungen“.

Das Buch „Primzahlen. Langer Weg in die Unendlichkeit“

Cover des Buches „Die Welt der Mathematik. Primzahlen. Langer Weg in die Unendlichkeit“

Darüber hinaus empfehle ich die Lektüre eines faszinierenden populärwissenschaftlichen Buches, in dessen Anmerkung es heißt: „Die Suche nach Primzahlen ist eines der paradoxsten Probleme der Mathematik.“ Wissenschaftler versuchen seit mehreren Jahrtausenden, es zu lösen, aber angesichts der zunehmenden Verbreitung neuer Versionen und Hypothesen bleibt dieses Rätsel immer noch ungelöst. Das Auftreten von Primzahlen unterliegt keinem System: Sie erscheinen spontan in der Reihe der natürlichen Zahlen und ignorieren alle Versuche der Mathematiker, Muster in ihrer Folge zu identifizieren. Dieses Buch wird es dem Leser ermöglichen, die Entwicklung wissenschaftlicher Konzepte von der Antike bis zur Gegenwart zu verfolgen und die interessantesten Theorien zur Suche nach Primzahlen vorzustellen.“

Zusätzlich zitiere ich den Anfang des zweiten Kapitels dieses Buches: „Primzahlen sind eines der wichtigen Themen, die uns zu den Anfängen der Mathematik zurückführen und uns dann auf einem Weg zunehmender Komplexität an die Spitze führen.“ der modernen Wissenschaft. Daher wäre es sehr nützlich, die faszinierende und komplexe Geschichte der Primzahlentheorie nachzuzeichnen: genau, wie sie sich entwickelte, genau, wie die heute allgemein akzeptierten Fakten und Wahrheiten gesammelt wurden. In diesem Kapitel werden wir sehen, wie Generationen von Mathematikern die natürlichen Zahlen sorgfältig untersuchten, auf der Suche nach einer Regel, die das Auftreten von Primzahlen vorhersagte – eine Regel, die mit fortschreitender Suche immer schwer fassbarer wurde. Wir werden uns auch im Detail mit dem historischen Kontext befassen: den Bedingungen, unter denen Mathematiker arbeiteten, und dem Ausmaß, in dem ihre Arbeit mystische und halbreligiöse Praktiken beinhaltete, die sich deutlich von den wissenschaftlichen Methoden unserer Zeit unterscheiden. Dennoch wurde langsam und mühsam der Boden für neue Ansichten bereitet, die Fermat und Euler im 17. und 18. Jahrhundert inspirierten.“

Aufzählung von Teilern. Per Definition Zahl N ist nur dann eine Primzahl, wenn sie nicht gleichmäßig durch 2 und andere ganze Zahlen außer 1 und sich selbst teilbar ist. Die obige Formel erspart unnötige Schritte und spart Zeit: Nachdem beispielsweise geprüft wurde, ob eine Zahl durch 3 teilbar ist, muss nicht geprüft werden, ob sie durch 9 teilbar ist.

• Die Funktion floor(x) rundet x auf die nächste ganze Zahl, die kleiner oder gleich x ist.

Erfahren Sie mehr über modulare Arithmetik. Die Operation „x mod y“ (mod ist eine Abkürzung des lateinischen Wortes „modulo“, also „Modul“) bedeutet „x durch y dividieren und den Rest ermitteln“. Mit anderen Worten, in der modularen Arithmetik wird bei Erreichen eines bestimmten Wertes aufgerufen Modul, „drehen“ sich die Zahlen wieder auf Null. Beispielsweise hält eine Uhr die Zeit mit einem Modul von 12: Sie zeigt 10, 11 und 12 Uhr an und kehrt dann auf 1 zurück.

• Viele Rechner verfügen über einen Mod-Key. Am Ende dieses Abschnitts wird gezeigt, wie Sie diese Funktion für große Zahlen manuell auswerten.

Ilyas Antwort ist richtig, aber nicht sehr detailliert. Im 18. Jahrhundert galt die Eins übrigens noch als Primzahl. Zum Beispiel so große Mathematiker wie Euler und Goldbach. Goldbach ist der Autor eines der sieben Probleme des Jahrtausends – der Goldbach-Hypothese. Die ursprüngliche Formulierung besagt, dass jede gerade Zahl als Summe zweier Primzahlen dargestellt werden kann. Außerdem wurde zunächst 1 als Primzahl berücksichtigt, und wir sehen Folgendes: 2 = 1+1. Dies ist das kleinste Beispiel, das die ursprüngliche Formulierung der Hypothese erfüllt. Später wurde es korrigiert und die Formulierung erhielt eine moderne Form: „Jede gerade Zahl, beginnend mit 4, kann als Summe zweier Primzahlen dargestellt werden.“

Erinnern wir uns an die Definition. Eine Primzahl ist eine natürliche Zahl p, die nur zwei verschiedene natürliche Teiler hat: p selbst und 1. Folgerung aus der Definition: Eine Primzahl p hat nur einen Primteiler – p selbst.

Nehmen wir nun an, dass 1 eine Primzahl ist. Per Definition hat eine Primzahl nur einen Primteiler – sich selbst. Dann stellt sich heraus, dass jede Primzahl größer als 1 durch eine andere Primzahl (durch 1) teilbar ist. Aber zwei verschiedene Primzahlen können nicht durcheinander geteilt werden, weil Andernfalls handelt es sich nicht um Primzahlen, sondern um zusammengesetzte Zahlen, was der Definition widerspricht. Bei diesem Ansatz stellt sich heraus, dass es nur eine Primzahl gibt – die Einheit selbst. Aber das ist absurd. Daher ist 1 keine Primzahl.

1 sowie 0 bilden eine weitere Klasse von Zahlen – die Klasse neutraler Elemente in Bezug auf n-äre Operationen in einer Teilmenge des algebraischen Feldes. Darüber hinaus ist 1 im Hinblick auf die Additionsoperation auch ein erzeugendes Element für den Ring der ganzen Zahlen.

Mit dieser Überlegung ist es nicht schwer, Analoga von Primzahlen in anderen algebraischen Strukturen zu entdecken. Angenommen, wir haben eine multiplikative Gruppe, die aus Zweierpotenzen gebildet wird, beginnend mit 1: 2, 4, 8, 16, ... usw. 2 fungiert hier als prägendes Element. Eine Primzahl in dieser Gruppe ist eine Zahl, die größer als das kleinste Element ist und nur durch sich selbst und das kleinste Element teilbar ist. In unserer Gruppe haben nur 4 solche Eigenschaften. In unserer Gruppe gibt es keine Primzahlen mehr.

Wenn 2 in unserer Gruppe auch eine Primzahl wäre, dann sehen Sie sich den ersten Absatz an – auch hier würde sich herausstellen, dass nur 2 eine Primzahl ist.

• Übersetzung

Die Eigenschaften von Primzahlen wurden erstmals von Mathematikern im antiken Griechenland untersucht. Mathematiker der pythagoräischen Schule (500 – 300 v. Chr.) interessierten sich vor allem für die mystischen und numerologischen Eigenschaften von Primzahlen. Sie waren die ersten, die Ideen für perfekte und freundliche Zahlen hatten.

Eine vollkommene Zahl hat eine Summe ihrer eigenen Teiler, die ihr selbst entspricht. Zum Beispiel sind die echten Teiler der Zahl 6 1, 2 und 3. 1 + 2 + 3 = 6. Die Teiler der Zahl 28 sind 1, 2, 4, 7 und 14. Außerdem 1 + 2 + 4 + 7 + 14 = 28.

Zahlen werden freundlich genannt, wenn die Summe der echten Teiler einer Zahl gleich einer anderen ist und umgekehrt – zum Beispiel 220 und 284. Wir können sagen, dass eine perfekte Zahl freundlich zu sich selbst ist.

Zur Zeit von Euklids Elementen im Jahr 300 v. Mehrere wichtige Fakten über Primzahlen wurden bereits bewiesen. Im Buch IX der Elemente bewies Euklid, dass es unendlich viele Primzahlen gibt. Dies ist übrigens eines der ersten Beispiele für die Verwendung des Widerspruchsbeweises. Er beweist auch den Grundsatz der Arithmetik – jede ganze Zahl kann eindeutig als Produkt von Primzahlen dargestellt werden.

Er zeigte auch, dass die Zahl 2n-1 * (2n-1) perfekt ist, wenn die Zahl 2n-1 eine Primzahl ist. Ein anderer Mathematiker, Euler, konnte 1747 zeigen, dass alle geraden perfekten Zahlen in dieser Form geschrieben werden können. Bis heute ist nicht bekannt, ob es ungerade vollkommene Zahlen gibt.

Im Jahr 200 v. Chr. Der Grieche Eratosthenes entwickelte einen Algorithmus zum Finden von Primzahlen namens Sieb des Eratosthenes.

Und dann kam es zu einem großen Bruch in der Geschichte der Erforschung der Primzahlen, der mit dem Mittelalter verbunden ist.

Die folgenden Entdeckungen wurden bereits zu Beginn des 17. Jahrhunderts vom Mathematiker Fermat gemacht. Er bewies Albert Girards Vermutung, dass jede Primzahl der Form 4n+1 eindeutig als Summe zweier Quadrate geschrieben werden kann, und formulierte außerdem den Satz, dass jede Zahl als Summe vier Quadrate geschrieben werden kann.

Er entwickelte eine neue Methode zur Faktorisierung großer Zahlen und demonstrierte sie anhand der Zahl 2027651281 = 44021 × 46061. Er bewies auch den kleinen Satz von Fermat: Wenn p eine Primzahl ist, gilt für jede ganze Zahl a, dass a p = a modulo P.

Diese Aussage beweist die Hälfte dessen, was als „chinesische Vermutung“ bekannt ist und 2000 Jahre zurückreicht: Eine ganze Zahl n ist genau dann eine Primzahl, wenn 2 n -2 durch n teilbar ist. Der zweite Teil der Hypothese erwies sich als falsch – zum Beispiel ist 2.341 – 2 durch 341 teilbar, obwohl die Zahl 341 zusammengesetzt ist: 341 = 31 × 11.

Der kleine Satz von Fermat diente als Grundlage für viele weitere Ergebnisse der Zahlentheorie und Methoden zum Testen, ob Zahlen Primzahlen sind – von denen viele noch heute verwendet werden.

Fermat korrespondierte viel mit seinen Zeitgenossen, insbesondere mit einem Mönch namens Maren Mersenne. In einem seiner Briefe stellte er die Hypothese auf, dass Zahlen der Form 2 n +1 immer Primzahlen sein werden, wenn n eine Zweierpotenz ist. Er testete dies für n = 1, 2, 4, 8 und 16 und war überzeugt, dass in dem Fall, in dem n keine Zweierpotenz war, die Zahl nicht unbedingt eine Primzahl war. Diese Zahlen werden Fermats Zahlen genannt, und nur 100 Jahre später zeigte Euler, dass die nächste Zahl, 2 · 32 + 1 = 4294967297, durch 641 teilbar und daher keine Primzahl ist.

Zahlen der Form 2 n - 1 waren ebenfalls Gegenstand der Forschung, da sich leicht zeigen lässt, dass, wenn n zusammengesetzt ist, auch die Zahl selbst zusammengesetzt ist. Diese Zahlen werden Mersenne-Zahlen genannt, weil er sie eingehend untersucht hat.

Aber nicht alle Zahlen der Form 2 n - 1, wobei n eine Primzahl ist, sind Primzahlen. Zum Beispiel 2 11 - 1 = 2047 = 23 * 89. Dies wurde erstmals 1536 entdeckt.

Zahlen dieser Art lieferten den Mathematikern viele Jahre lang die größten bekannten Primzahlen. Dass M 19 1588 von Cataldi bewiesen wurde, war 200 Jahre lang die größte bekannte Primzahl, bis Euler bewies, dass M 31 ebenfalls eine Primzahl war. Dieser Rekord hielt weitere hundert Jahre an, und dann zeigte Lucas, dass M 127 eine Primzahl ist (und dies ist bereits eine Zahl mit 39 Ziffern), und danach wurde die Forschung mit dem Aufkommen von Computern fortgesetzt.

Im Jahr 1952 wurde die Primzahl der Zahlen M 521, M 607, M 1279, M 2203 und M 2281 nachgewiesen.

Bis 2005 wurden 42 Mersenne-Primzahlen gefunden. Die größte davon, M 25964951, besteht aus 7816230 Ziffern.

Eulers Arbeit hatte großen Einfluss auf die Zahlentheorie, einschließlich der Primzahlen. Er erweiterte den Kleinen Satz von Fermat und führte die φ-Funktion ein. Faktorisierte die 5. Fermat-Zahl 2 32 +1, fand 60 Paare befreundeter Zahlen und formulierte das quadratische Reziprozitätsgesetz (konnte es jedoch nicht beweisen).

Er war der erste, der Methoden der mathematischen Analyse einführte und die analytische Zahlentheorie entwickelte. Er bewies, dass nicht nur die harmonische Reihe ∑ (1/n), sondern auch eine Reihe der Form

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Auch das durch die Summe der Kehrwerte der Primzahlen erhaltene Ergebnis divergiert. Die Summe der n Terme der harmonischen Reihe wächst ungefähr mit log(n), und die zweite Reihe divergiert langsamer mit log[log(n)]. Das bedeutet, dass beispielsweise die Summe der Kehrwerte aller bisher gefundenen Primzahlen nur 4 ergibt, obwohl die Reihe immer noch divergiert.

Auf den ersten Blick scheint es, dass Primzahlen ziemlich zufällig auf ganze Zahlen verteilt sind. Beispielsweise gibt es unter den 100 Zahlen unmittelbar vor 10000000 9 Primzahlen und unter den 100 Zahlen unmittelbar nach diesem Wert nur 2. Über große Abschnitte sind die Primzahlen jedoch recht gleichmäßig verteilt. Legendre und Gauß befassten sich mit Fragen ihrer Verbreitung. Gauß erzählte einmal einem Freund, dass er in allen freien 15 Minuten immer die Anzahl der Primzahlen in den nächsten 1000 Zahlen zählt. Am Ende seines Lebens hatte er alle Primzahlen bis 3 Millionen gezählt. Legendre und Gauß haben gleichermaßen berechnet, dass für große n die Primzahldichte 1/log(n) beträgt. Legendre schätzte die Anzahl der Primzahlen im Bereich von 1 bis n als

π(n) = n/(log(n) - 1,08366)

Und Gauß ist wie ein logarithmisches Integral

π(n) = ∫ 1/log(t) dt

Mit einem Integrationsintervall von 2 bis n.

Die Aussage über die Primzahldichte 1/log(n) ist als Primzahlverteilungssatz bekannt. Sie versuchten dies im Laufe des 19. Jahrhunderts zu beweisen, und Tschebyschew und Riemann erzielten Fortschritte. Sie verbanden es mit der Riemannschen Hypothese, einer noch unbewiesenen Hypothese über die Nullstellenverteilung der Riemannschen Zetafunktion. Die Dichte der Primzahlen wurde 1896 gleichzeitig von Hadamard und Vallée-Poussin bewiesen.

In der Primzahlentheorie gibt es noch viele ungelöste Fragen, die teilweise Hunderte von Jahren alt sind:

• Bei der Primzahlzwillingshypothese geht es um unendlich viele Paare von Primzahlen, die sich um 2 voneinander unterscheiden
• Goldbachs Vermutung: Jede gerade Zahl, beginnend mit 4, kann als Summe zweier Primzahlen dargestellt werden
• Gibt es unendlich viele Primzahlen der Form n 2 + 1?
• Ist es immer möglich, eine Primzahl zwischen n 2 und (n + 1) 2 zu finden? (Die Tatsache, dass es zwischen n und 2n immer eine Primzahl gibt, wurde von Tschebyschew bewiesen)
• Ist die Anzahl der Fermat-Primzahlen unendlich? Gibt es nach 4 Fermat-Primzahlen?
• Gibt es eine arithmetische Folge aufeinanderfolgender Primzahlen für eine bestimmte Länge? zum Beispiel für Länge 4: 251, 257, 263, 269. Die maximal gefundene Länge beträgt 26.
• Gibt es unendlich viele Mengen von drei aufeinanderfolgenden Primzahlen in einer arithmetischen Folge?
• n 2 - n + 41 ist eine Primzahl für 0 ≤ n ≤ 40. Gibt es unendlich viele solcher Primzahlen? Dieselbe Frage für die Formel n 2 - 79 n + 1601. Diese Zahlen sind Primzahlen für 0 ≤ n ≤ 79.
• Gibt es unendlich viele Primzahlen der Form n# + 1? (n# ist das Ergebnis der Multiplikation aller Primzahlen kleiner als n)
• Gibt es unendlich viele Primzahlen der Form n# -1?
• Gibt es unendlich viele Primzahlen der Form n? + 1?
• Gibt es unendlich viele Primzahlen der Form n? – 1?
• Wenn p eine Primzahl ist, enthält 2 p -1 dann nicht immer Primzahlquadrate unter seinen Faktoren?
• Enthält die Fibonacci-Folge unendlich viele Primzahlen?

Die größten Zwillingsprimzahlen sind 2003663613 × 2 195000 ± 1. Sie bestehen aus 58711 Ziffern und wurden 2007 entdeckt.

Die größte faktorielle Primzahl (vom Typ n! ± 1) ist 147855! - 1. Es besteht aus 142891 Ziffern und wurde 2002 gefunden.

Die größte ursprüngliche Primzahl (eine Zahl der Form n# ± 1) ist 1098133# + 1.

• Übersetzung

Die Eigenschaften von Primzahlen wurden erstmals von Mathematikern im antiken Griechenland untersucht. Mathematiker der pythagoräischen Schule (500 – 300 v. Chr.) interessierten sich vor allem für die mystischen und numerologischen Eigenschaften von Primzahlen. Sie waren die ersten, die Ideen für perfekte und freundliche Zahlen hatten.

Eine vollkommene Zahl hat eine Summe ihrer eigenen Teiler, die ihr selbst entspricht. Zum Beispiel sind die echten Teiler der Zahl 6 1, 2 und 3. 1 + 2 + 3 = 6. Die Teiler der Zahl 28 sind 1, 2, 4, 7 und 14. Außerdem 1 + 2 + 4 + 7 + 14 = 28.

Zahlen werden freundlich genannt, wenn die Summe der echten Teiler einer Zahl gleich einer anderen ist und umgekehrt – zum Beispiel 220 und 284. Wir können sagen, dass eine perfekte Zahl freundlich zu sich selbst ist.

Zur Zeit von Euklids Elementen im Jahr 300 v. Mehrere wichtige Fakten über Primzahlen wurden bereits bewiesen. Im Buch IX der Elemente bewies Euklid, dass es unendlich viele Primzahlen gibt. Dies ist übrigens eines der ersten Beispiele für die Verwendung des Widerspruchsbeweises. Er beweist auch den Grundsatz der Arithmetik – jede ganze Zahl kann eindeutig als Produkt von Primzahlen dargestellt werden.

Er zeigte auch, dass die Zahl 2n-1 * (2n-1) perfekt ist, wenn die Zahl 2n-1 eine Primzahl ist. Ein anderer Mathematiker, Euler, konnte 1747 zeigen, dass alle geraden perfekten Zahlen in dieser Form geschrieben werden können. Bis heute ist nicht bekannt, ob es ungerade vollkommene Zahlen gibt.

Im Jahr 200 v. Chr. Der Grieche Eratosthenes entwickelte einen Algorithmus zum Finden von Primzahlen namens Sieb des Eratosthenes.

Und dann kam es zu einem großen Bruch in der Geschichte der Erforschung der Primzahlen, der mit dem Mittelalter verbunden ist.

Die folgenden Entdeckungen wurden bereits zu Beginn des 17. Jahrhunderts vom Mathematiker Fermat gemacht. Er bewies Albert Girards Vermutung, dass jede Primzahl der Form 4n+1 eindeutig als Summe zweier Quadrate geschrieben werden kann, und formulierte außerdem den Satz, dass jede Zahl als Summe vier Quadrate geschrieben werden kann.

Er entwickelte eine neue Methode zur Faktorisierung großer Zahlen und demonstrierte sie anhand der Zahl 2027651281 = 44021 × 46061. Er bewies auch den kleinen Satz von Fermat: Wenn p eine Primzahl ist, gilt für jede ganze Zahl a, dass a p = a modulo P.

Diese Aussage beweist die Hälfte dessen, was als „chinesische Vermutung“ bekannt ist und 2000 Jahre zurückreicht: Eine ganze Zahl n ist genau dann eine Primzahl, wenn 2 n -2 durch n teilbar ist. Der zweite Teil der Hypothese erwies sich als falsch – zum Beispiel ist 2.341 – 2 durch 341 teilbar, obwohl die Zahl 341 zusammengesetzt ist: 341 = 31 × 11.

Der kleine Satz von Fermat diente als Grundlage für viele weitere Ergebnisse der Zahlentheorie und Methoden zum Testen, ob Zahlen Primzahlen sind – von denen viele noch heute verwendet werden.

Fermat korrespondierte viel mit seinen Zeitgenossen, insbesondere mit einem Mönch namens Maren Mersenne. In einem seiner Briefe stellte er die Hypothese auf, dass Zahlen der Form 2 n +1 immer Primzahlen sein werden, wenn n eine Zweierpotenz ist. Er testete dies für n = 1, 2, 4, 8 und 16 und war überzeugt, dass in dem Fall, in dem n keine Zweierpotenz war, die Zahl nicht unbedingt eine Primzahl war. Diese Zahlen werden Fermats Zahlen genannt, und nur 100 Jahre später zeigte Euler, dass die nächste Zahl, 2 · 32 + 1 = 4294967297, durch 641 teilbar und daher keine Primzahl ist.

Zahlen der Form 2 n - 1 waren ebenfalls Gegenstand der Forschung, da sich leicht zeigen lässt, dass, wenn n zusammengesetzt ist, auch die Zahl selbst zusammengesetzt ist. Diese Zahlen werden Mersenne-Zahlen genannt, weil er sie eingehend untersucht hat.

Aber nicht alle Zahlen der Form 2 n - 1, wobei n eine Primzahl ist, sind Primzahlen. Zum Beispiel 2 11 - 1 = 2047 = 23 * 89. Dies wurde erstmals 1536 entdeckt.

Zahlen dieser Art lieferten den Mathematikern viele Jahre lang die größten bekannten Primzahlen. Dass M 19 1588 von Cataldi bewiesen wurde, war 200 Jahre lang die größte bekannte Primzahl, bis Euler bewies, dass M 31 ebenfalls eine Primzahl war. Dieser Rekord hielt weitere hundert Jahre an, und dann zeigte Lucas, dass M 127 eine Primzahl ist (und dies ist bereits eine Zahl mit 39 Ziffern), und danach wurde die Forschung mit dem Aufkommen von Computern fortgesetzt.

Im Jahr 1952 wurde die Primzahl der Zahlen M 521, M 607, M 1279, M 2203 und M 2281 nachgewiesen.

Bis 2005 wurden 42 Mersenne-Primzahlen gefunden. Die größte davon, M 25964951, besteht aus 7816230 Ziffern.

Eulers Arbeit hatte großen Einfluss auf die Zahlentheorie, einschließlich der Primzahlen. Er erweiterte den Kleinen Satz von Fermat und führte die φ-Funktion ein. Faktorisierte die 5. Fermat-Zahl 2 32 +1, fand 60 Paare befreundeter Zahlen und formulierte das quadratische Reziprozitätsgesetz (konnte es jedoch nicht beweisen).

Er war der erste, der Methoden der mathematischen Analyse einführte und die analytische Zahlentheorie entwickelte. Er bewies, dass nicht nur die harmonische Reihe ∑ (1/n), sondern auch eine Reihe der Form

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Auch das durch die Summe der Kehrwerte der Primzahlen erhaltene Ergebnis divergiert. Die Summe der n Terme der harmonischen Reihe wächst ungefähr mit log(n), und die zweite Reihe divergiert langsamer mit log[log(n)]. Das bedeutet, dass beispielsweise die Summe der Kehrwerte aller bisher gefundenen Primzahlen nur 4 ergibt, obwohl die Reihe immer noch divergiert.

Auf den ersten Blick scheint es, dass Primzahlen ziemlich zufällig auf ganze Zahlen verteilt sind. Beispielsweise gibt es unter den 100 Zahlen unmittelbar vor 10000000 9 Primzahlen und unter den 100 Zahlen unmittelbar nach diesem Wert nur 2. Über große Abschnitte sind die Primzahlen jedoch recht gleichmäßig verteilt. Legendre und Gauß befassten sich mit Fragen ihrer Verbreitung. Gauß erzählte einmal einem Freund, dass er in allen freien 15 Minuten immer die Anzahl der Primzahlen in den nächsten 1000 Zahlen zählt. Am Ende seines Lebens hatte er alle Primzahlen bis 3 Millionen gezählt. Legendre und Gauß haben gleichermaßen berechnet, dass für große n die Primzahldichte 1/log(n) beträgt. Legendre schätzte die Anzahl der Primzahlen im Bereich von 1 bis n als

π(n) = n/(log(n) - 1,08366)

Und Gauß ist wie ein logarithmisches Integral

π(n) = ∫ 1/log(t) dt

Mit einem Integrationsintervall von 2 bis n.

Die Aussage über die Primzahldichte 1/log(n) ist als Primzahlverteilungssatz bekannt. Sie versuchten dies im Laufe des 19. Jahrhunderts zu beweisen, und Tschebyschew und Riemann erzielten Fortschritte. Sie verbanden es mit der Riemannschen Hypothese, einer noch unbewiesenen Hypothese über die Nullstellenverteilung der Riemannschen Zetafunktion. Die Dichte der Primzahlen wurde 1896 gleichzeitig von Hadamard und Vallée-Poussin bewiesen.

In der Primzahlentheorie gibt es noch viele ungelöste Fragen, die teilweise Hunderte von Jahren alt sind:

• Bei der Primzahlzwillingshypothese geht es um unendlich viele Paare von Primzahlen, die sich um 2 voneinander unterscheiden
• Goldbachs Vermutung: Jede gerade Zahl, beginnend mit 4, kann als Summe zweier Primzahlen dargestellt werden
• Gibt es unendlich viele Primzahlen der Form n 2 + 1?
• Ist es immer möglich, eine Primzahl zwischen n 2 und (n + 1) 2 zu finden? (Die Tatsache, dass es zwischen n und 2n immer eine Primzahl gibt, wurde von Tschebyschew bewiesen)
• Ist die Anzahl der Fermat-Primzahlen unendlich? Gibt es nach 4 Fermat-Primzahlen?
• Gibt es eine arithmetische Folge aufeinanderfolgender Primzahlen für eine bestimmte Länge? zum Beispiel für Länge 4: 251, 257, 263, 269. Die maximal gefundene Länge beträgt 26.
• Gibt es unendlich viele Mengen von drei aufeinanderfolgenden Primzahlen in einer arithmetischen Folge?
• n 2 - n + 41 ist eine Primzahl für 0 ≤ n ≤ 40. Gibt es unendlich viele solcher Primzahlen? Dieselbe Frage für die Formel n 2 - 79 n + 1601. Diese Zahlen sind Primzahlen für 0 ≤ n ≤ 79.
• Gibt es unendlich viele Primzahlen der Form n# + 1? (n# ist das Ergebnis der Multiplikation aller Primzahlen kleiner als n)
• Gibt es unendlich viele Primzahlen der Form n# -1?
• Gibt es unendlich viele Primzahlen der Form n? + 1?
• Gibt es unendlich viele Primzahlen der Form n? – 1?
• Wenn p eine Primzahl ist, enthält 2 p -1 dann nicht immer Primzahlquadrate unter seinen Faktoren?
• Enthält die Fibonacci-Folge unendlich viele Primzahlen?

Die größten Zwillingsprimzahlen sind 2003663613 × 2 195000 ± 1. Sie bestehen aus 58711 Ziffern und wurden 2007 entdeckt.

Die größte faktorielle Primzahl (vom Typ n! ± 1) ist 147855! - 1. Es besteht aus 142891 Ziffern und wurde 2002 gefunden.

Die größte ursprüngliche Primzahl (eine Zahl der Form n# ± 1) ist 1098133# + 1.

Tags: Tags hinzufügen