Satz von Euklid - Euclid's theorem

Der Satz von Euklid ist eine grundlegende Aussage der Zahlentheorie , die besagt , dass es unendlich viele Primzahlen gibt. Es wurde zuerst von Euklid in seinem Werk Elements bewiesen . Es gibt mehrere Beweise für das Theorem.

Euklids Beweis

Euklid bot einen Beweis an, der in seinem Werk Elemente (Buch IX, Proposition 20) veröffentlicht wurde, das hier paraphrasiert ist.

Betrachten Sie eine beliebige endliche Liste von Primzahlen p 1p 2 , ...,  p n . Es wird gezeigt, dass mindestens eine weitere Primzahl existiert, die nicht in dieser Liste enthalten ist. Sei P das Produkt aller Primzahlen in der Liste: P  =  p 1 p 2 ... p n . Sei q  =  P  + 1. Dann ist q entweder prim oder nicht:

  • Wenn q eine Primzahl ist, gibt es mindestens eine weitere Primzahl, die nicht in der Liste enthalten ist, nämlich q selbst.
  • Wenn q keine Primzahl ist, dann teilt ein  Primfaktor p q . Wenn dieser Faktor p in unserer Liste wäre, würde er P teilen (da P das Produkt jeder Zahl in der Liste ist); p teilt aber auch P  + 1 =  q , wie eben gesagt. Wenn p P und auch q teilt , dann muss p auch die Differenz der beiden Zahlen teilen, die ( P  + 1) −  P oder nur 1 ist. Da keine Primzahl 1 teilt, kann p nicht auf der Liste stehen. Dies bedeutet, dass mindestens eine weitere Primzahl über die in der Liste hinaus existiert.

Dies beweist, dass es zu jeder endlichen Liste von Primzahlen eine Primzahl gibt, die nicht in der Liste enthalten ist. Da Euklid keine Möglichkeit hatte, eine beliebige Liste von Primzahlen zu schreiben, verwendete er im Originalwerk eine Methode, die er häufig anwandte, nämlich die Methode des verallgemeinerbaren Beispiels. Er wählt nämlich nur drei Primzahlen aus und beweist mit der oben skizzierten allgemeinen Methode, dass er immer eine zusätzliche Primzahl finden kann. Euklid geht vermutlich davon aus, dass seine Leser davon überzeugt sind, dass ein ähnlicher Beweis funktionieren wird, egal wie viele Primzahlen ursprünglich ausgewählt wurden.

Es wird oft fälschlicherweise berichtet, dass Euklid dieses Ergebnis durch Widerspruch bewiesen hat, beginnend mit der Annahme, dass die anfangs betrachtete endliche Menge alle Primzahlen enthält, obwohl es sich tatsächlich um einen Beweis durch Fälle handelt , eine direkte Beweismethode . Der Philosoph Torkel Franzén , in einem Buch über Logik, heißt es: „Euklids Beweis , dass es unendlich viele Primzahlen ist nicht ein indirekter Beweis [...] Das Argument , manchmal als indirekten Beweis formuliert wird , indem sie mit der Annahme , ‚ Es wäre zu ersetzen q 1 , ... q n sind alle Primzahlen". Da diese Annahme jedoch nicht einmal im Beweis verwendet wird, ist die Umformulierung sinnlos."

Variationen

Es gibt mehrere Variationen von Euklids Beweis, darunter die folgenden:

Die Fakultät n ! einer positiven ganzen Zahl n ist durch jede ganze Zahl von 2 bis n teilbar , da es das Produkt aller davon ist. Daher ist n ! + 1 ist durch keine der ganzen Zahlen von 2 bis n (einschließlich) teilbar (ergibt einen Rest von 1, wenn durch jede der Zahlen geteilt wird). Daher n ! + 1 ist entweder prim oder durch eine Primzahl größer als n teilbar  . In jedem Fall gibt es für jede positive ganze Zahl n mindestens eine Primzahl größer als  n . Die Schlussfolgerung ist, dass die Anzahl der Primzahlen unendlich ist.

Eulers Beweis

Ein weiterer Beweis des Schweizer Mathematikers Leonhard Euler beruht auf dem fundamentalen Satz der Arithmetik : dass jede ganze Zahl eine eindeutige Primfaktorzerlegung hat. Was Euler schrieb (nicht mit dieser modernen Notation und im Gegensatz zu modernen Standards, die die Argumente in Summen und Produkten nicht auf endliche Mengen von ganzen Zahlen beschränkt) ist äquivalent zu der Aussage, die wir haben

wobei bezeichnet die Menge der k ersten Primzahlen und ist die Menge der positiven ganzen Zahlen, deren Primfaktoren alle in . sind

Um dies zu zeigen, dehnt ich je einen Faktor in dem Produkt als geometrische Reihe , und verteilt das Produkt über die Summe (Dies ist ein Spezialfall der Euler Produktformel für die Riemann Zeta - Funktion ).

