Widerspruchsbeweise – Unendlichkeit der Primzahlen

Widerspruchsbeweise – Unendlichkeit der Primzahlen Übung

• Beschreibe, wie du allgemein bei einem Widerspruchsbeweis vorgehst.

  Tipps

  Möchten wir beweisen, dass es unendlich viele Primzahlen gibt, formulieren wir folgende Gegenannahme:

  Es gibt endlich viele Primzahlen.

  Um zu zeigen, dass die Aussage wahr ist, muss man zunächst zeigen, dass die Gegenannahme unwahr ist.

  Lösung

  Es gibt verschiedene Wege, eine mathematische Aussage zu beweisen. Eine besondere Art des Beweises ist der Widerspruchsbeweis. Weil wir bei diesem Verfahren nicht direkt vorgehen, heißt es auch indirekter Beweis. Dabei gehen wir wie folgt vor:

  1. Zuerst formulieren wir die zu beweisende Aussage.
  2. Dann müssen wir die Aussage, die wir beweisen möchten, logisch verneinen. Das ist dann unsere Gegenannahme.
  3. Wir versuchen, bei der Gegenannahme mit logisch richtigen Schritten zu einem Widerspruch zu gelangen.
  4. Wenn uns das gelingt, haben wir gezeigt, dass die Gegenannahme falsch bzw. unwahr ist.
  5. Deshalb muss die ursprüngliche Aussage wahr sein!

• Gib den indirekten Beweis für die Existenz unendlich vieler Primzahlen an.

  Tipps

  Um zu überprüfen, ob eine Zahl keine Primzahl ist, nutzt du die Primfaktorzerlegung:

  Du teilst die Zahl durch alle kleineren Primzahlen. Wenn es dabei keinen Rest gibt, ist die Zahl teilbar durch diese Primzahl – und damit selbst keine Primzahl.

  Die Gegenannahme muss widerlegt werden, damit gezeigt ist, dass die ursprüngliche Aussage richtig bzw. wahr ist.

  Lösung

  Im Folgenden möchten wir zeigen, dass es unendlich viele Primzahlen gibt.

  Aussage: Es gibt unendlich viele Primzahlen.

  Gegenannahme: Es gibt endlich viele Primzahlen.

  Logische Schlüsse

  • Multiplikation aller Primzahlen, wobei $P$ die größte Primzahl ist, und Addition von $1$

  Das Ergebnis nennen wir hier $\Omega$:

  $2\cdot 3\cdot 5\cdot\ ...\ \cdot P+1=\Omega$

  Wir suchen jetzt diejenige Primzahl, durch die $\Omega$ ohne Rest teilbar ist:

  $(2\cdot 3\cdot 5\cdot\ ...\ \cdot P+1):2\quad\rightarrow\quad$ Rest $1$
  $(2\cdot 3\cdot 5\cdot\ ...\ \cdot P+1):3\quad\rightarrow\quad$ Rest $1$
  ...
  $(2\cdot 3\cdot 5\cdot\ ...\ \cdot P+1):P\quad\rightarrow\quad$ Rest $1$

  Schlussfolgerung

  $\Omega$ ist durch keine einzige Primzahl ohne Rest teilbar. Also gibt es diese beiden Optionen:

  • $\Omega$ ist selbst eine Primzahl.
  • $\Omega$ hat noch eine Primzahl als Teiler, die nicht zwischen $2$ und $P$, sondern zwischen $P$ und $\Omega$ liegt.

  Das heißt, dass unsere Liste nicht alle Primzahlen enthält. Die Existenz der größten Primzahl $P$ haben wir aus der Gegenannahme gefolgert. Also muss diese Gegenannahme falsch sein.

  Deshalb können wir schließen, dass es unendlich viele Primzahlen gibt!

