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 p₁, p₂, ...p_n.
   Bilde dann die Zahl z = p₁·p₂·...·p_n + 1 und führe die Annahme zum Widerspruch.
2. Das Verfahren, aus einer gegebenen Menge von Primzahlen M = { p₁, p₂, ...p_s } andere Primzahlen zu finden, indem man eine Zahl z = p_a·p_b·...·p_r + 1 bildet und deren Primteiler bestimmt, nennt man Euklids Primzahlmaschine ( p_a, p_b,...p_r 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.

Lösung