5. Die Teilerfremdheit aufeinanderfolgender Zahlen
Euklids Beweis verwendet entscheidend, dass für alle Primzahlen p1, …, pk die beiden Zahlen p1 ·…· pk und p1 ·…· pk + 1 keinen gemeinsamen Teiler größer als 1 besitzen. Allgemein gilt:
Satz (Teilerfremdheit aufeinanderfolgender Zahlen)
Sei n ≥ 1 eine natürliche Zahl. Dann sind n und n + 1 teilerfremd.
Beweis
Sei d > 1 ein Teiler von n. Dann hat n + 1 den Rest 1 bei Division durch d, sodass d kein Teiler von n + 1 ist. Dies zeigt, dass die Zahlen n und n + 1 teilerfremd sind.
Der Satz lässt sich auch als Spezialfall des Satzes über die Konstruktion teilerfremder Zahlen (mit nur einer Zahl a1 = n und a1 + 1 = n + 1) ansehen.
Damit zeigen wir noch einmal:
Satz (Unendlichkeit der Primzahlen)
Sei n ≥ 1, und seien p1, …, pn Primzahlen. Dann gibt es eine Primzahl p, die von allen Primzahlen p1, …, pn verschieden ist.
Beweis
Wir setzen a = p1 · … · pn und b = a + 1. Dann sind a und b teilerfremd. Wegen b ≥ 2 existiert ein Primteiler p von b. Dann ist p kein Teiler von a. Da die Zahlen p1, …, pn Teiler von a sind, ist p wie gewünscht.
Der Satz über die Teilerfremdheit aufeinanderfolgender Zahlen zeigt noch einmal, dass wir auch −1 statt +1 verwenden können, falls a = p1 ·… · pn größer ist als 2, sodass b = a − 1 ≥ 2 einen Primteiler besitzt. Denn die Zahlen a − 1 und a folgen aufeinander, sodass a − 1 und a teilerfremd sind. Genau wie die beiden Zahlen a und a + 1.
Diese Variante der Darstellung des Beweises von Euklid ist ein weiteres Beispiel für die Nützlichkeit der Formulierung von Hilfssätzen. Die Betonung der Teilerfremdheit aufeinanderfolgender Zahlen führt zur rekursiven Konstruktion einer Folge, aus der sich die Unendlichkeit der Primzahlen ablesen lässt. Das Argument wurde offenbar erst 2006 von Filip Saidak explizit notiert:
Weiterer Beweis des Satzes von Euklid
Wir definieren eine unendliche Folge b1, b2, b3, …, bn, … natürlicher Zahlen rekursiv durch
b1 = 2,
bn + 1 = bn (bn + 1) für alle n ≥ 0.
Da zwei aufeinanderfolgende natürliche Zahlen teilerfremd sind, kommt in jedem Schritt mindestens ein neuer Primteiler hinzu. Für alle n ≥ 1 hat also die Zahl bn mindestens n verschiedene Primteiler. Folglich gibt es unendlich viele Primzahlen.
Die ersten Zahlen der Folge sind b1 = 2 und
b2 = b1 (b1 + 1) = 2 · 3 = 6
b3 = b2 (b2 + 1) = 2 · 3 · 7 = 42
b4 = b3 (b3 + 1) = 2 · 3 · 7 · 43 = 1806
b5 = b4 (b4 + 1) = 2 · 3 · 7 · 43 · 1807 = 3263442
Die Folge ist nicht teilerfremd, nach Konstruktion ist sogar jedes Folgenglied bn ein Teiler von bn + 1. Eine teilerfremde Folge erhalten wir durch die Division bn + 1/bn aufeinanderfolgender Glieder (mit b0 = 1). Dies liefert die Folge
2, 3, 7, 43, 1807, 3263443, …
der an, die wir im vorangehenden Essay bereits untersucht hatten, mit
a1 = 2, an + 1 = a1 · … · an + 1 für alle n ≥ 1.
Die konstruierte Folge bn ist damit die Folge der Partialprodukte der Folge der an. Es gilt
a1 = 2 = b1
a1 · a2 = a1 (a1 + 1) = b1 (b1 + 1) = b2
a1 · a2 · a3 = a1 · a2 · (a1 · a2 + 1) = b2 · (b2 + 1) = b3
usw. Der Beweis von Saidak ist also letztendlich eine weitere rekursive Version des Beweises von Euklid. Dennoch ist das Argument für sich genommen sehr schön, und der Beweis wirkt auf viele Leser anders als der Beweis von Euklid, der traditionell nicht rekursiv präsentiert wird. Darüber hinaus zeigt er: Es lohnt sich, über klassische Argumente immer wieder neu nachzudenken. Die Mathematik ist niemals fertig.