Über einen Satz der Arithmetik

Italo Zignano

31. Juli 1998

1 Einführung

Es gilt der Satz:

Jede arithmetische Progression, in welcher die beiden ersten Glieder teilerfremd sind, enthält unendlich viele Primzahlen.

Dieser wurde das erste mal von Legendre in den Recherches d’analyse indeterminée ausgesprochen, und zwar auf deren letzter Seite, obwohl er schon im Laufe der Untersuchung implizit benutzt worden ist. Der Autor gibt keinen Beweis, deutet aber eine Methode an, die vielleicht zu einem solchen führen könnte. Hier ist die Meinung von Gauß [2, p. 297]:

Ill. LeGendre ... conducere possit.

Aber Gauß nimmt an, daß, um auf diesem Weg ans Ziel zu gelangen, seiner Meinung nach viele Voruntersuchungen notwendig seien. Es scheint, daß auch Legendre sich dieser Meinung angeschloßen hat, denn als er seinen Beweis von neuem aufgriff, wählte er einen andern Weg. Dieses mal gab er einen verwickelten Beweis [3]. Allerdings benutzt er dabei einen nicht hinreichend bewiesenen Hilfssatz. Dirichlet versuchte, Legendre’s Beweis zu vervollständigen, fand aber, wie er sagte, unüberwindliche Hindernisse, suchte einen andern Weg und fand ihn auch ([1]). Sein Beweis ist sehr schön, aber, wie der Autor selbst gesteht, nicht arithmetischer Natur, da er sich auf Prinzipien der Infinitesimalrechnung gründet.

In jüngerer Zeit hat Sylvester [4] einen arithmetischen Beweis des Dirichletschen Satzes gesucht und war für solche Progressionen erfolgreich, die von der Gestalt ax + 1 sind, sowie für einige weitere Spezialfälle.

2 Definitionen

Wir verwenden folgende Bezeichnungen.

1. M(a, b) = max(a, b);

2. m(a, b) = min(a, b);

3. M^{k}_{z=1} u_{z} = max{u_{1}, …, u_{k}};

4. m^{k}_{z=1} u_{z} = min{u_{1}, …, u_{k}};

5. D(a) bezeichnet einen Teiler von a;

6. D^{m+n}_{m} (a) ist ein Teiler d von a mit m ≤ d ≤ m + n;

7. M D^{m+n}_{m} (a) ist der maximale Teiler d von a mit m ≤ d ≤ m + n;

8. D(a, b) ist ein gemeinsamer Teiler von a und b;

3 Der Beweis

Proposition 1. Seien p_{1}, …, p_{s} paarweise verschiedene Primzahlen, die a nicht teilen; dann gibt es unter p_{1} ⋯ p_{s} aufeinanderfolgenden Gliedern der arithmetischen Progression

b, b + a, b + 2a, …  (1)

mindestens ein Glied, das durch keines der p_{i} teilbar ist.

Beweis. Im Falle, daß wir nur eine Primzahl haben, ist die Proposition bewiesen. Es genügt daher zu zeigen, daß sie für s Primzahlen wahr ist, falls sie es für s−1 pz en ist.

Dazu wählen wir irgendwelche p_{1} ⋯ p_{s} aufeinanderfolgende Gliedern der arithmetischen Progression, z.B.

b + (x + 1)a, b + (x + 2)a, …, b + (x + p_{1} ⋯ p_{s})a

und teilen sie wie folgt in zwei Teile;

\begin{matrix}b + (x + 1)a, & …, & b + (x + p_{1} ⋯ p_{s−1})a, \\ b + (x + p_{1} ⋯ p_{s−1} + 1)a, & …, & b + (x + p_{1} · p_{s})a, \end{matrix}

indem wie dem einen Teil die ersten p_{1} ⋯ p_{s−1} Glieder, dem zweiten die folgenden Glieder zuteilen. Nach Induktionsvoraussetzung enthält der erste Teil eine Zahl, die duch keine der Primzahlen p_{1}, …, p_{s−1} teilbar ist. Sie b + (x + h)a eine solche. Die Bedingung, daß diese Zahl zum ersten Teil gehört, kann man so schreiben:

1 ≤ h ≤ p_{1} ⋯ p_{s−1}.  (2)

Betrachten wir jetzt das Glied b + (x + h + p_{1} ⋯ p_{s−1})a. Es gehört zum zweiten Teil, da nach (2) gilt

p_{1} ⋯ p_{s−1} ≤ h + p_{1} ⋯ p_{s−1} ≤ p_{1} ⋯ p_{s}.  (3)

Weiter ist es durch keine der Primzahlen p_{1}, …, p_{s−1} teilbar, denn wäre z.B. p_{2} | (b + (x + h + p_{1} ⋯ p_{s−1})a), so würde auch p_{2} | (b + (x + h)a) gelten.

Von den beiden Zahlen

b + (x + h)a, b + (x + h + p_{1} ⋯ p_{s−1})a

ist mindestens eine nicht durch p_{s} teilbar: sonst wäre auch deren Differenz p_{1} ⋯ p_{s−1}a durch p_{s} teilbar.

