ZUSAMMENFASSUNG:

Die ersten Primzahlen bilden Gruppen, in denen alle anderen Primzahlen enthalten sind. Dies wird zuerst dargestellt. Eine Analyse der Gruppen liefert eine Aussage über den Abstand von Primzahlen, eine Erweiterung des Bertrandschen Postulats, Goldbachs Vermutung und einen Algorithmus zur Berechnung von Primzahlen und zur Primfaktorzerlegung. Die Ergebnisse werden mit Riemanns Zeta-Funktion verglichen.

1. Einleitung

Eine ganze Zahl > 1, die keine natürlichen Teiler außer sich selbst und 1 hat, heißt Primzahl.
Über die Anordnung von Primzahlen sind schon viele Abhandlungen veröffentlicht worden. Eine gewisse Systematik ihrer Verteilung zeigt sich in der sogenannten Ulam-Spirale oder Primzahl-Spirale [1]. Sie wurde 1963 von dem polnischen Mathematiker Stanislaw Ulam während eines wissenschaftlichen Vortrags entdeckt, als er Zahlenreihen auf ein Papier kritzelte. Er begann mit der "1" in der Mitte und fuhr dann in Spiralform fort. Wenn man dann die Primzahlen markiert, stellt man fest, dass viele Primzahlen sich auf diagonalen Geraden befinden, wie es die Grafik (Abbildung 1) zeigt.



Abbildung 1: Die Ulam-Spirale

Vernachlässigt man die einzige gerade Primzahl 2, so tritt der Effekt noch deutlicher zutage. Dies hat mich angeregt, eine weitere systematische Anordnung zu untersuchen.

2. Prime Restklassen

Eine andere Systematik der Primzahlen wird in gewissen primen Restklassen, im folgenden auch "Stempel" genannt, sichtbar. Deren Bedeutung soll nun beschrieben werden. Mit p seien die Primzahlen bezeichnet und p1 , p2 , . . . seien die Primzahlen in aufsteigender Reihenfolge. Analog zum Faktorprodukt n! sei ein Primzahlenprodukt p# definiert durch


Dies ist das Produkt der ersten n Primzahlen. Wenn es nicht auf die Anzahl n ankommt, lasse ich den Index weg und bezeichne mit p#   ein solches Produkt.

2.1 Der 6-er Stempel

In vielen Artikeln über Primzahlen wird erwähnt, dass sämtliche Primzahlen > 3 die Form 6k - 1 oder 6k + 1; k = 1, 2, 3, . . besitzen. In Abbildung 2 ist dies bis zur Zahl 30 dargestellt. In der ersten Zeile, der Grundlinie, d.h. dem Stempel (zu dem immer auch die "1" gehört), sind die ersten 6 Zahlen dargestellt. In den weiteren Zeilen sind wiederum je 6 Zahlen enthalten. Eine Zahl am Kreuzungspunkt von Zeile und Spalte ergibt sich aus der Summe der Zahl am linken Rand und der Zahl am oberen Rand. Die 2 Kreise mit weißen Innenbereich sind die Primzahlen 2 und 3. Die schwarzen Punkte sind die restlichen Primzahlen ‹ 30. Die beiden Zahlen 2 und 3 sind die Primteiler von 6. Man nennt die Zahlen 1 und 5 die primen Restklassen modulo 6.


Abbildung 2: Der "6-er Stempel" und die Primzahlen < 30, angeordnet in Zeilen zu je 6 Spalten

Die Anzahl von 6 Spalten ergibt sich aus dem Produkt der ersten 2 Primzahlen 2 und 3. Alle Primzahlen außer 2 und 3 liegen auf der ersten und fünften Spalte, dem "6-er Stempel". Die Zahlen auf den anderen Spalten sind entweder durch 2 oder durch 3 teilbar.

2.2 Der 30-er Stempel

Auch in einer Anordnung der Zahlen zu je 30, dem Produkt der ersten 3 Primzahlen 2, 3 und 5, liegen die Primzahlen (ausgenommen die Primzahlen 2, 3 und 5) in bestimmten Spalten. Dies ist in Abbildung 3 bis zur Zahl 210 dargestellt. [siehe auch: "Kurt Diedrich: Primzahl-Lücken-Verteilung ohne Geheimnisse? www.primzahlen.de"]. Es wird hier eine graphische Darstellung gewählt, um die Zusammenhänge anschaulich zu machen und für alle verständlich, die an diesem Problem interessiert sind.

Stempel 30 scrollen
Abbildung 3: Der "30-er Stempel" und die Primzahlen < 210, in Zeilen zu je 30 Spalten angeordnet.

Wiederum sind die schwarzen Punkte die Primzahlen < 210. Zum Ablesen und Bestimmen einer Zahl sind am linken Rand und am oberen Rand Zahlen eingezeichnet (bei den Zahlen am oberen Rand sind die Ziffern untereinander geschrieben). Am Kreuzungspunkt von Zeile und Spalte steht diejenige Zahl, die sich aus der Summe der oberen und linken Zahl ergibt. Die Primzahlen 2, 3 und 5, die Primteiler, dargestellt durch 3 Kreise mit weißem Innenbereich, gehö nicht zum Stempel, der primen Restklasse. Auf den Spalten der Primteiler liegen keine weiteren Primzahlen. Die Linien sind gestrichelt, jede zehnte Linie ist zur besseren Orientierung durchgezogen. Auf die Zahlen, welche durch kleine Quadrate mit weißem Innenbereich gekennzeichnet sind, möchte ich am Ende dieses Abschnittes eingehen.
Bezeichnet man einen derartigen Stempel mit S, so kann man den 30-er Stempel mit Hilfe der Definition von pn# auch mit S5# bezeichnen. Seine Elemente sind die 1 und die Primzahlen, außer 2, 3 und 5 in der 1. Zeile, der Grundlinie. In Abbildung 3 sind sie mit einem Querstrich markiert. Diese bezeichne ich mit s1, s2, . . . ,sm . Wir haben hier 8 Spalten, in denen alle Primzahlen außer 2, 3 und 5 liegen. Hier ist also m=8. Nur die Elemente in der ersten Zeile gehören zum Stempel. Sämtliche Primzahlen < 30 haben die Form sj + 30k; j = 1, . . . ,m; k = 1, 2, 3, . . . . Es sind in der Abbildung 3 noch 6 weitere Zeilen dargestellt, die zeigen, wie der nächste Stempel entsteht.

2.3 Der 2-er Stempel

Der kleinste Stempel, den man auf diese Art bilden kann, besteht aus zwei Spalten. Die ersten Zeile enthält die 1 und als erste Primzahl die 2. Die nächste Primzahl 3 liegt in der zweiten Zeile. Dargestellt sind in Abbildung 4 nur 3 Zeilen.

2-Stempel
Abbildung 4: Der "2-er Stempel" und die Primzahlen < 6, angeordnet in 2 Spalten


Die erste Spalte enthält alle Primzahlen < 2. Dies ist wohlbekannt: Alle Primzahlen > 2 sind ungerade. Untersucht man die Stempel genauer, so stellt an fest, dass sie aufeinander aufbauen. Beispielsweise entstehen die Zahlen des 30-er Stempels, indem man die Zahlen aus den Spalten 1 und 5 des 6-er Stempels in den ersten 5 Zeilen auswählt und aus dieser Auswahl diejenigen Zahlen eliminiert, welche durch 5 ohne Rest teilbar sind. Dies sind die beiden Zahlen 5 und 25.

2.4 Der 210-er Stempel

Ebenso entsteht aus dem 30-er Stempel der 210-er Stempel oder S7#. Aus den Spalten des 30-er Stempels werden alle Zahlen bis 210 ausgewählt und diejenigen nicht in den Stempel aufgenommen, welche durch 7 ohne Rest teilbar sind. So erhält man die Stempel-Zahlen des 210-er Stempels. Sie sind in Abbildung 5 daran erkennbar, dass in ihren Spalten alle Primzahlen, außer 2, 3, 5 und 7 liegen. Die Teilmenge P7 = {2, 3, 5, 7} der Primzahlen bildet den Stempel.


Definition(2) Basis-Primzahlen sollen im folgenden diejenigen Primzahlen p1, p2, . . . ,pk heißen, die nicht zum Stempel gehören.


Für den Stempel S7# sind dies die Primzahlen 2, 3, 5 und 7. Nur die "Eins" und die anderen markierten Punkte der ersten Zeile gehören zum Stempel. Auch die Primzahlen > 210 bis 2310 sind in Abbildung 5 zusätzlich eingezeichnet.

Aus Platzgründen besteht Abbildung 5 aus 3 Teilen zu je 70 Zahlen. Die ersten 4 Primzahlen liegen nicht auf den Spalten des Stempels und sind durch Kreise mit weißem Innenbereich gekennzeichnet. Die Zahlen, welche durch Quadrate mit weißem Innenbereich markiert sind, sind durch 11 ohne Rest teilbar und sind für die Bildung des nächsten Stempels von Bedeutung. In den Stempeln S2#, S3# und S5# waren alle Zahlen der Stempel, mit Ausnahme der 1, Primzahlen.

