6. Primzahlen in arithmetischen Progressionen
Die Zahl 2 ist die einzige gerade Primzahl. Alle anderen Primzahlen sind ungerade, d. h. sie besitzen den Rest 1 bei Division durch 2. Analog gilt: Die Primzahl 3 ist die einzige Primzahl, die durch 3 teilbar ist. Alle anderen Primzahlen besitzen den Rest 1 oder 2 bei Division durch 3. Die Reste der ersten Primzahlen
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
bei Division durch 3 lauten
2, 0, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 1, 2
Zur Berechnung erinnere sich der Leser daran, dass der Rest einer natürlichen Zahl in Dezimaldarstellung bei Division durch 3 mit dem Rest der Quersumme der Zahl bei Division durch 3 übereinstimmt.
Wir fragen:
Taucht die 1 unendlich oft als Rest bei der Division der Primzahlen durch 3 auf?
Taucht die 2 unendlich oft als Rest bei der Division der Primzahlen durch 3 auf?
Gleichwertig können wir die beiden folgenden Fragen stellen:
Enthält die Folge 1, 4, 7, 10, 13, 16, 19, … unendlich viele Primzahlen?
Enthält die Folge 2, 5, 8, 11, 14, 17, 20, … unendlich viele Primzahlen?
Wir definieren:
Definition (arithmetische Progression (als Folge in den natürlichen Zahlen))
Eine Folge natürlicher Zahlen der Form
a, a + m, a + 2m, a + 3m, …
heißt eine (unendliche) arithmetische Progression mit Startpunkt a und Schrittweite m.
Die Progressionen 1, 4, 7, … und 2, 5, 8, … besitzen die Schrittweite 3. Eine der beiden Progressionen muss unendlich viele Primzahlen enthalten, da die Primzahlen unendlich sind und in der Progression 3, 6, 9, … nur eine Primzahl enthalten ist. Wie können wir herausfinden, ob beide Progressionen unendlich viele Primzahlen enthalten? Wieder ist eine Variante des Beweises von Euklid geeignet, einen Teil der Frage positiv zu beantworten:
Satz (Unendlichkeit der Primzahlen mit Rest 2 bei Division durch 3)
Die Progression 2, 5, 8, 11, 14, 17, 20, … enthält unendlich viele Primzahlen.
Wir zeigen vorab:
Satz (Erhalt des Restes 1 bei Produktbildung)
Sei m ≥ 1, und seien b1, …, bk natürliche Zahlen mit Rest 1 bei Division durch m. Dann besitzt auch das Produkt b1 … bk den Rest 1 bei Division durch m.
Beweis
Nach Voraussetzung gibt es n1, …, nk mit b1 = n1m + 1, …, bk = nkm + 1. Ausmultiplizieren zeigt, dass
b1 … bk = (n1m + 1) … (nkm + 1) = nm + 1,
für eine gewisse natürliche Zahl n (denn wir können die Zahl m aus allen Summanden bis auf den letzten ausklammern). Dies zeigt, dass b1…bk den Rest 1 bei Division durch m besitzt.
Wir betrachten nun wieder speziell m = 3. Hat eine Zahl a den Rest 2 bei Division durch 3, so ist a nicht durch 3 teilbar, sodass alle Primteiler von a den Rest 1 oder 2 bei Division durch 3 haben. Nach dem gerade gezeigten Erhaltungssatz können nicht alle Primteiler von a den Rest 1 haben. Damit gilt:
Korollar
Besitzt eine Zahl a den Rest 2 bei Division durch 3, so hat a mindestens einen Primteiler, der den Rest 2 bei Division durch 3 besitzt.
Nun können wir den Satz durch eine Variante von „Produkt plus 1“ beweisen. Die Variante lautet „dreifaches Produkt minus 1“:
Beweis des Satzes
Seien p1, …, pn Primzahlen, die alle den Rest 2 bei Division durch 3 besitzen. Wir zeigen, dass es eine von p1, …, pn verschiedene Primzahl p gibt, die bei Division durch 3 ebenfalls den Rest 2 besitzt. Wir setzen hierzu
a = 3 p1 … pn − 1.
Dann ist a nicht durch die Primzahlen p1, …, pn teilbar, sodass jeder Primteiler von a von p1, …, pn verschieden ist. Nach Konstruktion besitzt a den Rest 2 bei Division durch 3. Nach dem Hilfssatz hat a mindestens einen Primteiler p, der den Rest 2 bei Division durch 3 besitzt. Die Primzahl p ist wie gewünscht.
Da jede zweite Zahl der Progression 2, 5, 8, 11, 14, 17, 20, … gerade ist, erhalten wir folgende Verstärkung:
Korollar (Unendlichkeit der Primzahlen mit Rest 5 bei Division durch 6)
Die Progression 5, 11, 17, 23, 29, … enthält unendlich viele Primzahlen.
Auch die Progression 1, 4, 7, 10, 13, 16, 19, … enthält unendliche viele Primzahlen und folglich gilt dies für 1, 7, 13, 19, 25, 31, … Der Beweis ist nicht mehr so leicht zu führen (der Leser findet einen Beweis im Anhang über Kongruenzen). Unsere Methode ist aber geeignet, um zu zeigen:
Satz (Unendlichkeit der Primzahlen mit Rest 1 bei Division durch 4)
Die Progression 1, 5, 9, 13, 17, 21, … enthält unendlich viele Primzahlen.
Zum Beweis argumentieren wir wie oben, wobei wir nun die Zahl
a = 4 p1 … pn − 1
betrachten, die den Rest 3 bei Division durch 4 besitzt. Der Leser führe das Argument durch.
Unsere Sätze über Primzahlen in Progressionen sind Spezialfälle eines allgemeinen von Peter Gustav Dirichlet 1837 mit Hilfe komplexer Analysis bewiesenen Satzes:
Satz (Primzahlsatz von Dirichlet)
Seien a und m teilerfremde Zahlen. Dann enthält die arithmetische Progression
a, a + m, a + 2m, a + 3m, …
unendlich viele Primzahlen.
Beispiele
(1) | Da a = 7 und m = 10 teilerfremd sind, tauchen in der Progression 7, 17, 27, 37, 47, … unendliche viele Primzahlen auf. Es gibt also unendlich viele Primzahlen, deren letzte Ziffer in Dezimaldarstellung die 7 ist. |
(2) | Für a = 6 und m = 9 lautet die Progression 6, 15, 21, 30, 39, … Alle Zahlen sind durch 3 teilbar und größer als 3, sodass die Progression keine Primzahlen enthält. Allgemein gilt: Ist d ≥ 2 ein gemeinsamer Teiler von a und m, so ist d ein Teiler aller Zahlen der Progression a, a + m, a + 2m, … Damit kann in diesem Fall allenfalls die erste Zahl a der Progression prim sein. |
Die folgenden Abbildungen illustrieren die Ergebnisse. Wir färben die Primzahlen nach ihrem Rest bei der Division durch die betrachtete Schrittweite m. Gleiche Farbe bedeutet gleicher Rest.
Einfärbung der ersten 200 Primzahlen nach ihrem Rest bei Division durch 3
Einfärbung der ersten 200 Primzahlen nach ihrem Rest bei Division durch 7
Einfärbung der ersten 200 Primzahlen ab 106 nach ihrem Rest bei Division durch 3
Eine andere Möglichkeit, den Primzahlsatz von Dirichlet zu visualisieren, besteht darin, die natürlichen Zahlen „modulo m“ anzuordnen, d. h. nach ihrem Rest bei Division durch m zu gruppieren. Für m = 5 ergibt sich:
Anordnung der natürlichen Zahlen bis 100 modulo 5
Der Primzahlsatz von Dirichlet besagt für den Fall m = 5, dass sich in jeder Zeilen mit Ausnahme der untersten unendliche viele Primzahlen befinden. Für einen größeren Abschnitt erhalten wir folgendes Bild, wobei wir die Primzahlen der Übersichtlichkeit halber durch Punkte ersetzen:
Anordnung der natürlichen Zahlen bis 500 modulo 5
Für m = 12 erhalten wir:
Anordnung der natürlichen Zahlen bis 1200 modulo 12
Anordnung der natürlichen Zahlen bis 10000 modulo 100