• Ermittle die Eigenschaften der gegebenen Terme.

  Tipps

  Wenn eine Zahl $a$ der Teiler einer Zahl $b$ ist, so schreiben wir $a\mid b$.

  Es ist $2n$ mit $n\in\mathbb{N}$ eine gerade Zahl und $2n+1$ mit $n\in\mathbb{N}$ eine ungerade Zahl.

  Schaue dir folgendes Beispiel für $k\in\mathbb{Z}$ an:

  $\underbrace{2\cdot (\underbrace{\underbrace{2\cdot (\underbrace{3n}_{\text{durch } 3 \text{ teilbar}})}_{\text{gerade Zahl}}+1}_{\text{ungerade Zahl}})}_{\text{gerade Zahl}}$

  Der gesamte Ausdruck ist somit eine gerade Zahl.

  Wird eine beliebige Klammer mit einer Zahl multipliziert, so ist diese Zahl auch ihr Teiler.

  Lösung

  Bei einem indirekten Beweis ist es wichtig, Schlüsse zu folgern, die die Gegenannahme widerlegen. Also schauen wir uns nun einige solcher Zusammenhänge an:

  Gerade Zahl

  Eine Zahl $x$ ist genau dann gerade, wenn sie ohne Rest durch $2$ teilbar ist. Wir schreiben dann $2\mid x$ und sprechen „zwei ist ein Teiler von $x$“. Jede Zahl, die mit der $2$ multipliziert wird, ergibt ein gerades Produkt. Demnach gilt:

  $2\mid x$, wenn $x=2n$ mit $n\in\mathbb{N}$

  Ungerade Zahl

  Wird eine Zahl $x$ durch $2$ dividiert und es bleibt ein Rest von $1$, so ist die Zahl $x$ ungerade. Wir schreiben dann $2\nmid x$ und sprechen „zwei ist kein Teiler von $x$“. Demnach gilt:

  $2\nmid x$, wenn $x=2n+1$ mit $n\in\mathbb{N}$

  Zahl durch $3$ teilbar

  Eine Zahl ist genau dann durch drei teilbar, wenn die Division durch $3$ ohne Rest möglich ist. Multiplizierst du eine Zahl mit $3$, so ist das Produkt auch durch $3$ ohne Rest teilbar. Demnach gilt:

  $3\mid x$, wenn $x=3(n+1)$ mit $n\in\mathbb{N}$

  Zahl durch $5$ teilbar

  Eine Zahl ist genau dann durch fünf teilbar, wenn die Division durch $5$ ohne Rest möglich ist. Multiplizierst du eine Zahl mit $5$, so ist das Produkt auch durch $5$ ohne Rest teilbar. Demnach gilt:

  $5\mid x$, wenn $x=5(3n+2)$ mit $n\in\mathbb{N}$

• Prüfe die Richtigkeit der gegebenen Aussage mittels eines indirekten Beweises.

  Tipps

  Schaue dir die Erläuterung folgender mathematischer Schreibweisen an:

  • $2\mid x \quad\rightarrow\quad 2$ ist Teiler von $x$
  • $2\nmid x\quad\rightarrow\quad 2$ ist kein Teiler von $x$

  Du kannst eine gerade und ungerade Zahl mithilfe von natürlichen Zahlen wie folgt darstellen:

  • $2n$ mit $n\in\mathbb{N}$ ist eine gerade Zahl
  • $2n+1$ mit $n\in\mathbb{N}$ ist eine ungerade Zahl

  Lösung

  Wir betrachten im Folgenden die Aussage: „Wenn das Quadrat einer natürlichen Zahl gerade ist, so ist die Zahl selbst gerade.“

  Dieser Aussage können wir Folgendes entnehmen:

  Voraussetzung: $\quad 2\mid x^2; ~x\in\mathbb{N}$

  Behauptung: $\qquad 2\mid x$

  Diese Behauptung möchten wir mit einem Widerspruchsbeweis prüfen. Wir formulieren also eine entsprechende Gegenannahme, die wir widerlegen wollen, um somit indirekt die Behauptung zu beweisen.

  Gegenannahme:
  Wenn das Quadrat einer natürlichen Zahl gerade ist, so ist die Zahl selbst ungerade.
  Es ist also unter der gleichen Voraussetzung die neue Behauptung $2\nmid x$.

  Ansatz:
  $x=2n+1$ mit $n\in\mathbb{N}$ ist eine ungerade Zahl.
  Diese wird nun quadriert zu:

  $x^2=(2n+1)^2$

  Wir erhalten:

  $x^2=4n^2+4n+1=2(2n^2+2n)+1$

  Da $n$ eine natürliche Zahl ist, ist der Ausdruck $2n^2+2n$ ebenfalls eine natürliche Zahl. Wir nennen diesen Ausdruck $m$, also $m=2n^2+2n$. Es folgt dann:

  $x^2=2m+1\quad$ mit $\quad m\in\mathbb{N}$

  Der Ausdruck $2m+1$ mit $m\in\mathbb{N}$ stellt eine ungerade Zahl dar. Das Quadrat einer ungeraden Zahl $x$ ist also wieder eine ungerade Zahl. Somit ist ein Widerspruch der Voraussetzung, dass $2$ ein Teiler von $x^2$ ist bzw. dass $x^2$ eine gerade Zahl ist, erzeugt.