Stempel 210 scrollen

Abbildung 5: Der 210-er Stempel und die Primzahlen < 2310, angeordnet in Zeilen zu je 210 Spalten.

Im Gegensatz dazu tritt hier zum ersten Mal der Fall auf, dass nicht alle Zahlen des Stempels prim sind. Dies ist für die weiteren Ausführungen wichtig. In diesem Stempel sind es die Zahlen 121, 143, 169, 187 und 209, Produkte mit Primfaktoren > 7. Alle Elemente des Stempels S7# sind wieder mit einem Querstrich gekennzeichnet.
Solche Zahlen kommen entsprechend auch in den höheren Stempeln vor. Ich werde im folgenden auf diesen Stempel öfters zurückkommen, denn an ihm läßt vieles über Primzahlen ablesen. Die Elemente des Stempels sind jeweils die Zahlen der ersten Spalte, die mit einem scharzen Punkt gekennzeichnet sind. Hinzu kommt noch die 1. Man sieht, dass in den nachfolgenden Zeilen der Stempel nicht präzise arbeitet, denn in jeder Zeile gibt es auch Lücken. Im Gegensatz dazu tritt hier zum ersten Mal der Fall auf, dass nicht alle Zahlen des Stempels prim sind. Dies ist für die weiteren Ausführungen wichtig. In diesem Stempel sind es die Zahlen 121, 143, 169, 187 und 209, Produkte mit Primfaktoren > 7. Alle Elemente des Stempels S7# sind wieder mit einem Querstrich gekennzeichnet. Solche Zahlen kommen entsprechend auch in den höheren Stempeln vor. Ich werde im folgenden auf diesen Stempel öfters zurückkommen, denn an ihm läßt vieles über Primzahlen ablesen.

2.5. Anzahl der Elemente

Zunächst beschäftigen uns wir mit der Anzahl der Elemente in den einzelnen Stempeln. Der kleinste Stempel S2# hat nur ein Element, s1 = 1.

Im nächsten Stempel S3# liegen die Primzahlen > 5 auf 2 Spalten. Dieser Stempel besitzt also 2 Elemente: s1 = 1 und s2 = 5. Da S5# eine Breite von 30 hat, bilden wir diesen Stempel aus den ersten 5 Zeilen des Stempels S3#. Von den Zahlen s , s + 6, s + 12, s + 18, s + 24, welche in der Spalte s1 liegen, ist genau eine durch 5 teilbar. Auch die Zahlen s1, s1 + 6, s1+12; s1+18; s1+24 liegen in einer Spalte und genau eine davon ist durch 5 teilbar. Diese beiden durch 5 teilbaren Zahlen werden nicht in den Stempel S5# aufgenommen. Wir erhalten somit 8 Elemente in diesem Stempel. wenn wir dieses Verfahren fortsetzen und zu den nächst höheren Stempeln übergehen, erhalten wir folgendes Ergebnis:


Die Anzahl der Elemente eines Stempels  Spn#  ist  Anzahl Elemente

Wie wir anhand der Stempel sehen, z. B. beim 210-Stempel, gehören die ersten Primzahlen, hier die 2, 3, 5 und 7, nicht zum Stempel. Der Stempel wird jedoch ausschließlich durch diese Primzahlen gebildet.


Definition(3): Die zu pi; (i = 1, , , n) teilerfremden Zahlen Sj heißen Stempel  Spn#   . Ein Stempel  Spn#  wird durch die Primzahlen p1, p2, p3 , , , pn der Teilmenge Pn = 2, 3, , , pn gebildet. Diese Primzahlen heißen im folgenden die Primteiler des Stempels  Spn# .


Definition(4): a mod m heißt prime Restklasse, wenn a und m teilerfremd sind, d.h. ggT(a,m)=1.


Bei den Stempeln handelt es sich um prime Restklassengruppen. Beispielsweise betrachten wir den Stempel S5#. Die Primteiler von 30 sind 2, 3 und 5. Die eulersche φ-Funktion berechnet die Ordnung der Gruppe:


Dabei sind p|n alle Primteiler von n.

Auch damit kann die Anzahl der primen Restklassen berechnet werden. Beispielsweise ergibt sich


und die 8 Elemente sind 1, 7, 11, 13, 17, 19, 23 und 29. Genau dies sind die Elemente von S5# (Abb. 3).

Die Zahlen 1 und gehören immer zu einem Stempel. Beim Stempel S7# sind die Elemente sj zu den Primzahlen 2, 3, 5 und 7 teilerfremd. Für sie gilt:



In den nächsten Intervallen 211 bis 420, 421 bis 630 usw. wiederholen sich die Ergebnisse, wobei einige Zahlen aus dem Stempel entfallen. Wir können aber bei diesen Intervallen von einer Kopie des ersten Intervalls 1 bis 210 sprechen, genauso wie ein Stempel ein eingeprägtes Muster (eingermaßen) kopiert.
Bevor ich mit meinen Ausführungen fortfahre, möchte ich einen bekannten Satz zitieren. Es ist der

Satz 1: Hauptsatz der elementaren Zahlentheorie:

Jede ganze Zahl n > 1 , n ∈ N , besitzt genau eine Darstellung

mit Primzahlen p1 < p2 < pr und Exponenten m1 ≥ 1,   m2 ≥ 1  ,   ,  ,   mr ≥ 1.
Schon Euklid (325-265 v. Chr.) hat erkannt, dass eine Primzahl, welche das Produkt von a * b teilt, auch Teiler von a oder Teiler von b ist. Bewiesen wurde der Hauptsatz der elementaren Zahlentheorie von C. F. Gauss (1777-1855) und E. Zermelo (1871-1953).


Wir betrachten einen Stempel  Spn#  mit den Elementen sj . Er hat die Breite pn#. Das erste Element ist s1=1, die erste Primzahl in einem Stempel ist s2=pn+1. Ergänzt man den Stempel (die oberste Zeile) zu einem Rechteck mit der Höhe pn+1, um den nächsten Stempel zu bilden, so liegt in diesem Rechteck in jeder Spalte dieses Stempels genau eine Zahl, die durch s2 teilbar ist. Die Zahlen sj + k * pn# ; k=0, 1, 2, 3, . . . , pn+1 -1 liegen auf einer Spalte eines Stempels Spn#. Die Zahl pn# ist das Produkt der Primzahlen p1, , , pn, also nicht durch pn+1 teilbar. Alle Elemente sj sind kleiner als pn#. Durch die Stempelbildung ist s2 die nächste Primzahl, also ist s2 = pn+1. Entweder ist sj selbst durch s2 teilbar. Dann ist erst wieder die Zahl sj +pn+1 * pn# durch s2 teilbar oder sj ist nicht durch s2 teilbar. Dann ist s2 sj durch s2 teilbar.


Satz 2: Für pn# > 2 gilt: Die Stempel sind symmetrisch.


Beweis: Die älteste Vorgehensweise, um die Primzahlen zu ermitteln, ist das Sieb des Eratosthenes ( ca. 300 v. Chr.). Die erste Zahl, die nur durch sich selbst und 1 teilbar ist, ist die 2, die erste Primzahl. Zunächst werden alle Vielfachen von 2 aus der Zahlengeraden weggestrichen. Als nächste Primzahl wird die 3 erkannt. Alle Vielfachen der 3 werden weggestrichen usw. .


Wenn wir diese Vorgehensweise mit den Primzahlen 2, 3, 5 und 7 auf die Zahlen bis 210, dem Produkt dieser 4 Primzahlen anwenden und die Primteiler selbst auch ausstreichen, erhalten wir den Stempel S7#. Das gleiche Ergebnis erhalten wir, wenn wir die 4 Primzahlen bei 210 einsetzen und rückwärts schreitend ihre Vielfachen ausstreichen. Damit erklärt sich die Symmetrie. Das gleiche Ergebnis ergibt sich auch, wenn wir mit den ersten 5 Primzahlen 2, . . . , 11 den Zahlenbereich bis 2310 = 11# vorwärts und rückwärts durchlaufen oder allgemein für jedes Primzahlenprodukt pn# mit n > 1. ( = quod erat demonstrandum)


Bei 210 treffen sich die 4 ersten Primzahlen zum ersten Mal auf der Zahlengeraden wieder. Das Sieb des Eratosthenes setzt die Primzahlen bei 0 ein und alle Primzahlen überspringen damit immer die 1. Entsprechend wird, wenn wir den allgemeinen Fall betrachten und bei einem beliebigen Stempel bei pn#, n > 2 beginnen und die Primzahlen rückwärts bis 0 laufen lassen, die Zahl pn# - 1 stets übersprungen. Das bedeutet: 1 und pn# - 1 gehören immer zu einem Stempel.


Eine Abschätzung der Anzahl der Primzahlen

