Primzahlen: II. Kapitel: Die Unendlichkeit der Primzahlen

Aus Wikibooks
Zur Navigation springen Zur Suche springen


Nuvola apps bookcase 1.svg Primzahlen

Einleitung[Bearbeiten]

Wir können davon ausgehen, dass Primzahlen existieren, denn sonst würde es dieses Kapitel und das ganze Buch nicht geben. Obwohl ein paar kritische Leser einwerfen, dass dies gar nicht so sicher ist. Wie dem auch sei, wir gehen davon aus, dass es Primzahlen gibt. Um die große Frage, ob es nur endlich viele Primzahlen oder doch unendlich viele Primzahlen gibt, beziehungweise die Beantwortung dieser Frage geht es in diesem Kapitel. Es gibt also unendlich viele Primzahlen, und die folgenden Beweise handeln davon.

Euklids Beweis[Bearbeiten]

Der um 300 v. Chr. in Alexandria lebende Mathematiker Euklid hat folgenden Beweis geliefert: Angenommen, es gäbe endlich viele Primzahlen. Dann gäbe es die größte Primzahl . Man kann nun das Produkt aller Primzahlen bilden. ist durch alle Primzahlen von bis teilbar. Die Zahl ist wiederum durch keine der Primzahlen zwischen und teilbar. Daraus folgt, dass entweder eine weitere Primzahl ist, oder das Produkt von noch unbekannten Primzahlen ist. Egal was nun zutreffen mag, es gibt immer mehr Primzahlen als die Primzahlen, die schon bekannt sind.

Beispiele[Bearbeiten]

Angenommen, 11 sei die größte Primzahl, dann ist aber:

eine Primzahl größer als 11.

Angenommen, 13 sei die größte Primzahl, dann ist aber:

.

zwar selbst keine Primzahl, jedoch das Produkt der Primzahlen 59 und 509, beide größer als 13.


Stieltjes Beweis (1890)[Bearbeiten]

Angenommen seien die einzigen Primzahlen, die existieren. Dann gilt für die Zahl , dass sie sich in der Form zerlegen lässt, wobei für beide Zahlen und angenommen werden kann, dass sie größer 1 sind und dass jede Primzahl entweder oder teilt, aber nicht beide zugleich. Aus diesem Grund ist durch keine der existierenden Primzahlen teilbar. Da aber ist, ist eine weitere, größere Primzahl oder durch eine weitere noch unbekannte Primzahl teilbar.

Stieltjes Beweis ist im Grunde eine Verallgemeinerung von Euklids Satz, da dieser mit einen Spezialfall von Stieltjes Beweis darstellt.

Beispiel[Bearbeiten]

Angenommen es gäbe nur die 4 Primzahlen 2, 3, 5 und 7. Dann wäre N = 2 · 3 · 5 · 7 = 210. N ließe sich beispielsweise in die Faktoren 15 (= 3 · 5) und 14 (= 2 · 7) zerlegen. 15 + 14 = 29. Die Zahl 29 lässt sich weder durch 2, 3, 5 oder 7 teilen. Also ist 29 eine Primzahl oder durch wenigstens zwei, zueinander teilerfremde, Primzahlen teilbar, die sich nicht in der Menge {2, 3, 5, 7} befinden.

Schorns Beweis[Bearbeiten]

Vorbemerkung zu "paarweise teilerfremd"[Bearbeiten]

Dieser (Schorns) und der folgende (Goldbachs) Beweis erfordern eine Erklärung. Zwei Zahlen a1 und a2 (nicht unbedingt Primzahlen) ohne gemeinsame Primfaktoren, also mit ggT (größter gemeinsame Teiler) 1, heißen teilerfremd. Eine Menge von Zahlen heißt paarweise teilerfremd, wenn je zwei beliebige Zahlen aus dieser Menge teilerfremd sind.

Beweis[Bearbeiten]

Angenommen, es gäbe genau verschiedene Primzahlen. Dann setze . Die natürlichen Zahlen für sind paarweise teilerfremd. Wenn eine Primzahl die natürliche Zahl teilt, dann sind die Primzahlen unterschiedliche Primzahlen, was im Widerspruch zu unserer anfänglichen Annahme steht, dass es genau verschiedene Primzahlen gibt.

Beispiel[Bearbeiten]

Angenommen, man geht davon aus, dass es genau 3 Primzahlen gibt. Dann ist . Mit dieser Zahl kann man die folgenden 4 Zahlen konstruieren:

.

Alle vier Zahlen sind also paarweise teilerfremd. Das bedeutet auch, dass es mindestens 4 verschiedene Primzahlen gibt, was der Annahme widerspricht, dass es nur genau 3 Primzahlen gibt.

Vorteil[Bearbeiten]

Der große Vorteil an Schorns Beweis gegenüber den Beweisen von Euklid und Stieltjes ist, dass man bei ihm nur von einer bestimmten Anzahl von Primzahlen, nicht aber von konkreten Primzahlen ausgeht.

Goldbachs Beweis (1730)[Bearbeiten]

Wenn man eine unendliche Folge natürlicher Zahlen finden kann, die paarweise teilerfremd sind, dann existiert eine Folge von Primzahlen , für die gilt, dass die Primzahlen die natürliche Zahlen teilen. Diese Primzahlen sind dann alle verschieden. Wenn man also eine solche Folge findet, dann gibt es auch eine unendliche Anzahl von Primzahlen.

Es gibt eine solche Folge natürlicher Zahlen, die paarweise teilerfremd sind: die Folge der Fermat-Zahlen für . Es gilt nämlich . Dieser Satz lässt sich per vollständiger Induktion zeigen. Daraus folgt für , dass die Zahl dividiert. Angenommen eine Primzahl würde die beiden Fermat-Zahlen und dividieren, dann würde sie auch und dividieren. Daraus würde folgen. Da aber jedes ungerade und damit nicht durch 2 teilbar ist, ist jedes Glied dieser Folge teilerfremd zu allen anderen.

Bertrands Postulat[Bearbeiten]

Bertrands Postulat besagt: Für gilt, daß zwischen und wenigstens eine Primzahl liegt. Nun kann man die unendliche Folge der Natürlichen Zahlen in unendlich viele Abschnitte aufteilen: 2 bis 4; 5 bis 10; 11 bis 22; 23 bis 46; 47 bis 94; 95 bis 190; ... . In jedem dieser unendlich vielen Abschnitte muß wenigstens eine Primzahl liegen. Demzufolge müssen unendlich viele Primzahlen existieren.


Quelle: Die Primzahlbeweise von Thomas Jean Stieltjes, Schorn und Christian Goldbach sind aus dem Artikel Primzahl (Beweise) von der deutsprachigen de.wikipedia.org entnommen. Als ursprüngliche Quelle diente das Buch: The New Book of Prime Number Records, 3. Aufl., Springer Verlag von Paolo Ribenboim.

Die abzählbare Unendlichkeit[Bearbeiten]

Die Primzahlen bilden eine unendliche Teilmenge der Menge der Natürlichen Zahlen, und sind deshalb abzählbar unendlich.