Proposition 2. Wenn a, b, c keinen gemeinsamen Teiler haben, dann ist unter c aufeinanderfolgenden Gliedern der arithmetischen Progression

b, b + a, b + 2a, …

mindestens eine Zahl teilerfremd zu c.

Beweis. Wir wählen irgendwelche c aufeinanderfolgende Glieder der arithmetischen Progression, z.B. b + (x + 1)a, b + (x + 2)a, …, b + (x + c)a, und verteilen die Teiler von c auf zwei Klassen, deren eine die Primteiler enthält, welche auch a teilen, die andere den Rest. Dann stellen wir fest:

1. Die Primzahlen der ersten Klasse teilen kein Glied der Reihe. Eine solche Zahl würde nämlich a, b und c teilen.

2. Es gibt unter c aufeinanderfolgenden Gliedern der arithmetischen Progression mindestens eines, welches durch keine Primzahl der zweiten Klasse teilbar ist.

Denn wenn p_{1}, …, p_{s} diese Zahlen sind, genügt es, die Primteiler p_{1}, …, p_{s} unter den gewählten Gliedern zu untersuchen und eines zu finden (nach Proposition 1), welches durch keine der Zahlen p_{1}, …, p_{s} teilbar ist.

Beobachtung I. Kürzer kann man diese Proposition so aussprechen:

ggT (a, b, c) = 1 ⟹ m^{x+c}_{y=x+1} ggT (b + ay, c) = 1.

Korollar 1. Haben a, b und c keinen gemeinsamen Teiler, und ist k ≥ c, so gibt es unter k aufeinanderfolgenden Gliedern der arithmetischen Progression

b, b + a, b + 2a, …

mindestens eine Zahl, die zu c teilerfremd ist.

Beobachtung II. Das Korollar läßt sich kürzer so aussprechen:

k ≥ c, ggT (a, b, c) = 1 ⟹ m^{x+k}_{y=x+1} ggT (b + ay, c) = 1.

Proposition 3. Sei c ≤ s. Dann gilt

m^{r+s−1}_{y=0} ggT (b + ay, c) = ggT (a, b, c).

Beweis. Setzt man nämlich d = ggT (a, b, c) und a = a′d, b = b′d, c = c′d, so folgt c′ ≤ c, ggT (a′, b′, c′) = 1, also nach Proposition 2

m^{r+s−1}_{y=0} ggT (b′ + a′y, c′) = 1.

Andererseits gilt

m^{r+s−1}_{y=0} ggT (b + ay, c) = m^{r+s−1}_{y=0} ggT (b′d + a′dy, c′d)
= m^{r+s−1}_{y=0} d · ggT (b′ + a′y, c′)
= d · m^{r+s−1}_{y=0} ggT (b′ + a′y, c′)

Proposition 4. Sei k ≤ a; dann gilt

m^{r+s−1}_{y=0} M^{k}_{z=1} ggT (b + ay, z) = D(a, b).

Beweis. Die Behauptung ist trivial für k = 1, da die linke Seite dann gleich 1 ist. Es genügt daher zu zeigen, daß die Aussage für k + 1 gilt, wenn sie für k wahr ist. Nun hat man für alle y ∈ ℕ

M^{k}_{z=1} ggT (b + ay, z) = max { M^{k−1}_{z=1} ggT (b + ay, z), ggT (b + ay, k)}

und folglich

m^{a−1}_{y=0} M^{k}_{z=1} ggT (b + ay, z) = m^{a−1}_{y=0} max { M^{k−1}_{z=1} ggT (b + ay, z), ggT (b + ay, k)}.

Andererseits gilt eine der beiden Gleichungen

max { M^{k−1}_{z=1} ggT (b + ay, z), ggT (b + ay, k)} = M^{k−1}_{z=1} ggT (b + ay, z)

oder

max { M^{k−1}_{z=1} ggT (b + ay, z), ggT (b + ay, k)} = ggT (b + ay, k),

folglich eine der beiden

m^{a−1}_{y=0} max { M^{k−1}_{z=1} ggT (b + ay, z), ggT (b + ay, k)} = m^{a−1}_{y=0} M^{k−1}_{z=1} ggT (b + ay, z) oder

m^{a−1}_{y=0} max { M^{k−1}_{z=1} ggT (b + ay, z), ggT (b + ay, k)} = m^{a−1}_{y=0} ggT (b + ay, k),

und dies kann man so schreiben:

m^{a−1}_{y=0} M^{k}_{z=1} ggT (b + ay, z) = m^{a−1}_{y=0} M^{k−1}_{z=1} ggT (b + ay, z)

oder

m^{a−1}_{y=0} M^{k}_{z=1} ggT (b + ay, z) = m^{a−1}_{y=0} ggT (b + ay, k).

In beiden Formeln ist die rechte Seite ein Teiler von a und b. Betrachten wir die erste; nach Induktionsvoraussetzung ist

m^{a−1}_{y=0} M^{k}_{z=1} ggT (b + ay, z) = D(a, b).

Betrachten wir die zweite. Wegen k ≤ a gilt nach Proposition 3