Ein Stempel enthält alle Primzahlen bis pn# außer den n Primteilern, die kleiner sind als s2. Außerdem enthält jeder Stempel die 1, die keine Primzahl ist. Es gilt daher :


Satz 3: Die Elemente sj des Stempels  Spn#  bilden zusammen mit den Elementen sj + k * pn# ; j = 1, . . . , m ; k = 1, 2, 3, . . . eine Gruppe mit der Multiplikation als Operation.


Beweis: Die Konstruktion der Stempel beseitigt zunächst alle Zahlen, die durch 2 teilbar sind und die 2 selbst. Im nächsten Schritt wird die nächste Primzahl 3 und alle ihre Vielfachen beseitigt, usw. Durch die Konstruktion des Stempels Spn# werden alle Primteiler und ihre Vielfachen beseitigt. Jede Zahl t + pn# , die nicht Element des Stempels ist, ist durch einen der Primteiler teilbar. Damit sind auch die Zahlen t + k *pn# durch einen der Primteiler teilbar. Nach Satz 1 ist die Zerlegung in ein Produkt von Primzahlen eindeutig. Damit liegen alle Elemente eines Stempels und ihre Produkte auf den Spalten Stempels Spn#.


Für den kleinsten Stempel S2# ist die Eigenschaft einer solchen Gruppe wohlbekannt: Produkte von ungeraden Zahlen sind ungerade.


Satz 4: In jedem Stempel Spn+1 sind diejenigen Zahlen prim, die < pn+12 sind.


Beweis: Die Elemente eines Stempels sind Repräsentanten der primen Restklassen mod pn# aus der Reste-Menge {0, 1, 2, . . . , pn# - 1 }, die zu pn# relativ prim sind. In jedem Stempel oder dieser Reste-Menge ist die erste Zahl die 1, das Einheitselement. Das nächste Element s2 ist pn+1. Das kleinste Produkt, das mit diesen ganzzahligen positiven Elementen gebildet werden kann, ist somit s22 und deshalb sind alle ganzzahligen positiven Elemente, die kleiner als dieser Wert sind, Primzahlen.

3. Eine Erweiterung des Bertandschen Postulats

Bei Primzahlen gilt das Bertrandsche Postulat:


Satz 5: (Bertrands Postulat): Für jedes n > 1 , n ∈ N gibt es zwischen n und 2n mindestens eine Primzahl.


Bewiesen wurde dieser Satz von P. L. Tschebyschow (1821-1894) und dann auch von J. S. Hadamard (1865-1963) und P. Erdös (1913-1996).


Im folgenden will ich eine Aussage über den Abstand von 2 Primzahlen treffen, die präziser ist als das Bertrandsche Postulat. Dazu wird zunächst der Stempel S7# näher untersucht. Die Ergebnisse sind entsprechend auf alle Stempel anwendbar. Es gilt der


Satz 6: In jedem Intervall der Größe 2pn - 2, dessen obere Intervallgrenze < p2 n+1 ist, liegt mindestens eine Primzahl.


Beweis : Ich beginne mit dem Stempel S7# und weise dort Eigenschaften nach, die auch für höhere Stempel gelten. Wenn wir die Modulo-Funktion mit den ersten vier Primzahlen 2, 3, 5 und 7 im Bereich bis 210 bilden, so erhalten wir für die Zahlen von 1 bis 210 unterschiedliche Ergebnisse. Beispielsweise erhält man für die Zahl 63 die Ergebnisse 63 mod 2 = 1,  63 mod 3 = 0,  63 mod 5 = 3 und 63 mod 7 = 0. Ich bezeichne dieses Ergebnis als Quadrupel {1, 0, 3, 0}. Eine Zahl die zu den ersten 4 Primzahlen teilerfremd ist, beispielsweise die Zahl 89 liefert das Quadrupel {1, 2, 4, 5}. Da die Zahl 89 teilerfremd ist, sind natürlich alle 4 Zahlen ≠ 0. Der Stempel S7# ist symmetrisch in 210, deshalb erhält man für 121, der zu 89 symmetrischen Zahl 1 als Ergebnis {1, 1, 1, 2}, d. h. Zahlen, die mit dem Quadrupel von 89 summiert das Quadrupel {2, 3, 5, 7} ergeben, also wiederum die 4 Primzahlen. Für 147, die zu 63 symmetrische Zahl erhält man das Ergebnis {1, 0, 2, 0}. Die entsprechenden Summen sind mod pi mit pi gleich.


Anmerkung: Die Zahl 121 ist keine Primzahl, jedoch teilerfremd zu 2, 3, 5 und 7 und daher ein Element aus S7# .


Abbildung 6: Die Modulo-Bildung füe alle Elemente von S7#

Die Elemente sj von S7# und ihre Quadrupel sind in Tabelle 6 aufgelistet. In S7# kommt jede mögliche Kombination der Modulo-Bildung genau einmal vor. Dies folgt aus den Chinesischen Restsatz. Die Modulo-Funktionen liefern den Rest zu den vorausgehenden Vielfachen der Primzahlen 2, 3, 5 und 7. Die Funktionen pi - (sj mod pi) liefern die Differenzen zu den nachfolgenden Vielfachen von pi. Wegen der symmetrischen Lage der Elemente sj in S7# gilt


Dies bedeutet: Für die zu sj symmetrischen Zahlen 210 - sj erhält man die nachfolgenden Vielfachen aus derselben Tabelle (Spalte 210 - sj und unterste Zeile, grau unterlegt). Daraus folgt, dass die Differenz von einem Element aus S7# zu einem Vielfachen von p4 = 7 höchstens p4 - 1, also 6 betragen kann. Dies gilt sowohl für die Differenz zum nachfolgenden sj+1 als auch für die Differenz zum vorausgehenden sj. Damit gilt: Der Abstand zwischen zwei Elementen sj und sj+1 ist höchstens 2p4 - 2 = 12 und daher liegt in jedem Intervall der Größe 2ps4 - 2 mindestens ein sj.


Entsprechend liegt zwischen jedem Vielfachen von pn+1, also hier von 11 bis zum Quadrat 121 mindestens eine Primzahl.


Im Stempel S7# liegt zwischen jedem Vielfachen von 7 mindestens ein Element sj . Dies muss laut Chinesischem Restsatz nicht für jeden Stempel Spn# bzw. nicht für jedes sj im ganzen Bereich jedes Stempels gelten. Wegen Satz 4 können wir uns darauf beschränken, in Spn# nur den Bereich ≤ p2n+1 zu betrachten. Wenn wir den Stempel S2# betrachten, so sehen wir: Alle ungeraden Zahlen bis zum Quadrat der nächsten Primzahl 3 sind Primzahlen. Erst ab 9, dem Quadrat der nächsten Primzahl 3, wird diese aktiv, um Vielfache von 3 aus der Zahlengeraden nach dem Sieb des Eratosthenes zu entfernen. Dies gilt auch für die nächste Primzahl 5, welche ab 25 aktiv wird (Abb. 2). Alle Produkte mit 5, die kleiner als 25 sind, werden durch Vielfache der Primzahlen 2 und 3 aus der Zahlengeraden entfernt. Entsprechendes gilt auch für alle weiteren Stempel. Daraus folgt, dass sich beispielsweise der Stempel S3# wiederholt bis p22 = 25.


Gehen wir zum nächsten Stempel über, so fallen außer der Zahl pn+1, welche zum Primteiler wird, bis pn+22 genau 2 Zahlen aus dem Stempel heraus: pn+12 und pn+1 * pn+2. Daraus folgt, dass diejenigen sj , die zwischen pn+12 und pn+1 * pn+2 liegen, Primzahlen sein müssen, ebenso diejenigen sj, die zwischen pn+1 * pn+2 und pn+22 liegen.


Nach den eben erläuterten Eigenschaften genügt es also zu zeigen:


Satz 7: Für n > 2 gilt: Bis n2 liegt zwischen jedem Vielfachen von n mindestens eine Primzahl.


Beweis : Ich beginne mit einem Beispiel aus dem Bereich der Primzahlen. Ich wähle den Stempel S7# und den Bereich bis 121, dem Quadrat der Primzahl 11, und betrachte hier den Zahlenbereich ]99, . . . ,110[ . Die Intervallgrenzen sind zwei aufeinanderfolgende Vielfache von 11. In diesem Bereich muss also, wie behauptet, eine Primzahl liegen. Dieser Bereich hat 5 gerade und 5 ungerade Zahlen. Die geraden Zahlen werden durch die Vielfachen von 2 entfernt.