In der vorletzten Summe kommt jedes Produkt von Primzahlen genau einmal vor, und so gilt nach dem Fundamentalsatz der Arithmetik die letzte Gleichheit. In seiner ersten Folgerung zu diesem Ergebnis bezeichnet Euler durch ein der „absoluten Unendlichkeit“ ähnliches Symbol und schreibt, dass die unendliche Summe in der Aussage gleich dem „Wert“ ist, dem also auch das unendliche Produkt gleich ist (in moderner Terminologie ist dies äquivalent zu sagen, dass die Teilsumme bis zu der harmonischen Reihe asymptotisch divergiert wie ). Dann stellt Euler in seiner zweiten Folgerung fest, dass das Produkt

gegen den endlichen Wert 2 konvergiert, und dass es folglich mehr Primzahlen als Quadrate gibt (« sequitur infinities plures esse numeros primos »). Dies beweist den Satz von Euklid.

Von Euler verwendetes Symbol , um die Unendlichkeit anzuzeigen


In derselben Arbeit (Satz 19) benutzte Euler die obige Gleichheit tatsächlich, um einen viel stärkeren Satz zu beweisen, der vor ihm unbekannt war, nämlich dass die Reihe

ist divergent , wobei P die Menge aller Primzahlen bezeichnet (Euler schreibt , dass die unendliche Summe , die in der modernen Terminologie ist äquivalent zu sagen , dass die Teilsumme von bis zu dieser Serie verhält sich asymptotisch wie ).

Der Beweis von Erdős

Paul Erdős hat einen Beweis geführt, der ebenfalls auf dem Fundamentalsatz der Arithmetik beruht. Jede positive ganze Zahl hat eine eindeutige Faktorisierung in eine quadratfreie Zahl und eine Quadratzahl rs 2 . Beispiel: 75.600 = 2 4 3 3 5 2 7 1 = 21 ⋅ 60 2 .

Sei N eine positive ganze Zahl und k die Anzahl der Primzahlen kleiner oder gleich N . Nennen Sie diese Primzahlen p 1 , ... , p k . Jede positive ganze Zahl, die kleiner oder gleich N ist, kann dann in der Form

wobei jedes e i entweder 0 oder 1 ist . Es gibt 2 k Möglichkeiten, den quadratfreien Teil von a zu bilden . Und s 2 kann höchstens N sein , also sN . Somit können höchstens 2 k N Zahlen in dieser Form geschrieben werden. Mit anderen Worten,

Oder, neu anordnen, k , die Anzahl der Primzahlen kleiner oder gleich N ist größer oder gleich 1/2log 2 N . Da N willkürlich war, kann k durch geeignete Wahl von N beliebig groß sein .

Fürstenbergs Beweis

In den 1950er Jahren führte Hillel Fürstenberg einen Widerspruchsbeweis mit Punktmengentopologie ein .

Definieren Sie eine Topologie auf den ganzen Zahlen Z , genannt die gleichmäßig verteilte ganzzahlige Topologie , indem Sie eine Teilmenge U  ⊆  Z genau dann als offene Menge deklarieren, wenn sie entweder die leere Menge oder eine Vereinigung von arithmetischen Folgen S ist ( ab ) (für a  ≠ 0), wobei

Dann folgt ein Widerspruch aus der Eigenschaft, dass eine endliche Menge von ganzen Zahlen nicht offen sein kann und der Eigenschaft, dass die Basismengen S ( ab ) sowohl offen als auch abgeschlossen sind , da

kann nicht abgeschlossen werden, weil sein Komplement endlich ist, aber abgeschlossen, weil es eine endliche Vereinigung abgeschlossener Mengen ist.

Einige aktuelle Beweise

Nachweis nach dem Einschluss-Ausschluss-Prinzip

Juan Pablo Pinasco hat den folgenden Beweis geschrieben.

Seien p 1 , ...,  p N die kleinsten N Primzahlen. Dann ist nach dem Einschluss-Ausschluss-Prinzip die Anzahl der positiven ganzen Zahlen kleiner oder gleich x , die durch eine dieser Primzahlen teilbar sind

Durch x dividieren und x  → ∞ lassen ergibt

Dies kann geschrieben werden als

Wenn keine anderen Primzahlen als p 1 , ...,  p N existieren, dann ist der Ausdruck in (1) gleich  und der Ausdruck in (2) ist gleich 1, aber offensichtlich ist der Ausdruck in (3) nicht gleich 1. Daher muss es mehr Primzahlen als   p 1 , ...,  p N geben .

Beweis mit der Formel von de Polignac

Im Jahr 2010 veröffentlichte Junho Peter Whang den folgenden Widerspruchsbeweis. Sei k eine beliebige positive ganze Zahl. Dann nach der Formel von de Polignac (eigentlich aufgrund von Legendre )

wo