m^{a−1}_{y=0} ggT (b + ay, k) = ggT (a, b, k),

folglich ist auch

m^{a−1}_{y=0} ggT (b + ay, k) = D(a, b).

Proposition 5. Es gilt

M^{k}_{z=1} ggT (u, z) = max D^{k}_{1} (u).

Beweis. 1. Jede der Zahlen ggT (u, z) ist auch eine der D^{k}_{1} (u). Sie ist nämlich ein Teiler von u, und ≤ k wegen z ≤ k.

2. Andererseits ist jeder D^{k}_{1} (u) eine der ggT (u, z): ist z.B. h | u mit h ≤ k,

so ist h = ggT (u, h).

Proposition 6. Es gilt

m^{a−1}_{y=0} M^{a}_{z=1} ggT (b + ay, z) = ggT (a, b).

Beweis. Nach Proposition 5 ist M^{a}_{z=1} ggT (b + ay, z) der größte unter den Teilern

von b + ay, die a nicht übersteigen; folglich ist, da ggT (a, b) einer dieser Teiler ist,

M^{a}_{z=1} ggT (b + ay, z) ≥ ggT (a, b),

und damit hat man insbesondere

m^{a−1}_{y=0} M^{a}_{z=1} ggT (b + ay, z) ≥ ggT (a, b).

Andererseits ist nach Proposition 4 m^{a−1}_{y=0} M^{a}_{z=1} ggT (b+ay, z) ein gemeinsamer Teiler

von a und b, somit gilt

m^{a−1}_{y=0} M^{a}_{z=1} ggT (b + ay, z) ≤ ggT (a, b).

Diese beiden Ungleichungen widersprechen einander, falls nicht gilt:

m^{a−1}_{y=0} M^{a}_{z=1} ggT (b + ay, z) = ggT (a, b).

Proposition 7. Sei 1 < b ≤ a und ggT (a, b) = 1. Dann ist eine der Zahlen

b, b + a, b + 2a, …, b + (a − 1)a

prim.

Beweis. Nach Proposition 6 gilt wegen ggT (a, b) = 1

m^{a−1}_{y=0} M^{a}_{z=1} ggT (b + ay, z) = 1,

nach Proposition 5 daher

m^{a−1}_{y=0} max D^{a}_{1} (b + ay) = 1.

Bezeichne b+ay′ ein Glied der Reihe b, b+a, b+2a, …, b+(a−1)a, für welches

max D^{a}_{1} (b+ay) minimal wird. Die Gleichung m^{a−1}_{y=0} max D^{a}_{1} (b+ay) = 1 besagt, daß

jeder Teiler von b + ay′ entweder gleich 1 oder > a ist. Also hat b + ay′ keine Teiler ≤ a außer 1.

Wegen b ≤ a folgt andererseits, daß die Glieder b, b+a, b+2a, …, b+(a−1)a alle ≤ a^{2} sind; insbesondere ist b+ay′ ≤ a^{2}. Aber wenn eine Zahl 1 < a+by′ ≤ a^{2} keine Teiler ≤ a außer der 1 hat, ist sie prim. Folglich ist b + ay′ prim.

Proposition 8. Ist ggT (a, b) = 1, so enthält die arithmetische Progression

b, b + a, b + 2a, …, b + (a − 1)a

mindestens eine Primzahl.

Beweis. Indem wir b durch b + a ersetzen, erreichen wir b > 1. Wegen (b, a) = 1 ist entweder b ≤ a oder b > a; im Falle b ≤ a ist Proposition 8 wegen Proposition 7 bewiesen. Sei also b > a. Wir wählen eine Zahl cb teilerfremd zu b und größer als b. Dann enthalten die Glieder b, b + ac, b + 2ac, …, b + (ac − 1)ac eine Primzahl nach Proposition 7. Aber diese Zahlen sind in der arithmetische Progression b, b + a, b + 2a, …, b + (a − 1)a enthalten.

Proposition 9. Ist ggT (a, b) = 1, so enthält die arithmetische Progression

b, b + a, b + 2a, …, b + (a − 1)a

unendlich viele Primzahlen.

Beweis. Nach Proposition 8 enthält die arithmetische Progression mindestens eine Primzahl, sagen wir b + ay. Die Glieder

b + (y + 1)a, b + (y + 2)a, …  (4)

bilden eine arithmetische Progression mit erstem Glied b+(y+1)a und Differenz a. Da b und a teilerfremd sind, sind dies auch b + (y + 1)a und a. Also enthält (4) eine Primzahl, folglich b, b + a, b + 2a, …, mindestens zwei. Ähnlich zeigt man die Existenz von drei, dann von vier Primzahlen etc.

Genua, 21. Januar 1893

Literatur

[1] G. Dirichlet, , Math. Abh. Berlin, 1837; J. Math. 1839

[2] C.F. Gauß, Disquisitiones arithmeticae

[3] Legendre, Teorie dei numeri, vol II, 1830

[4] Sylvester, , C. R. Acad. Sci. Paris 108, 1888

[5] I. Zignano, Intorno ... Annali di Mat.