Anmerkung: Mit ]a, . . . ,b[ wird ein Intervall bezeichnet, das die Zahlen enthält, die größer als a und kleiner als b sind. Die Zahlen a und b gehören nicht zu dieser Zahlenmenge.


Für die ungeraden Zahlen gilt: Maximal 2 davon können durch Vielfache von 3 entfernt werden, maximal je eine durch Vielfache von 5 und von 7. Dies ist der schlimmste Fall ("worst case"), der eintreten kann. Es bleibt also von den 5 ungeraden Zahlen eine &uuml;brig. Dies muss eine Primzahl sein. Dies gilt für alle Intervalle ](i-1) * 11, . . . ,i * 11[  für i = 1, . . . ,11. Ich habe hier ein Intervall gew&auml;hlt, das oberhalb der 49 liegt. Für Intervalle mit der Obergrenze kleiner als 25 erh&ouml;ht sich die Anzahl der Primzahlen in einem solchen Intervall entsprechend. Die Annahme, dass zwischen zwei aufeinanderfolgenden Vielfachen von 11 bis zum Quadrat 121 keine Primzahl liegt, führt also zu einem Widerspruch.

Wir haben hier eine multiplikative Abbildung der ungeraden Zahlen, die kleiner sind als pn, auf jedes der Intervalle ](i - 1) ∗ pn, . . . ,i ∗pn[ für i = 2, . . . ,pn. Eine ungerade Zahl, die keine Primzahl ist, bildet dabei mit einem ihrer Primfaktoren ab.

Im Gegensatz zur Addition mit dem neutralen Element 0 gehört das neutrale Element 1 der Multiplikation zu den positiven ganzen Zahlen und ist ungerade. Dies wirkt sich bei jeder multiplikativen Abbildung auf die oberen Intervalle aus. Den unteren Intervallen werden die bereits vorhandenen Primzahlen zugeordnet.

Bei dieser Abbildung gibt es also eine Ausnahme: Die 1, das neutrale Element, kann keine multiplikative Abbildung vollziehen. Werden nur unterschiedliche ungerade Zahlen im Zielbereich getroffen, so haben wir den worst-case: Eine ungerade Zahl bleibt übrig. Sie muss eine Primzahl sein. Werden bei dieser Abbildung auch gerade Zahlen getroffen oder ungerade Zahlen mehrfach getroffen, so erhöht sich die Anzahl der Primzahlen im Zielbereich entsprechend.

Dies gilt nicht nicht nur für Primzahlen, sondern auch für alle ungeraden Zahlen > 1. Nun zu den geraden Zahlen: ein Intervall   ]n, . . . ,2n[ mit n gerade enthält genauso viele ungerade Zahlen, wie das Intervall ]n+1, . . . ,2(n+1)*n[. Ein Beispiel für Intervalle mit geraden Zahlen als Intervallgrenzen zeigt die Abbildung 7. Es ist allgemein bekannt, dass in jedem Intervall   ]10, . . . , 20[ ,  ]20, . . . , 30[ bis   ]90, . . . , 100[ mindestens eine Primzahl liegt. Satz 7 erklärt, warum dies so ist.

Intervalle scrollen
Abbildung 7: Abbildung der Intervalle   ]10, . . . , 20[   bis   ]90, . . . , 100[


In jedes Intervall werden die ungeraden Zahlen 3, 5, 7 und 9 abgebildet. Die Zahl 1 kann nicht abbilden und die 9 bildet durch den Primdivisor 3 ab. Im 9. Intervall ]90, . . . , 100[ treffen alle Abbildungen auf unterschiedliche ungerade Zahlen und wir haben deshalb den worst case, d. h. dort liegt nur eine Primzahl. Im 8. Intervall bildet die 7 auf eine gerade Zahl ab, alle anderen Abbildungen sind ungerade und unterschiedlich, dort liegen 2 Primzahlen. Ein anderes Beispiel liefert das 3. Intervall. Dort bilden die Zahlen 5 und 7 auf die gleiche Zahl 35 ab und deshalb liegen in diesen Intervall auch 2 Primzahlen. Alle Intervalle mit Produkten uj * uk < 10; ungerade und uk < 10; ungerade und uj * uk ≠ 10 enthalten mehr als eine Primzahl.


Bei den Intervallen ]11, . . . ,22[ usw. ist das Intervall mit der kleinsten Anzahl von Primzahlen das Intervall ]110, . . . ,121[ mit der Primzahl 113. Nun zurück zu den oben erwähnten größeren Intervallen. Dort lassen sich mit den ungeraden Zahlen uj und uk mit uj < 1000 und uk < 1000 viele unterschiedliche Produkte bilden, die zwischen 1000 und 1 000 000 liegen und die ungleich piun mit pi < 1000 sind. Desgleichen gibt es einige Primzahlen kleiner als 1000, etwa diejenigen zwischen 800 und 1000. Fast die Hälfte von ihnen bildet in einem Intervall nur einmal ab und zwar auf eine gerade Zahl. Ein anderer Teil dieser Primzahlen bildet im nächsten Intervall nur einmal ab und zwar auf eine gerade Zahl. Wiederum ein anderer Teil bidet im dritten Intervall nur auf eine gerade Zahl ab, usw.. Deshalb kann der "worst case " nicht mehr eintreten, d.h. mehr als eine Primzahl liegt in jedem Intervall. Die Intervalle der Größe 21, d.h. die Intervalle ]21, . . . , 42[, ]42, . . . , 63[ bis ]420, . . . , 441[ haben bereits mindestens 2 Primzahlen, Intervalle der Größe 100 mindestens 7 und Intervalle der Größe 500 mindestens 26 Primzahlen.


Es genügt, die Intervalle bis 1 000 000 zu untersuchen. Dies hat mehrere Gründe:


1. Die " 1 " bildet nicht ab.
2. Mit der Funktion x/ln(x) wird die Anzahl der Primzahlen < x abgeschätzt. Dann kann die Anzahl der Primzahlen im Intervall ]x2 -x, . . . ,x2[ abgeschätzt werden mit

 

. Auch diese Funktion ist eine aufsteigende Funktion (für x > 2), d.h. die Anzahl der Primzahlen in den Intervallen nimmt allmählich zu.

Die Tabelle 8 zeigt die minimale Anzahl von Primzahlen in den Intervallen bis ]39 800, . . . ,40 000[. In der obersten Zeile sind die Zahlen 0, 1, . . . ,9 eingetragen, in der ersten Spalte die Zahlen 0, 10, . . . ,200.

Stempel 30 scrollen
Abbildung 8: Minimale Anzahl von Primzahlen in den Intervallen bis 200 ∗ 200

Als Beispiel ist in der obersten Zeile die Zahl 8 mit grauem Hintergrund gekennzeichnet. Bei den Zahlen in der ersten Spalte ist die Zahl 20 mit grauem Hintergrund belegt. Am Kreuzungspunkt der Zeile, die mit 20 beginnt, und Spalte, die mit 8 beginnt (20+8=28), befindet sich die Zahl 3. Dies bedeutet: In jedem der Intervalle ]28, . . . , 2*28[,  ]2*28, . . . ,3*28[ bis ]27*28, . . ,28*28[ befinden sich mindestens 3 Primzahlen. Ein weiteres Beispiel: Die Zahl 11 in der letzten Zeile bedeutet: Die Intervalle zwischen 200, 400, 600,. . . , 40 000 haben mindestens 11 Primzahlen.


Untersucht man mit Hilfe einer Tabelle der Primzahlen größere Intervalle z.B. die Intervalle ]1000, . . . , 2000[  bis ]999 000, . . . ,1 000 000[, so stellt man fest, dass dort in jedem Intervall mehr als 50 Primzahlen liegen. Mit Satz 7 ist auch Satz 6 bewiesen. Dieser Satz ist hilfreich für einige Probleme bei Primzahlen.


Der Einfachheit halber werden im folgenden nicht alle Zahlen benutzt, sondern nur die Primzahlen: Für p > 2 gilt:


Bis p2 ist der Abstand zweier benachbarter Primzahlen < 2p. Dualität: Mit Satz 4 und Satz 7 können wir von dualen Sätzen sprechen: Bei den ganzzahligen Werten > 1 der primen Restklassengruppe (Z/pn#Z) gibt es bis pn+12 nur Primzahlen und zwischen jedem Vielfachen von pn+1 gibt es bis mindestens eine Primzahl.


Bei großen Zahlen kommt es vor, dass man zwar eine Primzahl kennt, nennen wir sie vorerst pn+1, aber die vorausgehende Primzahl pn nicht. Da pn+1 - pn ≥ 2 gilt, wenn wir jetzt n+1 durch n ersetzen, auch die folgende Aussage:


Satz 8: Seien n und n+1 zwei natürliche Zahlen > 1. Dann gibt es zwischen n2 und (n+1)2 mindestens zwei Primzahlen.


Beweis:
  1. Zwischen 1 und 4 gibt es 2 Primzahlen : 2 und 3.
  2. Es gilt die Formel (n-1)2 = n2 - 2n - 1. Wenn wir diese Formel für ≥ 3 interpretieren, so heiÿt dies: (n-1)2 ist im vorletzten Intervall (-2n) die erste Zahl (+1) bezüglich n2. Dies bedeutet, dass die Primzahl, bzw. die Primzahlen des vorletzten Intervalls größer sein müssen als (n-1)2. Auch im letzten Intervall vor n2 liegt noch mindestens eine Primzahl. Somit haben wir mindestens zwei Primzahlen zwischen n2 und (n + 1)2.

4. Die Goldbachsche Vermutung

Im Jahre 1742 äußerte C. Goldbach (1690-1764) in einem Brief an L. Euler (1707-1783) die Vermutung, ob jede ungerade natürliche Zahl n > 5 als Summe von drei Primzahlen geschrieben werden kann, bzw. ob jede gerade natürliche Zahl n > 4 als Summe von zwei Primzahlen geschrieben werden kann. Beide Sätze sind als Goldbachsche Vermutung bekannt.


Es gibt mehrere Ansätze, diese Vermutung zu beweisen. Dies ist deshalb schwierig, weil Primzahlen durch Bildung von Produkten entstehen und die Bildung einer Summe nicht damit in Zusammenhang gebracht werden kann.


Zunächst soll eine graphische Darstellung einen Überblick geben. Ich stelle die Zahlengerade in der Waagrechten dar und zeichne die Primzahlen ein. Sie sind durch schwarze Punkte in der obersten Zeile gekennzeichnet.


Wir bilden eine Matrix der natürlichen Zahlen von 1 bis n. Dann zeichnen wir in jeder Spalte, die mit einer Primzahl beginnt, die Primzahlen in senkrechter Richtung ein. Auch in der ersten Spalte zeichnen wir die Primzahlen ein.

Goldbach-Bild scrollen

Abbildung 9: Primzahlen in waagrechter und senkrechter Darstellung

Somit erhalten wir ein symmetrisches Bild der Primzahlen. In Bild 9 sind am oberen und linken Rand die Zahlen in 5-er Schritten eingezeichnet.


In der Zeichnung ist zur Orientierung jede zehnte Linie durchgezogen, die 50. Linie ist etwas dicker. Eine Diagonale von 45°, beginnend an einer ungeraden Zahl 2n-1 am oberen Rand durch dieses Zahlenfeld trifft auf Primzahlen. Man kann hier unmittelbar Lösungen für die Goldbachsche Vermutung ablesen. Zum Beispiel trifft die Diagonale, die bei 127 beginnt, bei 109 auf die Zahl 19. Diese beide Zahlen sind nach Konstruktion Primzahlen und ihre Summe ist 128. erfolgen wir die Diagonale weiter, so erhalten wir den Schnittpunkt 31 bei 97, was ebenfalls 128 ergibt und den Schnittpunkt 61 bei 67.


Um Lösungen für die Goldbachsche Vermutung zu finden, müssen wir die Diagonale bei einer ungeraden Zahl beginnen, da die Zeichnung die Null-Zeile nicht enthält, sondern erst bei 1 beginnt. Es fällt auf, dass Diagonalen, die bei einer Primzahl beginnen, schwieriger zum nächsten Schnittpunkt mit einer Primzahl führen, als viele andere Diagonalen, die bei einer ungeraden Zahl beginnen, die keine Primzahl ist. Dies zur Einführung in die Problemstellung.


Wir haben im vorigen Kapitel gezeigt, dass in jedem Intervall der Gröÿe 2pn+1 mindestens 2 Primzahlen liegen. Wir wollen eine dieser Primzahlen fixieren. Wenn wir dies tun, haben wir noch mindestens eine Primzahl im genannten Intervall. Wir wollen dies am Beispiel mit den ersten 4 Primzahlen 2, 3, 5 und 7 demonstrieren. Der Füll-Bereich hat dann die Gröÿe 22.


Eine der Primzahlen wird auf die 1 fixiert, d. h. wir verwenden die Zahlen 2, 3, 5 und 7 nur so, dass sie nicht auf die 1 treffen. Wir können dann die 2 nur auf der 2 beginnen lassen. Die Primzahl 3 können wir auf 2 einsetzen. Dann trifft sie auf 2, 5, 8 usw.. Wir können sie aber auch auf 3 einsetzen. Dann trifft sie auf 3, 6, 9 und die anderen Vielfachen von 3. Entsprechend dieser Vorgehensweise ist die Primzahl 5 auf 2, 3, 4 und 5 einsetzbar und die Primzahl 7 ist auf 2, 3, 4, 5, 6 und 7 einzusetzen. Im Algorithmus ist festgelegt: Ist ein Feld einer Zeile mit einer Zahl > 0 belegt, so wird das Feld nicht geändert, wenn eine neue Zahl das gleiche Feld belegen soll. Dieses Festhalten an der zuerst eingespeicherten Zahl ist nicht zwingend notwendig. Hier dient es nur zum besseren Verständnis der Abbildung 10.


Gold-Prim scrollen

Abbildung 10: Startpositionen von P7 = {2, 3, 5, 7} bei Fixierung einer Primzahl

Insgesamt ergeben sich damit 48 Einsatzmöglichkeiten. Dies ist in Tabelle 10 dargestellt. Die erste Zeile im Bereich 1 bis 22 der Tabelle entsteht folgendermaßen: Zunächst wird der Füll-Bereich von 1 bis 22 gelöscht, d. h. mit Nullen vorbelegt. Die Primzahl 2 wird auf 2 eingesetzt. Sie selbst und ihre Vielfachen belegen die Zahlen 2, 4, 6, . . . , 22. Auch die Primzahl 3 wird auf 2 eingesetzt. Sie und ihre Vielfachen belegen dann die Zahlen 2, 5, 8, 11, 14, 17 und 20. Die Primzahl 5 wird ebenfalls auf 2 eingesetzt, ebenso die Primzahl 7. Damit ist die erste Zeile komplett.


In der zweiten Zeile wird mit den Primzahlen 2, 5 und 7 ebenso verfahren, wie in der 1. Zeile. Lediglich die Primzahl 3 startet jetzt auf Position 3. Sie und ihre Vielfachen belegen dann die Felder 3, 6, 9, 12, . . . , 21. In entsprechender Weise entstehen die weiteren Zeilen. Bemerkenswert ist die letzte Zeile. In ihr werden die Primzahlen genau so eingesetzt, wie wir es aus dem Sieb des Eratosthenes kennen.


Wie wir sehen, gibt es 48 Möglichkeiten und wir können deshalb versuchen, sie den Elementen sj von S7# zuzuordnen. Zunächst zur letzten Zeile. Sie ist zweifellos der 1 von S7# zuzuordnen. Die Elemente in S7# sind, wie wir wissen, nicht durch die ersten 4 Primzahlen teilbar. Darüber hinaus hat jedes Element folgende Eigenschaft: Es hat eindeutig eine Differenz zum nächsten Vielfachen der Primzahlen 2, 3, 5 und 7. Ich möchte dies an zwei Beispielen darlegen:


Beispiel 1: Für das Element 83 liegen die nächsten Vielfachen von 2, 3, 5 und 7. und 7 bei 84, 84, 85 und 84. Die Differenzen zu 83 sind also 1, 1, 2 und 1. Diese entsprechen in Abbildung 8 den Startpositionen 2, 2, 3,und 2. Dies ist die siebte Zeile. Deshalb ist dort unter fw (foward) die 83 eingetragen.


Beispiel 2: Für Element 43 liegen die nächsten Vielfachen von 2, 3, 5 und 7 bei 44, 45, 45 und 49. Die Differenzen zu 43 sind also 1, 2, 2 und 6, d. h. sie entsprechen den Startpositionen 2, 3, 3 und 7. Dies ist die 36. Zeile. Deshalb ist unter fw die 43 eingetragen.


Auf diese Weise lassen sich für alle Elemente von S7# die Einträge in Spalte fw (=forward) finden. Ebenso sind in S7# die Differenzen zu den nächst niedrigen Vielfachen vom P7 = {2, 3, 5, 7} eindeutig. Sie sind in der Spalte bw (=backward) eingetragen. Wegen der Symmetrie in S7# gilt auch bw = 7# - fw. Da die Zuordnung einer Zeile von Abbildung 10 zu einem Element von S7# eindeutig ist, können wir auch umgekehrt den Schluß ziehen: Jedem Element bw aus S7# kann eindeutig eine Zeile der Tabelle 10 zugeordnet werden. In Abbildung 10 gibt es im Intervall in jeder Zeile mindestens eine Primzahl. Die der Zeile zugeordnete Zahl bw trifft auf ein Element sj aus S7# , so dass gilt:


pk + sj = bw + 1


An einem Beispiel vergleichen wir die Ergebnisse von Abbildung 10 mit der Abbildung 9. Eine der eingezeichneten Diagonalen beginnt bei 97. Ein Vergleich mit den Ergebnissen der Tabelle 10 , Zeile 12 (bw = 97) zeigt: Die erste Null im Intervall 2 bis 22 ist auf Position 9 (keine Primzahl). Sie entspricht dem Durchgang der Diagonalen bei 89. Die nächste Null auf Position 15 (keine Primzahl) entspricht dem Durchgang der Diagonalen bei 83. Die nächste Null auf Position 19 (Primzahl) entspricht dem Auftreffen der Diagonalen auf 79.


Ausgehend von der Untermenge P7 {2,3,5,7} sind im entsprechenden Stempel in der primen Restklasse sämtliche Zahlen Primzahlen, die kleiner sind als 121, dem Quadrat der nächsten Primzahl. Entsprechendes gilt auch für die Abbildung 10. Hier sind ausgehend von den gleichen Primteilern nur die Werte von Interesse, die gröÿer als 49 sind. Zusammenfassend gilt damit, dass im Füll-Bereich 2, . . . pi+1 mindestens eine Primzahl liegt nur für die Primzahlen zwischen 49 und 121 anzuwenden ist.


Abbildung 10 ist ein Beispiel für die Primzahlen P7 {2,3,5,7} des Stempels S7#. Die Konstruktion einer solchen Tabelle ist auch jeden höheren Stempel durchführbar. Gemäß Satz 4 ist sj dann eine Primzahl, wenn sj < s22 ist. Durch geeignete Wahl (s. Anmerkung) eines höheren Stempels können wir erreichen, dass sj in (1) eine Primzahl ist.


Anmerkung: Wenn wir beispielsweise eine etwas grössere Primzahl betrachten, etwa pi = 16000057, so ist diese im Stempel S23# enthalten, weil 23# = 22309870 größ;er als pii ist. Die nächste Primzahl von 23 ist pk = 29. Dies bedeutet jedoch nicht, dass die nächste gerade Zahl, also die Zahl 16 000 058 die Summe von 2 Primzahlen muss, deren eine kleiner ist als 58 (= 2pk). Erst wenn wir einen Stempel S3989# benutzen, sind alle Zahlen im Stempel, die kleiner sind als 16 000 057, Primzahlen. Denn dann ist das zweite Element des Stempels s2 = 4001 und alle Stempel-Elemente < 40012 = 16008001 sind Primzahlen. Dann muss es eine Lösung für die Goldbachsche Vermutung geben, bei der eine der beiden Primzahlen kleiner ist als 8002.

Wir haben nun gesehen, dass ein Element aus S7# einer Variation der Basis-Primzahlen pi = 2, 3, 5, 7; pi, (i = 1, . . . n); n = 4 entspricht unter der Bedingung, dass eine Primzahl fixiert ist. Da im Bereich 1 bis 22 (= 2pi+1) mindestens noch eine Primzahl liegt, wenn die andere fixiert ist, folgt daraus, dass auch für das entsprechende Element, das im bw eingetragen ist, eine Lösung der Goldbachschen Vermutung existiert und zwar im Bereich 2pi+1, dem Füll-Bereich. Dies ist auch der Grund für die Gültigkeit des Bertrandschen Postulats.


Es kann noch weitere Lösungen des Goldbach-Problems, bei welchen die kleinere der beiden Primzahlen als größer als 2pi+1 ist. Es gibt aber immer zumindest eine L¨seng bei der die kleinere der beiden Primzahlen < 2pi+1 ist. Für größ Zahlen läÿt sich eine entsprechende Tabelle wie in Tabelle 10 konstruieren und die Werte fw und bw in derselben Weise bestimmen. Ein Element sj des Stempels und die im Intervall 2pi+1 vorhandene Primzahl bilden dann die gesuchte Summe, wenn im Stempel nur Zahlen < p2i+1 gewählt werden.


Durch die Fixierung auf die 1 in Abbildung 10 wird sichtbar (ähnlich wie in Satz 7): Wir haben hier eine multiplikative Abbildung der Primzahlen bis 7 auf den Stempel S7#. Die Abbildung der 1 wird durch Konstruktion ausdrücklich ausgeschlossen (außer in der letzten Zeile), d. h. die Produkte 1*3, 2*3, 3*3, usw., sowie 1*5, 2*5, 3*5 und 1*7, 2*7, 3*7 sind ausgeschlossen.


Daraus folgt, dass in jeder der 48 Kombinationen nicht nur Produkte der Zahlen 3, 5 und 7 auftreten können, sondern mindestens eine Zahl ist kein solches Produkt, also eine Primzahl.


Durch geeignete Wahl des Stempels kann erreicht werden, dass sj < s22 und damit eine Primzahl ist. Für gerade Zahlen 2n , für die 2n -1 eine Primzahl ist, ist damit die Behauptung bewiesen.


2. Fall: Die Zahl 2n-1 ist keine Primzahl. Wir betrachten wieder einen Stempel Spn# und in ihm die Primzahlen < pn+12 =s2. Sei pj eine solche Primzahl. Im Fall 1 wurde gezeigt, dass pj+1 die Summe aus 2 Primzahlen ist. Durch Addition von pj und den Primzahlen < 2pn+1 ergeben sich die geraden Zahlen bis zur nächsten Primzahl. Im Füll-Bereich [1, . . . , 2pn+1] sind jedoch nicht alle ungeraden Zahlen Primzahlen, sondern es kommen auch Produkte der Basis-Primzahlen vor. Es sind dies die Zahlen 9, 15, 21, . . . . So wie sich eine Fixierung auf die 1 vornehmen lässt, können wir auch die Fixierung auf jede andere ungerade Zahl im Bereich 2pi+1 vornehmen und mindestens eine weitere Zahl in diesem Bereich verbleibt dann als Primzahl. Die Fixierung auf die Primzahlen 3, 5, 7 usw. erübrigt sich, da diese Zahlen zusammen mit pj die Goldbachsche Vermutung erfüllen. Wenn wir die Fixierung auf eine der Zahlen 9, 15, ... durchführen, erhalten wir eine Primzahl < 2pn+1, welche zusammen mit einer Primzahl < pj die Goldbachsche Vermutung erfüllen. Damit ist die Goldbachsche Vermutung bewiesen.


Der Beweis für den zweiten Teil kann vereinfacht werden: Die vorausgegangenen Ergebnisse haben gezeigt, dass es sich bei der Lösung der Goldbach-Vermutung um die Reste rj einer Primzahl pj zu den Basis-Primzahlen p1, p2, p3, . . . ,pk handelt. Die Reste der Zahl pj - 2 bezüglich der Basis-Primzahlen sind die Zahlen rj - 2 oder pj - rj - 2, falls rj < 2 . Für pj - 2 könnte man daher wieder eine Fixierung vornehmen. Vorausgesetzt, es handelt sich bei pj - 2 um keine Primzahl, muss man die Diagonale in Abbildung 9, die bei pj beginnt, um 2 anheben. Dann beginnt die Diagonale für pj - 2 bei -1 mit der gleichen Sequenz von Basis-Primzahlen und Nullen wie sie für pj berechnet wurde. Daraus ergibt sich, dass das Intervall [1, . . . ,2pn+1] für pj - 2 zum Intervall [-1, . . . ,2pn+1 - 2] wird. Dieses Subtrahieren von 2 erfolgt solange bis die vorhergehende Primzahl pj-1 erreicht ist, d.h. die erste Null in der Sequenz erreicht wird. Dann beginnt wieder das im ersten Teil des Beweises beschriebene Vorgehen. Dies wird in Tabelle 11 für die Zahlen 98, 96, 94 und 92 dargestellt.


Goldbach-97

Abbildung 11: Berechnung der Goldbach-Zahlen für 98 - 92

Ich möchte diese Fixierung an einem Beispiel demonstrieren. Wir betrachten die Zahl 147. Sie hat die Primfaktorenzerlegung 3 * 7 * 7 . Die davor liegende Primzahl ist 139. Wenn wir durch 147 eine Diagonale mit 45° ziehen (Abb. 9), schneidet sie die 139 bei 9. Mit 147 befinden wir uns in einem Bereich, in dem alle Primzahlen durch die Basis-Primzahlen 2, 3, 5, 7 und 11 erzeugt wurden. Wir werden also diese 5 Basis-Primzahlen im Intervall [1, 26] so variieren, dass sie nicht auf die Zahl 9 treffen: Die Zahl 2 müssen wir immer auf der 2 starten lassen. Die Zahl 3 lassen wir auf 1 oder 2 starten, aber nicht auf 3, da sie ja dann auf die 9 treffen würde. Die Zahl 5 können wir auf 1, 2, 3 und 5 starten lassen. Entsprechend die Zahl 7 auf 1, 3, 4, 5, 6 und 7 und die Zahl 11 auf 1, 2, 3, . . . ,8, 10 und 11.


Prim-U147D Scroll
Abbildung 12: Fixierung der 5 Basis-Primzahlen auf 9 für die Zahl 147

Insgesamt ergeben sich 480 Möglichkeiten. Ich möchte hier nicht alle diese Möglichkeiten aufisten, sondern nur diejenige, die uns interessiert. Sie ist in Abb. 12 gezeigt. Die Differenzen von 147 zu den vorangehenden Vielfachen von 2, 3, 5, 7 und 11 sind 1, 0, 2, 0 und 4. Dies entspricht den in Abbildung 10 gewählten Startpositionen. Wie wir sehen, sind die Primzahlen 11 und 17 mit Nullen belegt. Dies entspricht den Primzahlen 137 und 131, wenn wir die bei 147 beginnende Diagonale weiter verfolgen.


Es ist nicht notwendig, die Tabelle aller Möglichkeiten aufzustellen, um die gesuchte Primzahl für die Goldbachsche Vermutung zu fnden. Für den Algorithmus genügt es vielmehr, die Primfaktorenzerlegung von 2n - 1 und die Differenzen von 2n - 1 zu den vorangehenden Vielfachen der Basis-Primzahlen, die nicht in der Primfaktorenzerlegung von 2n - 1 enthalten sind, d.h. die Reste von 2n - 1 bezüglich der Basis-Primzahlen zu ermitteln, um mit ihnen die Startpunkte für die Basis-Primzahlen festzulegen. Damit erhalten wir einen Bereich wie in Abbildung 10. Die Primzahlen pa , die dort eine Null aufweisen, sind zusammen mit 2n-pa Lösungen für die Goldbachsche Vermutung von 2n.


Die Goldbachschen Zahlen müssen gewissermaÿen 2 Siebe hintereinander passieren. Das erste Sieb ist das Sieb des Eratosthenes, bei dem alle Primzahlen bei Null beginnen. Das zweite Sieb ist ähnlich aufgebaut wie das erste, jedoch beginnen die Basis-Primzahlen ihren Lauf nicht alle bei Null, sondern an anderen Startpunkten, die mit Hilfe der Reste von 2n - 1 berechnet werden können.


Sierpinksi erwähnt in seinem Buch über die Theorie der Zahlen [Waclaw Sierpinski: Grundlegende Theorie der Zahlen, Wasawa 1964] in dem Abschnitt über Goldbachs Vermutung das Problem der Differenzen von Primzahlen. Anhand der obigen Ausführungen kann mit Hilfe der Zahlen fw und der Diagonalen in Richtung 315° (in Abb. 9 nicht eingezeichnet) auch der Satz bewiesen werden, dass jede gerade Zahl die Differenz zweier Primzahlen ist.


5. Ein Algorithmus zur Primzahlen-Berechnung

Im vorigen Abschnitt sind die Elemente von S7# aufgeführt und in der Abbildung 6 sind die Reste resi dargestellt. Mit der Abbildung 12, der Tabelle mit der Fixierung einer Primzahl auf die Position 1 sind die Startpositionen (nennen wir sie posi der 4 Primteiler 2, 3, 5 und 7 dargestellt, welche pro Zeile jeweils zu einer Fixierung auf die 1 führen. Die Anzahl dieser Primteiler, d.h. der Basis-Primzahlen. ist momentan n=4. Ein Vergleich der beiden Tabellen zeigt, dass sich die Werte resi und posi jeweils um 1 unterscheiden. Es ist posi = resi + 1. Die Nullen eines Füll-Bereichs, d. h. einer Zeile in Abbildung 12 zeigen an, wo sich - ausgehend von einem Element sk von S7# eine vorausgehendes Element von S7# befindet. Für die Elemente sk, welche kleiner als 121, dem Quadrat der nächsten Primzahl sind, bedeutet dies, dass wir in S7# dadurch ein Element fnden, welches eine Primzahl ist. Dies gilt zumindest bis 49, dem Quadrat der Primzahl 7.


Umgekehrt kann man auf Grund der Symmetrie der Stempel⁄primen Restklassen auch die auf das Element sk folgenden Primzahlen finden. Dazu müssen die Startpositionen für eine Zeile in Tabelle 10 anders gewählt werden und zwar gerade komplementär zu den gerade beschriebenen Werten. Wir müssen daher als Startpositionen die Werte posi = pi .. resi + 1 wählen und den im vorigen Kapitel geschilderten Algorithmus anwenden.


Ein Feld-Element des Füll-Bereichs kann mehrfach durch Primteiler belegt werden. Im vorigen Abschnitt wurde nur die einfache Belegung zur Verdeutlichung des Algorithmus zugelassen. Zur Beschleunigung des Verfahrens kann man die Prüfung, ob ein Feld schon belegt ist, weglassen und sich außerdem nur auf Feld-Elemente mit ungeraden Index beschränken.


Die Anzahl der Feld-Elemente des Füll-Bereichs ist hier zunächst 2pi+1. Bildet dieser Füll-Bereich einen Bereich ab, in dem das Quadrat p2n+1 liegt, so ist das entsprechende Element im Füll-Bereich eine Null und muss deshalb bei der Ausgabe der Primzahlen ausgesondert werden.


Die letzte Null, welche wir im Füll-Bereich 1, . . . , 2pi+1 finden, kennzeichnet die Primzahl pneu, wenn sie nicht dem Primzahl-Quadrat p2n+1 entspricht. Mit dieser neuen Primzahl können wir im nächsten Bearbeitungsschritt fortfahren. Die neuen Reste resi erhalten wir, wenn wir aus dem Füllbereich die Differenz der neuen Primzahl mit dem letzen Eintrag von pi in dem Füllbereich bilden.


Ist p2n+1 überschritten (hier =121), gehen wir zu S11# über, d.h. die Primzahl 11 wird in die "Basis-Primzahlen" aufgenommen. Damit ist deren Anzahl n=5. Der Rest res5 für 11 ist bei 121 = Null. Die Anzahl der Feld-Elemente des Füll-Bereichs wird 26. Der Rest res5 für 11 bei 121 ist Null.


Die ist jedoch die einzige Zahl, auf die bei der Aussonderung geachtet werden muss. Insgesamt kommen wir bei dieser Berechnung der Primzahlen mit sehr wenigen Divisionen aus. Wir müssen für einen 2pi+1-Bereich lediglich das Feld mit den Basis-Primzahlen pi belegen und die Primzahlen purzeln heraus wie die Kugeln bei einem Kaugummi-Automaten. Nur auf eine Zahl müssen wir achten, nämlich auf p2n+1. Sie ist keine Primzahl und sie erhöht, wenn sie überschritten wird, die Anzahl der Basis-Primzahlen um 1 und die Gröÿe des Füll-Bereichs.


Ich möchte das Vorgehen an einem Beispiel demonstrieren: Ich beginne mit der Primzahl 97. Die Primzahlen < √97 sind 2, 3, 5 und 7. Sie sind in den Abbildungen 10 und 11 die Basis-Primzahlen. Die nächste Primzahl ist 11. Die Anzahl der Elemente des Füll-Bereichs ist 2 * 11 = 22. Die Reste von 97 bezüglich 2, 3, 5 und 7 sind 1, 1, 2 und 6. Wir berechnen die Komplemente. Sie sind 1, 2, 3 und 7. Das Ganze ist noch einmal für den Startwert 97 in Tabelle 13 zusammengefasst.


Goldbach-Bild scrollen

Abbildung 13: Startwert 97. Primzahlen und Modulo-Werte

Die Werte "Komplement" + 1 sind die Startpositionen für den im vorigen Kapitel beschriebenen Algorithmus. Tabelle 13 zeigt das Ergebnis.


Hierbei ist außer dem ersten Wert der 5., 7., 11., 13. und 17. Wert eine Null. Die bedeutet: 101, 103, 107, 109 und 113 sind Primzahlen. Die letzte Primzahl dieser Reihe ist 113. Sie oder das nächste Prim-Quadrat ist der Startwert für den nächsten Durchgang. Durch Modulo-Berechnung oder Differenzbildung bei der letzten Primzahl des Füll-Bereichs erhält man die Reste und ihre Komplemente. Diese sind nun die neuen Startpositionen, usw.


Goldbach-97 scrollen

Abbildung 14: Startwert 97. Primzahlen und Füllbereich

Mit 113 als Startwert ergeben sich die Primzahlen 127 und 131. Auch der 9. Wert, welcher der Zahl 121 entspricht, enthält eine Null. Dies war zu erwarten und dieser Wert wird als Primzahl ausgesondert. Der nächste solche Wert wäre 143, das Produkt 11 * 13. Jedoch liegt dieser Wert außerhalb des Füll-Bereichs. Mit 127 und 131 überschreiten sogar 2 Primzahlen das Primzahl-Quadrat 121 und die nächste Berechnung mit dem Startwert 131 enthält 5 Reste für die Basis-Zahlen 2, 3, 5, 7 und 11 und die Anzahl der Feld-Elemente beträgt 26. Der Rest der Zahl 131 bezüglich der Zahl 11 ist 10. Dies berechnet man als Differenz zum Primzahl-Quadrat 121

Im Algorithmus sind 20 Schritte von 97 bis 811 erforderlich und man erhält 116 Primzahlen, 40 Schritte sind von 97 bis 2221 nötig. Das sind 311 Primzahlen.

Man kann den Algorithmus noch um einiges verbessern: Der Füll-Bereich kann vergröÿert werden, wenn die Differenz pn+1 - pn größer als 2pn ist. Im Algorithmus kann der Füll-Bereich so gestaltet werden, dass in einem Berechnungsschritt alle Primzahlen zwischen p2n und p2n+1 gefunden werden.

6. Ein Algorithmus zu Zerlegung einer Zahl in Primfaktoren

Im vorigen Abschnitt wird gezeigt, wie aus einem Füllbereich die Primzahlen entnommen werden können. An den entsprechenden Positionen sind Nullen eingetragen. Entsprechend haben die anderen Positionen des Füllbereichs positive Einträge von Primzahlen. Diese Einträge sind nun Primfaktoren der entspechenden Zahl. Wir müssen also den Füllbereich so wählen, dass die Zahl z, deren Primfaktoren wir ermitteln wollen, zwischen zwei aufeinanderfolgenden Primzahl-Quadraten liegt. Aus dem vorigen Abschnitt ist ersichtlich, dass nicht nur die Primzahlen eine Null enthalten, sondern auch die Quadrate der Primzahlen. Wir bewegen uns hier beispielsweise in einer primen Restklassengruppe oder anders gesagt im Stempel S7#. Dort sind p2n n = 121 und p2n+1 = 169 ebenfalls Elemente. Wir müssen also p2n und p2n+1 so wählen, dass p2n < z < p2n+1 ist. Den korrespondierenden Füllbereich lassen wir dann bei p2n beginnen und bei p2n+1 oder frühestens bei z enden - der eigentliche Füllbereich beginnt, wie oben gezeigt, immer bei 1. Nach Ausfüllen des Füllbereichs sind die Einträge bei der Position im Füllbereich, welche z entspricht - Primfaktoren von z.

Man muss also von Primzahl-Quadrat zum nächsten Primzahl-Quadrat fortfahren, bis die oben genannte Bedingung erfüllt ist. Am Ende jedes Füll-Bereichs, d.h. dem Intervall [ p2n, . . . ,p2n+1 ], werden die Reste bzw. Komplemente für den nächsten Berechnungsschritt bestimmt. Die Anzahl der Basis-Primzahlen wird um eine Primzahl erhöht.

Natürlich erhalten wir nicht alle Primfaktoren, denn Mehrfacheinträge eines Primfaktors können nicht Einträge bei der Position sein, welche z entspricht. Auch Primfaktoren gröÿer pn sind nicht eingetragen.

Es wäre ein großer Rechenaufwand, jedesmal alle Primzahlen, beginnend bei der ersten, zu berechnen. Deshalb empfiehlt es sich, in gewissen Abständen die Komplemente zu speichern. Beispielsweise für die j-te Primzahl p2j alle Komplemente zu speichern, welche bei p2j zum Weiterrechnen notwendig sind.

Stellt man sich die Primzahlen in waagrechten Linien geordnet vor: Auf der ersten Linie ist die Primzahl 2 und wird bei 4, 6, 8, 10, . . . wiederholt. Die Primzahl 3 liegt in die nächsten Zeile. Sie wird bei 6, 9, 12, 15, . . wiederholt. Entsprechend wird mit den weiteren Primzahlen verfahren: Auf der i-ten Linie liegt die Zahl pi und wird bei 2pi, 3pi, . . wiederholt. Jede Primzahl pi nimmt ab ihrem Quadrat pi2 Einfluss auf die Bildung der Primzahlen. Mit der 4. Primzahl beispielsweise werden die Zahlen 49, 77 und 91 aus der Menge der Primzahlen eliminiert.

Der vorgestellte Algorithmus macht einen senkrechten Schnitt durch diese Linien. Dieser Schnitt reicht jeweils bis zur i-ten Linie. So wird für die Zahlen ≥ 49 bis zu den Zahlen < 121 der Schnitt bis zur 4. Linie durchgeführt. Trift dieser Schnitt keinen Eintrag, so ist die Zahl prim. Trifft er jedoch eine oder mehrere Zahlen, so sind diese Primteiler. Bei jedem Schnitt kommt jeder Primteiler jedoch nur einmal vor.

Im Algorithmus lassen sich mehrere Korrekturen anbringen, um ihn schneller zu machen: Verzichtet man auf die Primfaktoren der geraden Zahlen, kann man im Füll-Bereich die geraden Zahlen weglassen. Ähnlich verhält es sich bei Zahlen die durch 3, 5, 7 und einige andere teilbar sind. Ich verweise hierzu auf die Teilbarkeitskriterien in [Zahlentheorie, Prof. Dr. Harald Schmitt, ISBN 3-411-14841-1, p. 121 ff.].

Da bei Füllen des Bereichs jede zweite Zahl gerade ist, kann man den Füll-Bereich schneller auffüllen, in dem man an diesen Stellen auf das Auffüllen verzichtet. Hat man die Primzahlen und die Komplemente bei p2i berechnet und gespeichert,n ist es zuweilen sinnvoller, den Berechnungs-Prozess rückwärts zu durchlaufen, um z.B. Primfaktoren für eine Zahl zu finden, die zwischen p2i-1 und p2iliegt.

Es sind noch weitere Maÿnahmen möglich, um den Algorithmus zu beschleunigen. Wird der Füll-Bereich zu groß, um ihn im Computer-Programm als Ganzes zu bearbeiten, läÿt er sich unterteilen. Ist man an den Primzahlen > pi+1 nicht interessiert, kann man den Prozeß solange fortsetzen, bis man die Primzahlen bis pi+1 gefunden hat. Man hat dann ein p2 erreicht, welches größer als pi+1 ist und die Reste oder Komplemente sind dann dort bekannt. Nun kann man die Reste von p2i bezüglich der Basis-Primzahlen mit anderen Methoden berechnen. Daraufhin berechnet man die Primfaktoren im Füllbereich [ p2i, . . . , p2i+1] in der oben beschriebenen Weise.

7. Vergleich mit der Zeta-Funktion

Vergleicht man diese Ergebnisse mit der Riemannschen Zeta-Funktion, so stellt man folgendes fest: Die Berechnung der Primzahlen erfolgt zwischen p2i und p2i+1, indem die vorausgegangenen Ergebnisse - die Primzahlen bis pi und die Reste bzw. Komplemente zu diesen Primzahlen an der Stelle p2i benutzt werden, um die Primzahlen bis p2i+1 zu ermitteln. Mit dem im vorigen Kapitel beschriebenen Algorithmus fällt dann auf p2i+1 keine Zahl, d.h. dies ist zunächst eine Primzahl im Sinne des Algorithmus. Da man aber pi+1 bereits kennt, kann man dort diesen Wert eintragen. Bei der Zeta-Funktion, welche mit den reziproken Werten der Primzahlen arbeitet, haben die Nullstellen den Realteil 1⁄2. Dies entspricht bei dem hier geschilderten Algorithmus einem Stop bei p2i+1. Dort kommt zum ersten Mal die Primzahl pi+1 ins Spiel. Zwischen den Quadraten von aufeinanderfolgenden Primzahlen, ja sogar zwischen Quadraten von aufeinanderfolgenden natürlichen Zahlen liegen Primzahlen, wie mit Satz 2 gezeigt wird. Die Berechnung der Primzahlen stoppt jedesmal nur bei p2i+1, wie bei der Zeta-Funktion jedesmal mit einer Nullstelle mit dem Realteil 1⁄2.

8. Schluß

Ich möchte hier nochmals auf die eingangs erwähnte Ulam-Spirale hinweisen. In der Diagonale, beginnend bei 1 nach rechts oben liegen die Quadratzahlen der geraden Zahlen. In der Diagonale beginnend bei 4 nach links unten liegen die Quadrate der ungeraden Zahlen. Aus Satz 8 folgt, dass zumindest bis zum Erreichen der nächsten geraden und ungeraden Quadratzahl, also bei jeder halben Umdrehung der Spirale bis zu einer dieser Diagonalen mindestens zwei Primzahlen auftreten. Eine Linie senkrecht zu dieser Diagonalen durch die Zahlen 6, 20, 42, . . . , d.h. n2 - n, (n ungerade), bzw. auf der anderen Seite durch die Zahlen 12, 30, 56, . . . , d.h. n2 - n (n gerade) kennzeichnet die Intervallgrenzen. Zwischen diesen Intervallgrenzen und den Quadraten liegt mindestens jeweils eine Primzahl.

An diesen Punkten (eine Zahl später) ändert die Ulam-Spirale ihre Richtung um 90° bzw. um - 90° je nachdem, ob die Spirale im oder gegen den Uhrzeigersinn gezeichnet wird. Es spielt dabei keine Rolle, ob die Spirale mit der 2 rechts, links, oberhalb oder unterhalb von der 1 begonnen wird. Beginnt die Ulam-Spirale mit der Null in der Mitte, so ändert sie genau an den Eckpunkten ihre Richtung um 90°.

Haben Sie Fehler darin entdeckt oder stimmen Sie meinen Beweisen zu, teilen Sie mir dies per Email mit.