Aber wenn nur endlich viele Primzahlen existieren, dann

(der Zähler des Bruchs würde einfach exponentiell wachsen, während der Nenner nach Stirling-Näherung schneller wächst als einfach exponentiell), was der Tatsache widerspricht, dass für jedes k der Zähler größer oder gleich dem Nenner ist.

Nachweis durch Konstruktion

Filip Saidak führte den folgenden Konstruktionsbeweis an , der weder die reductio ad absurdum noch das Lemma von Euklid verwendet (dass wenn eine Primzahl p ab teilt , muss sie a oder  b teilen ).

Da jede natürliche Zahl (> 1) mindestens einen Primfaktor hat und zwei aufeinanderfolgende Zahlen n und ( n  + 1) keinen gemeinsamen Faktor haben, hat das Produkt n ( n  + 1) mehr verschiedene Primfaktoren als die Zahl n selbst . Also die Kette der pronischen Zahlen :
1×2 = 2 {2}, 2×3 = 6 {2, 3}, 6×7 = 42 {2, 3, 7}, 42×43 = 1806 {2, 3, 7, 43}, 1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
liefert eine Folge von unbegrenzt wachsenden Mengen von Primzahlen.

Beweis mit der Irrationalität von π

Die Darstellung der Leibniz-Formel für π als Euler-Produkt ergibt

Die Zähler dieses Produkts sind die ungeraden Primzahlen, und jeder Nenner ist das Vielfache von vier, das dem Zähler am nächsten liegt.

Wenn es endlich viele Primzahlen wären , würde diese Formel zeigt , dass π eine rationale Zahl ist, im Widerspruch zu der Tatsache , dass π ist irrational .

Nachweis mittels Informationstheorie

Alexander Shen hat einen Beweis vorgelegt, der Inkompressibilität verwendet :

Angenommen, es gäbe nur k Primzahlen ( p 1 ...  p k ). Nach dem Fundamentalsatz der Arithmetik könnte dann jede positive ganze Zahl n wie folgt dargestellt werden:

wobei die nicht-negativen ganzzahligen Exponenten e i zusammen mit der endlichen Liste von Primzahlen ausreichen, um die Zahl zu rekonstruieren. Da für alle i folgt, dass all (wobei den Logarithmus zur Basis 2 bezeichnet).

Dies ergibt eine Kodierung für n der folgenden Größe (unter Verwendung der großen O-Notation ):

Bits.

Dies ist eine viel effizientere Codierung als die direkte Binärdarstellung von n , die Bits benötigt. Ein etabliertes Ergebnis der verlustfreien Datenkompression besagt, dass man N Informationsbits im Allgemeinen nicht in weniger als N Bits komprimieren kann . Die obige Darstellung verstößt dagegen bei weitem, wenn n groß genug ist, da .

Daher darf die Anzahl der Primzahlen nicht endlich sein.

Stärkere Ergebnisse

Die Sätze in diesem Abschnitt implizieren gleichzeitig den Satz von Euklid und andere Ergebnisse.

Satz von Dirichlet über arithmetische Progressionen

Dirichlet-Theorem besagt , dass für zwei beliebige positive coprime ganzen Zahlen a und  d , gibt es unendlich viele Primzahlen von der Form a  +  nd , wobei n auch eine positive ganze Zahl ist . Mit anderen Worten, es gibt unendlich viele Primzahlen, die zu a modulo d kongruent sind .

Primzahlsatz

Sei π ( x ) die Primzahlzählfunktion , die die Anzahl der Primzahlen kleiner oder gleich x für jede reelle Zahl  x angibt . Der Primzahlsatz dann heißt es, dass x / log x ist eine gute Annäherung an π ( x ) , in dem Sinne , dass der Grenzwert des Quotienten der beiden Funktionen π ( x ) und x / log x als x erhöht , ohne gebunden ist , 1 :

Unter Verwendung der asymptotischen Notation kann dieses Ergebnis umformuliert werden als

Dies ergibt den Satz von Euklid, da

Bertrand-Chebyshev-Theorem

In der Zahlentheorie ist Bertrands Postulat ein Satz, der besagt, dass es für jede ganze Zahl immer mindestens eine Primzahl gibt, so dass

Der Satz von Bertrand-Chebyshev kann auch als Beziehung zu angegeben werden , wobei die Primzahlzählfunktion (Anzahl der Primzahlen kleiner oder gleich ) ist:

für alle


Diese Aussage wurde erstmals 1845 von Joseph Bertrand (1822–1900) vermutet . Bertrand selbst hat seine Aussage für alle Zahlen im Intervall [2, 3 × 10 6 ] verifiziert . Seine Vermutung wurde 1852 von Chebyshev (1821-1894) vollständig bewiesen und so wird das Postulat auch Bertrand-Chebyshev-Theorem oder Chebyshev-Theorem genannt .

Hinweise und Referenzen

Externe Links