mini|hochkant=2.5|Satz des Euklid, Beispiel
Der Satz des Euklid, manchmal auch Satz von Euklid, ist ein Lehrsatz aus der elementaren Zahlentheorie und besagt, dass es unendlich viele Primzahlen gibt. Benannt ist er nach Euklid von Alexandria, der ihn als Erster im dritten Jahrhundert v. Chr. in seinen Elementen bewies. Jedoch kannten die Mathematiker der Antike das Konzept der Unendlichkeit noch nicht. Euklid selbst formulierte den Satz daher wie folgt: „Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.“
Eine Primzahl ist eine ganze Zahl größer als 1, die nur durch 1 und sich selbst ohne Rest teilbar ist. Die ersten Primzahlen sind 2, 3, 5 und 7. Der Satz des Euklid besagt, dass die Liste 2, 3, 5, 7, 11, 13, 17… aller Primzahlen nicht endet, genauso wie die Liste 1, 2, 3, 4, 5, 6 … aller natürlichen Zahlen nicht endet.
Der ursprüngliche von Euklid geführte Beweis ist direkt und konstruktiv. Zu einer gegebenen endlichen Liste von Primzahlen wird stets eine weitere noch nicht vorhandene Primzahl erzeugt, ohne diese jedoch explizit anzugeben. Vielmehr wird argumentiert, dass jede endliche Liste von Primzahlen unvollständig ist. Daraus wird gefolgert, dass es unendlich viele Primzahlen gibt. In der späteren Literatur wird oft fälschlicherweise behauptet, dass Euklids Argument anhand eines Widerspruchsbeweises aufgeführt sei. Jedoch lässt sich der Beweis leicht zu einem Widerspruchsbeweis umformulieren.
Nach dem Fundamentalsatz der Arithmetik können alle natürlichen Zahlen größer als 1 eindeutig in Primfaktoren zerlegt werden. Der Satz des Euklid ist daher eines der grundlegendsten Resultate der Zahlentheorie, da er zeigt, dass es unendlich viele unzerlegbare Grundbausteine der Zahlen gibt. Im Laufe der Zeit wurden neben Euklids Originalbeweis zahlreiche andere Beweise gefunden, die teilweise mathematische Techniken aus der Analysis, Kombinatorik oder auch der Topologie nutzen. Ab dem 19. Jahrhundert konnten zudem mit den Beweisen des Dirichletschen Primzahlsatzes und des Primzahlsatzes weitreichende Verallgemeinerungen erzielt werden. Während der Satz des Euklid lediglich aussagt, dass die Anzahl der Primzahlen unendlich groß ist, formulieren die modernen Primzahlsätze Regeln, wie häufig Primzahlen in gewissen Bereichen ungefähr anzutreffen sind.
Analoge Fragestellungen hinsichtlich der Häufigkeit von Primzahlzwillingen, Mersenne-Primzahlen oder Fermat-Primzahlen verbleiben bis heute unbeantwortet.
Beweis von Euklid Der Satz wurde erstmalsOlivier Bordellés: Arithmetic Tales. Springer-Verlag, 2020, S. 45. in Euklids Elementen im neunten Buch, Proposition 20, niedergeschrieben.
Originalformulierung Euklids Ausführung kann wie folgt ins Deutsche übersetzt werden: Originaltext (griechisch) ÜbersetzungΟἱ πρῶτοι ἀριθμοὶ πλείους εἰσὶ παντὸς τοῦ προτεθέντος πλήθους πρώτων ἀριθμῶν.
Ἔστωσαν οἱ προτεθέντες πρῶτοι ἀριθμοὶ οἱ Α, Β, Γ· λέγω, ὅτι τῶν Α, Β, Γ πλείους εἰσὶ πρῶτοι ἀριθμοί.
Εἰλήφθω γὰρ ὁ ὑπὸ τῶν Α, Β, Γ ἐλάχιστος μετρούμενος καὶ ἔστω ΔΕ, καὶ προσκείσθω τῷ ΔΕ μονὰς ἡ ΔΖ. ὁ δὴ ΕΖ ἤτοι πρῶτός ἐστιν ἢ οὔ. ἔστω πρότερον πρῶτος· εὐρημένοι ἄρα εἰσὶ πρῶτοι ἀριθμοὶ οἱ Α, Β, Γ, ΕΖ πλείους τῶν Α, Β, Γ. Ἀλλὰ δὴ μὴ ἔστω ὁ ΕΖ πρῶτος· ὑπὸ πρώτου ἄρα τινὸς ἀριθμοῦ μετρεῖται. μετρείσθω ὑπὸ πρώτου τοῦ Η· λέγω, ὅτι ὁ Η οὐδενὶ τῶν Α, Β, Γ ἐστιν ὁ αὐτός. εἰ γὰρ δυνατόν, ἔστω. οἱ δὲ Α, Β, Γ τὸν ΔΕ μετροῦσιν· καὶ ὁ Η ἄρα τὸν ΔΕ μετρήσει. μετρεῖ δὲ καὶ τὸν ΕΖ· καὶ λοιπὴν τὴν ΔΖ μονάδα μετρήσει ὁ Η ἀριθμὸς ὤν· ὅπερ ἄτοπον. οὐκ ἄρα ὁ Η ἑνὶ τῶν Α, Β, Γ ἐστιν ὁ αὐτός. καὶ ὑπόκειται πρῶτος. εὑρημένοι ἄρα εἰσὶ πρῶτοι ἀριθμοὶ πλείους τοῦ προτεθέντος πλήθους τῶν Α, Β, Γ οἱ Α, Β, Γ, Η· ὅπερ ἔδει δεῖξαι.Euclid’s Elements of Geometry. In: Euclidis Elementa. Edidit et Latine interpretatus est I.L. Heiberg, in aedibus B.G. Teubneri, 1883–1885, Übersetzung von Richard Fitzpatrick, S. 271.Es gibt mehr Primzahlen als jede vorgelegte Anzahl von Primzahlen.
Die vorgelegten Primzahlen seien a, b, c. Ich behaupte, dass es mehr Primzahlen gibt als a, b, c.
Man bilde die kleinste von a, b, c gemessene Zahl [= kgV, VII, 36]. Sie sei DE, und man füge zu DE die Einheit DF hinzu. Entweder ist EF dann eine Primzahl, oder nicht. Zunächst sei es eine Primzahl. Dann hat man mehr Primzahlen als a, b, c gefunden, nämlich a, b, c, EF. Zweitens sei EF keine Primzahl. Dann muss es von irgendeiner Primzahl gemessen werden [VII, 31]; es werde von der Primzahl g gemessen. Ich behaupte, dass g mit keiner der Zahlen a, b, c zusammenfällt. Wenn möglich, tue es dies nämlich, a, b, c messen nun auch DE; auch g müsste dann DE messen. Es misst aber auch EF. g müsste also auch den Rest, die Einheit DF, messen, während es eine Zahl ist; dies wäre Unsinn. Also fällt g mit keiner der Zahlen a, b, c zusammen; und es ist eine Primzahl nach Voraussetzung. Man hat also mehr Primzahlen als die vorgelegte Anzahl a, b, c gefunden, nämlich a, b, c, g, was zu beweisen war.Die Elemente von Euklid. In: Ostwalds Klassiker der exakten Wissenschaften. Verlag Europa-Lehrmittel, 4. Auflage, 2015, S. 204–205.
Erläuterungen: Zu jeder endlichen Menge von Primzahlen (gegebenes Objekt) gibt es danach eine Primzahl (gesuchtes Objekt), die dieser Menge nicht angehört. Euklid beweist dies konstruktiv, indem er ein Verfahren beschreibt, aus gegebenen endlich vielen Primzahlen (Euklid behandelt hier den Fall ) eine neue Primzahl zu gewinnen, indem man die Zahl bildet und einen ihrer Primfaktoren bestimmt. Im Beweis wird geometrisch-anschaulich argumentiert, indem gesagt wird, dass eine Strecke (Zahl) eine andere „misst“, wenn letztere durch erstere teilbar ist. In Euklids Ausführungen geht ferner sein bereits in Buch VII, Proposition 31 (die lautet: Jede zusammengesetzte Zahl wird von irgendeiner Primzahl gemessen)Die Elemente von Euklid. In: Ostwalds Klassiker der exakten Wissenschaften. Verlag Europa-Lehrmittel, S. 160. beschriebenes Verfahren zur effektiven Gewinnung eines Primfaktors einer vorgegebenen Zahl als „Unterprogramm“ ein.Peter Schreiber, Sonja Brentjes: Euklid. Teubner Verlagsgesellschaft, 1987, S. 41. Da Euklid im Originalwerk keine Möglichkeit hatte, eine willkürliche Liste von Primzahlen zu schreiben, verwendete er eine Methode, die er häufig anwandte, nämlich die Methode des verallgemeinerbaren Beispiels. Dabei wählt er nur drei Primzahlen aus und beweist mit der oben skizzierten allgemeinen Methode, dass er immer eine zusätzliche Primzahl finden kann. Euklid ging vermutlich davon aus, dass seine Leser davon überzeugt wären, dass ein ähnlicher Beweis funktionieren wird, egal wie viele Primzahlen ursprünglich ausgewählt werden.Victor J. Katz: A History of Mathematics. An Introduction. Second Edition, Addison Wesley Longman, 1998, S. 87.
Veranschaulichung des Beweises an einem Beispiel Die Beweisidee von Euklid lässt sich über folgendes Beispiel veranschaulichen. Dieses verwendet die ersten drei Primzahlen 2, 3 und 5. Aus diesen kann mit Euklids Methode eine neue Primzahl konstruiert werden, die in der Liste noch nicht vorkommt. Dafür wird die Zahl
betrachtet, die aus dem Produkt der Listenzahlen mit anschließender Addition von 1 gebildet wird. Diese Zahl 31 ist nun weder durch 2 noch durch 3 noch durch 5 teilbar. Das folgt daraus, dass die Differenz zweier Zahlen mit gemeinsamem Teiler wieder diesen Teiler hat: Es ist nach Konstruktion durch 2, 3 und 5 teilbar – hätte auch ihr Nachfolger 31 diese Eigenschaft, so auch Doch die 1 wird nur von 1 selbst geteilt. In der Tat ist 31 zum Beispiel wieder eine (neue) Primzahl und ungleich 2, 3 und 5.
In heutiger Fachsprache Trotz Euklids direkter Argumentation wird der Satz des Euklid von vielen Autoren in Standardwerken der Zahlentheorie als ein Widerspruchsbeweis wiedergegeben, zum Beispiel bei Jörg Brüdern oder Tom M. Apostol.Jörg Brüdern: Einführung in die analytische Zahlentheorie. Springer, S. 2.Tom M. Apostol: Introduction to Analytic Number Theory. Springer, S. 16–17.
In der Sprechweise der heutigen Mengenlehre stellt Euklid die folgende Behauptung auf: Gegeben sei eine endliche Menge von paarweise verschiedenen Primzahlen Dann gibt es mindestens eine weitere Primzahl die nicht in enthalten ist. Dazu bildet Euklid das kleinste Vielfache aller Primzahlen aus Dabei ist wichtig, dass alle bisherigen Primzahlen Teiler von sind. Dann bildet er und unterscheidet zwei Fälle: ist Primzahl, dann ist eine weitere Primzahl. ist keine Primzahl, dann hat einen Primteiler Angenommen, es wäre dann wäre ein Teiler von Es ist aber auch Teiler von und müsste folglich auch Teiler der Differenz sein. Ein Widerspruch!
Der Beweis kommt auch ohne die Fallunterscheidung aus: Angenommen, es gäbe nur endlich viele Primzahlen, etwa Dann wäre die Zahl wegen des Fundamentalsatzes der Arithmetik durch ein teilbar, also auch ein Widerspruch.
Beurteilung des Beweises Von Euklid wird oft fälschlicherweise berichtet, er habe sein Ergebnis durch Widerspruch bewiesen, beginnend mit der Annahme, dass die ursprünglich betrachtete endliche Menge alle Primzahlen enthält,Michael Hardy, Catherine Woodgold: Prime Simplicity. In: Mathematical Intelligencer. Vol. 31, No. 4, 2009, S. 44–52. obwohl es sich eigentlich um einen Beweis durch Fallunterscheidung, also eine direkte Beweismethode handelt. Der Philosoph Torkel Franzén stellte fest: „Euklids Beweis, dass es unendlich viele Primzahlen gibt, ist kein indirekter Beweis […]. Das Argument wird manchmal als indirekter Beweis formuliert, indem man es durch die Annahme ersetzt: ‚Angenommen sind alle Primzahlen.‘ Da diese Annahme jedoch nicht einmal im Beweis verwendet wird, ist die Neuformulierung sinnlos.“Torkel Franzén: Inexhaustibility. A Non-exhaustive Treatment. A. K. Peters, Ltd., 2004, S. 101.
Benno Artmann sieht im Beweis von Euklid ein Beispiel der Verwendung „endlicher Mittel zur Beherrschung des Unendlichen“. In dieser Hinsicht habe Euklid „Bahnbrechendes“ geleistet. Jedoch bildeten die Primzahlen nur ein Beispiel dieses Prinzips in Euklids Schaffen. Im selben Kontext wird seine Theorie der Parallelen und Kreistangenten sowie „Unvereinbarkeit“ (im Sinne des Euklidischen Algorithmus) von Artmann genannt.Benno Artmann: Euclid – The creation of mathematics. Springer, 1999, S. 279–281.
Die Zahlentheoretiker Gérald Tenenbaum und Michel Mendès France nennen Euklids Argument „wundervoll in seiner Schönheit und Einfachheit“ und weisen darauf hin, dass es sich in moderner Fachsprache auf die vier Symbole
reduzieren lässt. Dabei ist die Fakultät von und die erzeugte Zahl ist durch keine Zahl zwischen teilbar, weshalb es Primzahlen geben muss, die größer als sind.Gerald Tenenbaum, Michel Mendès France: The Prime Numbers and Their Distribution, Student Mathematical Library, Vol. 6, AMS, S. 2.
Der Beweis von Euklid wird, hinsichtlich der fundamentalen Bedeutung des Resultats für die Zahlentheorie, wegen seiner Einfachheit bis heute als elegant erachtet. Dennoch liefert er keine starke Methode, zu schätzen, wie viele Primzahlen es unter einer Schranke mindestens gibt. Zwar kann die Schranke , mit der Primzahlen abzählenden Funktion , induktiv aus Euklids Methode abgeleitet werden, doch dieses Resultat wird für die analytische Zahlentheorie als unbrauchbar angesehen. Dabei ist der natürliche Logarithmus von . Bereits mit nicht wesentlich schwierigeren Argumenten, zum Beispiel durch Ideen von Leonhard Euler und Pafnuti Lwowitsch Tschebyschow, können wesentlich stärkere Schranken für die Primzahlverteilung hergeleitet werden.Jörg Brüdern: Einführung in die analytische Zahlentheorie. Springer, S. 3–10. Dazu zählt die Schranke
für existierende Konstanten für alle .Jörg Brüdern: Einführung in die analytische Zahlentheorie. Springer, S. 4.
Bedeutung Erzeugung neuer Primzahlen Der Beweis des Satzes des Euklid zeigt eine Möglichkeit auf, wie aus einer oder mehreren vorgegebenen Primzahlen mindestens eine weitere Primzahl berechnet werden kann. Dazu bildet man das Produkt dieser Zahlen und addiert 1 zu dem Produkt, also Das Symbol ist das Produktzeichen.