7. Arithmetische Progressionen in den Primzahlen

Im letzten Essay haben wir die Frage verfolgt, ob arithmetische Progressionen viele Primzahlen enthalten. Umgekehrt fragen wir nun, ob sich in der Folge der Primzahlen viele arithmetische Progressionen finden. Zunächst kann eine unendliche Progression

a, a + m, a + 2m, a + 3m, …

nicht ausschließlich aus Primzahlen bestehen. Denn es gibt, wie wir gesehen haben, beliebig lange Intervalle zusammengesetzter Zahlen. Eine unendliche Progression der Schrittweite m trifft jedes hinter ihrem Startpunkt liegende Intervall, dessen Länge größergleich m ist. Damit enthält jede unendliche Progression unendlich viele zusammengesetzte Zahlen. Wir müssen uns also auf endliche arithmetische Progressionen der Form

(+) a, a + m, a + 2m, …, a + (k − 1)m

mit einer endlichen Länge k beschränken. Ist jedes Element einer solchen Progression eine Primzahl, so nennen wir die Progression eine Primzahl-Progression. Eine Primzahl-Progression der Form (+) existiert genau dann, wenn das Muster (m, …, m) mit k − 1 konstanten Einträgen m in den Primzahlen vorkommt. Wir fragen also nach konstanten Mustern in den Primzahlen (mit Überspringen). Mit Hilfe eines Computers können wir viele Beispiele für solche Progressionen finden:

Beispiele für Primzahl-Progressionen

2, 3	Länge 2, Schrittweite 1
3, 5, 7	Länge 3, Schrittweite 2
5, 11, 17, 23, 29	Länge 5, Schrittweite 6
7, 37, 67, 97, 127, 157	Länge 6, Schrittweite 30
7, 157, 307, 457, 607, 757, 907	Länge 7, Schrittweite 150
199, 199 + 210, …, 199 + 9 · 210	Länge 10, Schrittweite 210
4943, 4943 + 60060, …, 4943 + 12 · 60060	Länge 13, Schrittweite 60060

Die Tabelle vermittelt den Eindruck:

Lange Progressionen haben eine sehr große Schrittweite.

Wir wollen diese Aussage nun präzisieren und beweisen. Wie bei den Primzahlmustern liefert die Division mit Rest eine Schranke für die Länge einer Primzahl-Progression. Entscheidend verwenden wir:

Satz (Reste einer Progression bei Division durch eine Primzahl)

Seien a ≥ 0, m ≥ 1, und sei p eine Primzahl, die kein Teiler von m ist. Dann besitzen die Zahlen a, a + m, a + 2m, …, a + (p − 1)m paarweise verschiedene Reste bei der Division durch p.

Beweis

Für i = 0, …, p − 1 sei a + i m = q_i p + r_i die Division von a + i m durch p mit Rest. Für alle i, j mit 0 ≤ i < j < p ist dann

(j − i)m = (q_j − q_i) p + r_j − r_i.

Folglich ist r_j ≠ r_i, da andernfalls p ein Teiler von (j − i) m und damit von m wäre.

Da die Reste r_i Elemente der p-elementigen Menge { 0, …, p − 1 } sind, besagt der Satz, dass die Reste r₀, …, r_p − 1 eine Umordnung der Zahlen 0, …, p − 1 darstellen. Es folgt:

Satz (Schranke für die Länge einer Primzahl-Progression)

Sei a, a + m, a + 2m, …, a + (k − 1)m eine Primzahl-Progression der Länge k. Weiter sei p eine Primzahl, die kein Teiler von m ist und die in der Progression nicht vorkommt. Dann gilt k < p.

Beweis

Nach dem Satz ist { 0, …, p − 1 } die Menge der Reste der Division der Zahlen a, a + m, … , a + (p − 1) m durch p. Folglich ist eine dieser Zahlen durch p teilbar. Da p in der Primzahl-Progression nicht vorkommt, ist notwendig p − 1 > k − 1, sodass k < p.

Ist also in der Situation des Satzes p ≤ k eine Primzahl, die in der Progression nicht vorkommt, so ist die Schrittweite m ein Vielfaches von p. Allgemeiner erhalten wir:

Korollar (Teilbarkeit der Schrittweite einer Primzahl-Progression)

Sei a, a + m, a + 2m, …, a + (k − 1)m eine Primzahl-Progression der Länge k. Weiter seien p₁, …, p_r ≤ k Primzahlen, die in der Progression nicht vorkommen. Dann ist das Produkt p₁ … p_r ein Teiler von m.

Der Leser vergleiche dies mit den Schrittweiten der obigen Tabelle. Es gilt:

6 = 2 · 3, 30 = 2 · 3 · 5, 210 = 2 · 3 · 5 · 7, 60060 = 2 · 3 · 5 · 7 · 11 · 13.

Diese Schrittweiten sind also die Produkte der ersten Primzahlen.

Unser Ergebnisse lassen sich auch in der Sprache der Primzahlmuster formulieren: Wir betrachten ein konstantes Muster (m, …, m) der Länge k − 1. Ist dieses Muster zulässig, so gilt für jede Primzahl p, dass die Reste von m, 2m, …, (k − 1)m bei Division durch p ein Element in { 1, …, p − 1 } auslassen. Dies ist aufgrund des Satzes über die Reste einer Progression nur möglich, wenn für jede Primzahl gilt: p ist ein Teiler von m oder k < p. Anders formuliert: Alle Primzahlen p ≤ k sind Teiler von m.

Wir wissen also, dass lange Primzahl-Progressionen notwendig sehr große Schrittweiten aufweisen müssen. Ein drastisches limitierendes Ergebnis wäre, dass es ein k gibt derart, dass es gar keine Primzahl-Progression der Länge k existiert. Dies ist jedoch nicht der Fall. Aufbauend auf Ergebnissen von Endre Szemerédi aus dem Jahr 1975 über arithmetische Progressionen in hinreichend umfangreichen Mengen natürlicher Zahlen zeigten Ben Green und Terence Tao im Jahr 2004 (vgl. [ Green/Tao 2008 ]):

Satz (Satz von Green-Tao)

Es gibt beliebig lange Primzahl-Progressionen: Für alle k ≥ 1 gibt es natürliche Zahlen a, m ≥ 1, sodass die Progression

a, a + m, a + 2m, …, a + (k − 1)m

ausschließlich aus Primzahlen besteht.