Beweise mit einem indirekten Beweis, dass es unendlich viele Primzahlen gibt. Du darfst verwenden: Jede natürliche Zahl größer als \(1\) besitzt mindestens einen Primteiler.
a) Nimm zum Widerspruch an, es gebe nur endlich viele Primzahlen, und bezeichne sie mit \(p_1,p_2,\ldots,p_k\).
b) Betrachte die natürliche Zahl \(N=p_1\cdot p_2\cdots p_k+1\). Begründe, warum keine der angenommenen Primzahlen \(p_1,\ldots,p_k\) die Zahl \(N\) teilt.
c) Nutze die angegebene Tatsache über Primteiler, um den Widerspruch und den Schluss des indirekten Beweises zu formulieren.
Denkanstöße
- Formuliere genau, was die Annahme „Es gibt nur endlich viele Primzahlen“ für eine vollständige Liste bedeuten würde.
- Vergleiche \(N\) mit dem Produkt aller Zahlen dieser angenommenen Liste und achte darauf, welcher Rest bei einer Division entsteht.
- Verbinde anschließend die Aussage „keine Primzahl der Liste teilt \(N\)“ mit der im Text erlaubten Tatsache über natürliche Zahlen größer als \(1\).
Lösung
1. Angenommen, es gibt nur endlich viele Primzahlen \(p_1,p_2,\ldots,p_k\); die Liste enthält also alle Primzahlen.
2. Setze \(N=p_1\cdot p_2\cdots p_k+1\). Für jedes \(p_i\) ist das Produkt \(p_1\cdot p_2\cdots p_k\) durch \(p_i\) teilbar. Bei der Division von \(N\) durch \(p_i\) bleibt deshalb der Rest \(1\). Also teilt keines der \(p_i\) die Zahl \(N\).
3. Es ist \(N>1\). Nach der angegebenen Tatsache besitzt \(N\) daher einen Primteiler \(q\). Dieser Primteiler kann keiner der angeblich vollständigen Liste \(p_1,\ldots,p_k\) angehören.
4. Das widerspricht der Annahme, die Liste enthalte alle Primzahlen. Also gibt es unendlich viele Primzahlen.
Antwort
a) Angenommen, \(p_1,p_2,\ldots,p_k\) sind alle Primzahlen.
b) Keine dieser Primzahlen teilt \(N=p_1\cdot p_2\cdots p_k+1\), denn bei Division durch jedes \(p_i\) bleibt Rest \(1\).
c) Da \(N>1\) einen Primteiler besitzen muss, existiert eine Primzahl außerhalb der angenommenen vollständigen Liste. Das ist ein Widerspruch; folglich gibt es unendlich viele Primzahlen.