Die "Primzahlmaschine" von Euklid

Die Aufgabe stammt in allen wesentlichen Teilen aus dem Buch von E. Behrends: "Fünf Minuten Mathematik", erschienen im Vieweg - Verlag. Dem Buch verdankt unsere Arbeitsgemeinschaft eine Fülle von Anregungen.



  1. Zeige, dass es unendlich viele Primzahlen gibt.
    Gehe dazu wie folgt vor.
    Angenommen, es gäbe nur endlich viele Primzahlen p1, p2, ...pn.
    Bilde dann die Zahl z = p1·p2·...·pn + 1 und führe die Annahme zum Widerspruch.
  2. Das Verfahren, aus einer gegebenen Menge von Primzahlen M = { p1, p2, ...ps } andere Primzahlen zu finden, indem man eine Zahl z = pa·pb·...·pr + 1 bildet und deren Primteiler bestimmt, nennt man Euklids Primzahlmaschine ( pa, pb,...pr sind Elemente aus M. In dem Produkt müssen nicht alle Primzahlen aus M vorkommen, andererseits kann eine Primzahl auch mehrfach darin vorkommen.)
    Lässt sich ausgehend von der Primzahl 2 jede andere mit Euklids Primzahlmaschine konstruieren?
    Beweise dazu durch vollständige Induktion:
    Für jede natürliche Zahl n gilt, dass man alle Primzahlen, die kleiner sind als n, mit Euklids Primzahlmaschine konstruieren kann.

a) Keine der Primzahlen p1, p2, ...,pn ist Teiler von z. Nun muss aber z mindestens einen Primteiler haben ( genau einen dann, wenn z selbst eine Primzahl ist). Also gibt es mindestens eine Primzahl, die in der gegebenen Menge von Primzahlen nicht vorkommt.

Es folgt, dass es beliebig viele und damit auch beliebig große Primzahlen gibt.


b) Beweis durch vollständige Induktion.

1) Induktionsanfang. Wir konstruieren die ersten Primzahlen nach 2:
3 = 2 + 1; 5 = 2•2 + 1; 7 = 2•3 + 1

2) Die Aussage sei richtig für eine natürliche Zahl n. Zu zeigen ist, dass sie unter dieser Voraussetzung auch für n + 1 richtig ist.

Im Fall, dass n keine Primzahl ist, muss nichts bewiesen werden: Denn wir setzen ja voraus, dass alle Primzahlen, die kleiner als n sind, durch Euklids Maschine konstruiert werden können.

Im Fall, dass n eine Primzahl ist, betrachten wir die Zahl n – 1. Nach Voraussetzung sind alle Primteiler von n – 1 durch Euklids Maschine konstruiert.
Damit lässt sich n – 1 als ein Produkt bereits konstruierter Primzahlen schreiben. Und n ist gleich diesem Produkt plus 1. So ist die Primzahl n mit Euklids Primzahlmaschine konstruiert worden, und es folgt die Richtigkeit der Behauptung für n+1.

Hinweis. Zum Induktionsanfang hätte es genügt, die Primzahl 3 zu konstruieren. Übrigens lassen sich 5 und 7 auch auf andere Weise aus 2 und 3 mit Euklids Maschine finden: So ist

3•3 + 1 = 10; und 10 hat die Primteiler 2 ( bereits vorhanden) und 5 (neu!).

Und 2•2•3 + 1 = 13 ( Konstruktion der Primzahl 13). Und 13 + 1 = 14 ( Primteiler 2 und 7).