• Gib die Gegenannahme der jeweiligen Aussage an.

  Tipps

  Beim Formulieren der Gegenannahmen musst du die jeweilige Aussage verneinen.

  Schaue dir die verneinte Form einiger Begriffe an:

  • ungerade $\rightarrow$ nicht gerade
  • irrational $\rightarrow$ nicht rational
  • unendlich $\rightarrow$ nicht endlich

  Lösung

  Beim Formulieren einer Gegenannahme müssen wir die jeweilige Aussage verneinen. So erhalten wir:

  Beispiel 1

  • Aussage: $\sqrt{2}$ ist eine irrationale Zahl.
  • Gegenannahme: $\sqrt{2}$ ist eine rationale Zahl.

  Beispiel 2

  • Aussage: Es gibt unendlich viele Primzahlen.
  • Gegenannahme: Es gibt endlich viele Primzahlen.

  Beispiel 3

  • Aussage: Es gibt unter drei irrationalen Zahlen zwei, deren Summe auch irrational ist.
  • Gegenannahme: Es gibt unter drei irrationalen Zahlen keine zwei, deren Summe auch irrational ist.

• Zeige mittels eines Widerspruchsbeweises, dass $\sqrt 2$ eine irrationale Zahl ist.

  Tipps

  Wir formulieren zunächst eine Gegenannahme. Anschließend leiten wir ausgehend von der Gegenannahme einen Ansatz her.

  Die Ausgangsgleichung formen wir geschickt um und folgern Schlüsse, welche dazu führen, dass die Gegenannahme widerlegt wird.

  Zwei natürliche Zahlen sind teilerfremd, wenn sie als gemeinsamen Teiler nur die $1$ haben.

  Lösung

  Wir möchten zeigen, dass $\sqrt{2}$ eine irrationale Zahl ist. Hierzu nutzen wir einen indirekten Beweis.

  Aussage: $\sqrt{2}$ ist eine irrationale Zahl.

  Gegenannahme: $\sqrt 2$ ist eine rationale Zahl.

  Logische Schlüsse

  Wir nehmen an, dass $\sqrt{2}=\frac pq$ ist, wobei $p$ und $q$ teilerfremd sind und der Bruch nicht weiter gekürzt werden kann.

  Wir quadrieren diese Gleichung und stellen sie um:

  $\begin{array}{lllll} \\ \left(\frac pq\right)^2 &=& 2 && \vert \cdot q^2 \\ p^2 &=& 2q^2 && \\ \\ \end{array}$

  $2q^2$ ist eine gerade Zahl, sodass auch $p^2$ gerade ist. Daraus folgt, dass $p$ ebenfalls gerade sein muss.

  Somit lässt sich $p$ durch $p=2r$ darstellen, wobei $r$ eine ganze Zahl ist. Eingesetzt in die obige Gleichung erhalten wir:

  $\begin{array}{lllll} \\ 4r^2 &=& 2q^2 && \vert :2 \\ 2r^2 &=& q^2 && \\ \\ \end{array}$

  Somit ist $q^2$ und auch $q$ gerade. $p$ und $q$ sind also beide durch $2$ teilbar. Wir erhalten einen Widerspruch bezüglich der Teilerfremdheit.

  Demnach ist die Gegenannahme, dass $\sqrt{2}$ eine rationale Zahl ist, falsch bzw. unwahr. Und die Aussage, dass $\sqrt{2}$ eine irrationale Zahl ist, ist richtig bzw. wahr.