4. Teilerfremde Folgen und rekursive Konstruktionen
Der Begriff der Teilerfremdheit führt zu einem neuen Blick auf die Unendlichkeit der Primzahlen. Wir definieren hierzu:
Definition (teilerfremde Folge)
Eine unendliche Folge a0, a1, a2, …, an, … natürlicher Zahlen heißt teilerfremd, falls gilt:
(a) | Die Glieder der Folge sind paarweise teilerfremd, d. h. für alle i ≠ j sind die Zahlen ai und aj teilerfremd. |
(b) | an ≥ 2 für alle n. |
Die Bedeutung dieses Begriffs für die Primzahlen zeigt der folgende Satz:
Satz (teilerfremde Folgen und Unendlichkeit der Primzahlen)
Die folgenden Aussagen sind äquivalent:
(1) | Es gibt eine teilerfremde Folge. |
(2) | Es gibt unendlich viele Primzahlen. |
Beweis
(1) impliziert (2): Sei a0, a1, a2, …, an, … eine teilerfremde Folge. Wir setzen:
pn = „der kleinste Primteiler von an“ für alle n.
(Ein solcher Primteiler existiert, da jedes an größer als 1 ist.) Dann ist p0, p1, p2, …, pn, … eine unendliche Folge paarweise verschiedener Primzahlen. Wäre nämlich pi = pj für gewisse Indizes i ≠ j, so wäre pi ein gemeinsamer Teiler von ai und aj, was nach Voraussetzung nicht sein kann.
(2) impliziert (1): Gibt es unendlich viele Primzahlen, so können wir die Menge der Primzahlen in einer unendlichen streng monoton steigenden Folge
a0, a1, a2, …, an, …
aufzählen (also in der Form 2, 3, 5, 7, 11, …). Diese Folge ist eine teilerfremde Folge.
Um die Unendlichkeit der Primzahlen zu zeigen, genügt es also irgendeine unendliche Folge paarweise teilerfremder Zahlen anzugeben. Zur Konstruktion derartiger Folgen wird oft die Methode der Rekursion verwendet: Wir definieren zunächst a0 und weiter
a1 mit Hilfe von a0
a2 mit Hilfe von a0 und a1,
a3 mit Hilfe von a0, a1 und a2, und allgemein
an + 1 mit Hilfe von a0, …, an für alle n ≥ 0.
Kurz: Wir können Folgenglieder mit kleinerem Index verwenden, um ein neues Folgenglied zu definieren.
Beispiele
(1) | Ein einfaches Beispiel für eine rekursive Definition ist die Fakultät n! einer natürlichen Zahl n. Wir definieren rekursiv 0! = 1, (n + 1)! = n! · (n + 1) für alle n ≥ 0. Diese Form der Definition ist die „ordentliche Variante“ der Pünktchennotation n! = 1 · 2 · … · n. Es ergibt sich die Folge 1, 1, 2, 6, 24, 120, … |
(2) | Die monotone Aufzählung p1, p2, p3, … der Primzahlen kann rekursiv definiert werden durch p1 = 2, pn + 1 = „die kleinste Primzahl p mit p > pn“ für alle n ≥ 1. Traditionell beginnt man hier bei mit dem Index 1 anstelle von 0, sodass pn die n-te Primzahl ist. Generell starten wie eine Folge mit einem geeigneten kontextabhängigen Index. Meistens ist dies 0 oder 1. |
(3) | Ein berühmtes Beispiel für eine rekursiv definierte Folge liefern die Fibonacci-Zahlen f0, f1, f2, …, fn, … Sind werden rekursiv definiert durch f0 = 0, f1 = 1, fn + 1 = fn + fn − 1 für alle n ≥ 1. Wir starten also mit 0, 1 und bilden nun wiederholt die Summe der beiden letzten Glieder zur Definition des nächsten Folgenglieds. Es ergibt sich die Folge 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … |
Rekursiv definierte Folgen aus Euklids Beweis
Euklids Beweis der Unendlichkeit der Primzahlen führt direkt zu einer rekursiv definierten Folge von Primzahlen. Wir setzen hierzu
p1 = 2,
pn + 1 = „der kleinste Primteiler von p1 · … · pn + 1“ für alle n ≥ 1.
Der Beweis des Satzes von Euklid zeigt, dass wir dadurch eine unendliche Folge
p1, p2, p3, …, pn, …
von paarweise verschiedenen Primzahlen erhalten. Die ersten Glieder der Folge sind
2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11
Die Folge ist nicht monoton wachsend, aber sie ist frei von Wiederholungen. Wie bei den Euklidischen Zahlen ist auch hier p1 · …· pn + 1 im Allgemeinen nicht prim, sodass wir auf den kleinsten Primteiler dieser Zahl zurückfallen müssen, wenn wir eine unendliche Folge von Primzahlen erhalten wollen. Definieren wir dagegen rekursiv
a1 = 2,
an + 1 = a1 · … · an + 1 für alle n ≥ 1,
so erhalten wir eine streng monoton wachsende Folge
a1, a2, a3, …, an, …
Nach dem Satz über die Konstruktion einer teilerfremden Zahl ist jedes an + 1 teilerfremd zu a1, …, an. Zudem gilt an ≥ 2 für alle n. Damit ist die Folge
a1, a2, a3, …, an, …
teilerfremd. Auch diese Variante zeigt also (mit Hilfe des obigen Äquivalenzsatzes), dass es unendlich viele Primzahlen gibt. Die Folge der an beginnt mit
2, 3, 7, 43, 1807, 3263443, 10650056950807, …
Sie enthält Primzahlen wie 2, 3, 7, 43 und 3263443, aber auch zusammengesetzte Zahlen wie
1807 = 13 · 139, 10650056950807 = 547 · 607 · 1033 · 31051.
Den Unterschied der beiden Argumente können wir so beschreiben: Bei der ersten Rekursion suchen wir in jedem Schritt einen Primteiler. Bei der zweiten Rekursion konstruieren wir zuerst eine teilerfremde Folge und suchen dann für jedes Glied den kleinsten Primteiler, um unendlich viele Primzahlen zu erhalten.
Eine weitere teilerfremde Folge, die aus einer ganz anderen Idee hervorgeht, werden wir bei der Diskussion der Fermat-Zahlen kennenlernen.