Euklid's Beweis über die Unendlichkeit der Primzahlen

Aufgabe Ein berühmter Beweis durch Widerspruch ist ein Beweis von Euklid. Er hat als erster bewiesen, dass es unendlich viele Primzahlen gibt. Sucht diesen Beweis in Büchern oder im Internet und gebt ihn in eigenen Worten auf dieser Seite wieder. Ziel ist, dass ihr gemeinsam einen gut strukturierten Beweis auf der angelegten Wiki-Seite ausformuliert, der so ausführlich ist, dass er auch für andere gut verständlich ist (z.B. für eure Eltern oder Mitschüler). Ihr habt dafür zwei Wochen Zeit. Viel Spaß!

Behauptung: Es gibt unendlich viele Primzahlen.

Beweis:

Hier ist etwas zu tun!!! Es fehlt nur noch ein einziges Argument in Kaninchens Beweis (siehe ganz unten)!!

Wenn wir annehmen würden das es eine größte Primzahl n gibt, dann wären alle Primzahlen

2, 3, 5, 7, 11, 13, ... n

wenn wir allerdings alle Primzahlen multiplizieren, also

2 mal 3 mal 5 mal 7 mal ... mal n + 1

das wäre eine primzahl da sie durch keine der Primzahlen teilen lässt, da der Rest 1 bleibt und sie wäre deutlich größer als n.

Allerdings widerspricht das der Behauptung es gäbe eine größte Primzahl n.

QED

Merke Das ist schonmal ein guter Start! Ich frage mich gerade folgendes: Ist das, was du tust $2\cdot 3\cdot 5\cdot \ldots \cdot n +1$ eigentlich ein Konstruktionsverfahren für Primzahlen? Kriege ich dadurch immer eine neue Primzahl? Forscht mal nach und eventuell führt es dazu, dass ihr eure Beweise nochmals ein klein wenig umschreibt! (Leider führt dies nicht immer zu einer weiteren Primzahl, siehe weiter unten bei Kaninchens Beitrag!) Noch eine Sache, auf die man genauer eingehen könnte/sollte: Primzahlen sind Zahlen, die nur durch sich selbst und 1 teilbar sind. Warum darf man davon ausgehen, dass eine Zahl, die durch keine Primzahl teilbar ist, selbst Primzahl ist?

Behauptung: Es gibt unendlich viele Primzahlen

Beweis für die Behauptung: Nehmen wir an es gibt nur die Primzahlen 2,3 und 5 dann wäre 5 die größte Primzahl.
Aber wenn man 2*3*5+1 rechnet, (Ergebnis: 31) kommt in jedem Fall eine neue größere Primzahl raus, weil: würde man rechnen 2*3*5 (Ergebnis 30) wäre es durch alle Primzahlen (in dem Fall 2,3 und 5) teilbar.
Das heißt wenn man +1 rechnet, ist das Ergebnis durch keine Primzahl teilbar und weil alle Zahlen die KEINE Primzahlen sind Vielfache einer Primzahl sind, ist das Ergebnis in jedem Fall eine Primzahl.;-D Qed-man 19:30, 10. Sep. 2012 (CEST)

Merke Kaninchen schreibt weiter unten, warum das Ergebnis von 2*3*5*...*p+1 nicht immer Primzahl sein muss, man den Beweis aber dennoch auf diese Weise hinkriegt! Auch PhilipHP (eigentlich Klasse 10!) zeigt in seinem Beweis, wie man hier argumentieren muss. Schreibt das jemand noch sauber auf, indem er/sie Kaninchens Beweis um ein Argument ergänzt?

---

Voraussetzung Sei $\mathbb{P}$ die Menge der Primzahlen.

Behauptung: $|\mathbb{P}| = \infty$

Beweis: Indirekt.
Indirekte Annahme: $|\mathbb{P}| = k , k \in \mathbb{N}$
Aus der indirekten Annahme folgt, dass es eine größte Primzahl gibt.

Sei $n =1+ \prod_{a=0}^{k} \mathbb{P}_a$ das Produkt aller Primzahlen in $\mathbb{P} + 1$.
Da n offensichtlich keinen Teiler in $\mathbb{P}$ besitzt, muss n entweder durch eine in $\mathbb{P}$ nicht vorhandene Primzahl teilbar sein, oder selbst Primzahl sein.

PhilipHP

Behauptung: Es gibt unendlich viele Primzahlen

Beweis: Angenommen es gibt endlich viele Primzahlen: 2, 3, 5, 7,...p; dann ist p die größte Primzahl. Nehmen wir an es gäbe nur die Primzahlen 2, 3 und 5, dann wäre 5 p. Wenn wir diese 3 Primzahlen miteinander multiplizieren und dann 1 addieren, also 2*3*5*1=31 dann ist das Ergebnis auf jeden Fall eine Primzahl und dazu noch größer als p, dies widerspricht, dass p die größte Primzahl sei. Nehmen wir jetzt allerdings an, dass es nur die Primzahlen 2, 3, 5, 7, 11 und 13 gäbe, dann wäre in diesem Fall 13 p. 2*3*5*7*11*13+1=30031; 59*509=30031 das heißt 30030 ist keine Primzahl, was dazu bedeutet, dass die Theorie, dass wenn man die Primzahlen miteinander multipliziert und 1 addiert, dass auf jeden Fall eine neue Primzahl ensteht, falsch ist. Jedoch ist 30030 das Vielfache von zwei Primzahlen, nämlich 59 und 509. Die Primzahlen 59 und 509 sind dazu noch größer als p, das heißt p ist unmöglich die größte Primzahl.

Wenn man also 2*3*5*...*p+1=z rechnet, dann ist z entweder eine neue Primzahl oder das Vielfache einer Primzahl, die größer als die Primzahlen in der Rechnung ist.

Dies widerspricht der Annahme, es gäbe eine endliche Anzahl von Primzahlen. Kaninchen

Der Beweis von Kaninchen gefällt mir schon ganz gut, weil da auch einige Gedanken drin stehen, die man sich im Beweisverlauf machen muss. Was mir noch fehlt ist die Begründung, dass - falls z keine Primzahl ist - die Primfaktoren von z größer als die Primzahlen 2,3,5,...,p sein müssen. A.Hoffkamp 13:26, 11. Okt. 2012 (CEST)