a) Keine der Primzahlen p₁, p₂, ...,p_n 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).