2. Euklids Beweis

Wir betrachten nun den Beweis unseres Satzes im Detail. Den Satz selbst formulieren wir in der das Argument vorbereitenden Version:

Satz (Unendlichkeit der Primzahlen)

Sei n ≥ 1, und seien p₁, …, p_n Primzahlen. Dann gibt es eine Primzahl p, die von allen Primzahlen p₁, …, p_n verschieden ist.

Beweis

Wir setzen

a = p₁ · … · p_n + 1.

Dann ist a eine natürliche Zahl, die bei der Division durch p₁, …, p_n jeweils den Rest 1 besitzt. Damit ist a durch keine der Primzahlen p₁, …, p_n teilbar. Sei nun p der kleinste Teiler von a, der größer als 1 ist (ist die Zahl a selbst prim, so ist p = a). Dann ist p eine von allen Primzahlen p₁, …, p_n verschiedene Primzahl.

Wie ausführlich muss ein Beweis sein? Auf diese Frage gibt es keine definitive Antwort. Stil und Ausführlichkeit eines Beweises sind geprägt durch die mathematische Fachkultur und durch die Frage, für welche Leser der Beweis gedacht ist. In obiger Form ist der Beweis in zahlreichen Lehrbüchern zu finden. Als Kontrast betrachten wie eine ausführlichere Version:

Ausführlicher Beweis

Wir setzen

a = p₁ · … · p_n + 1.

Dann ist a eine natürliche Zahl, die bei der Division durch p₁ den Rest 1 besitzt. Denn es gilt p₁ ≥ 2 und die Division von a durch p₁ mit Rest lautet

a = (p₂ · … · p_n) p₁ + 1.

Damit ist a nicht durch p₁ teilbar, da die Division von a durch p₁ den Rest 0 ergeben würde, falls p₁ ein Teiler von a wäre. Analog ist a auch nicht durch die Primzahlen p₂, …, p_n teilbar. Wir setzen nun:

p = „die kleinste natürliche Zahl größer als 1, die ein Teiler von a ist“.

zur Existenz von p:

Da die Zahl a durch sich selbst teilbar und größer als 1 ist, ist die Menge

A = { d > 1 | d ist ein Teiler von a }

nichtleer (da a ein Element von A ist). Da jede nichtleere Menge natürlicher Zahlen ein kleinstes Element besitzt, existiert p.

Die Zahl p ist prim, da andernfalls k₁, k₂ mit 2 ≤ k₁, k₂ < p existieren würden mit p = k₁ k₂. Dann wäre aber 2 ≤ k₁ < p und k₁ ein Teiler von a, im Widerspruch zur Definition von p.

Nach Definition ist die Primzahl p ein Teiler von a. Wir hatten aber schon gesehen, dass keine der Primzahlen p₁, …, p_n die Zahl a teilt. Damit ist p eine von den Primzahlen p₁, …, p_n verschiedene Primzahl. Denn p hat eine Eigenschaft (Teiler von a zu sein), die die Zahlen p₁, …, p_n nicht haben.

Ausführliche Beweise können helfen, bestimmte Stellen, an denen ein Leser hängenbleiben könnte, zu vereinfachen. Auf der anderen Seite haben sie den Nachteil, dem Leser das Mitdenken und das präzise Formulieren von Warum-Fragen abzunehmen − beides äußerst wertvolle Dinge, die kontinuierlich trainiert werden wollen. Kurze Beweise sind in aller Regel besser, auch wenn sie öfters offene Fragen hinterlassen. Sie konzentrieren sich auf das Wesentliche und zeichnen dadurch eine klare Argumentationslinie. Ein Beweis ist keine bequeme Kutsche, die den Leser zum Satz hinfährt. Eher ein anstrengender Wanderpfad zum Gipfel.

Wiederkehrende Argumente, die nichts mit dem eigentlichen Beweis zu tun haben, stören den Beweisfluss. Es ist daher durchaus sinnvoll, vorab folgenden Satz zu diskutieren:

Satz (Prinzip vom kleinsten Element)

Sei A eine nichtleere Menge natürlicher Zahlen. Dann besitzt A ein kleinstes Element, d. h., es gibt eine natürliche Zahl n* mit den Eigenschaften:

(a)	n* ist ein Element von A.

(b)	Für alle Elemente n von A gilt n* ≤ n.

Dieser Satz wird oft ohne Beweis als „offensichtlich“ verwendet. Er kann mit Hilfe vollständiger Induktion bewiesen werden (und er ist sogar äquivalent zur Induktion). Eine einfache Folgerung ist:

Korollar (Existenz von Primteilern)

Sei a ≥ 2 eine natürliche Zahl. Dann besitzt a einen Primteiler, d. h., es gibt eine Primzahl p, die ein Teiler von a ist.

Zum Beweis des Korollars betrachten wir die Menge A und ihr kleinstes Element p wie im ausführlichen Beweis der Unendlichkeit der Primzahlen oben.