sofatutor 30 Tage
kostenlos ausprobieren

Videos & Übungen für alle Fächer & Klassenstufen

Widerspruchsbeweise – Unendlichkeit der Primzahlen 05:47 min

Textversion des Videos

Transkript Widerspruchsbeweise – Unendlichkeit der Primzahlen

Was für ein prima Wetter! Euklid genießt einen Tag am Strand. Ob er über seine Primadonna nachdenkt? Oder die Primeln in seinem Garten? Nein, über Primzahlen! Gibt es davon so viele wie Sand am Meer oder vielleicht noch mehr? Unendlich viele Primzahlen gibt es sogar! Und das zeigen wir mit einem Widerspruchsbeweis. Wie funktioniert das nochmal mit diesen Primzahlen? Primzahlen sind die Zahlen, die nur durch eins und durch sich selbst teilbar sind! Also zum Beispiel 2 oder 3, 4 aber nicht, 5 schon, 7 und 11 und so weiter. Und die 1 ist auch keine Primzahl. Um zu überprüfen, ob eine Zahl keine Primzahl ist, benutzt 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. Aber wie können wir denn jetzt sicher sein, dass es unendlich viele Primzahlen gibt? Um wirklich etwas ohne Zweifel wissen zu können, benutzt man in der Mathematik Beweise. Und eine besondere Art des Beweises ist der Widerspruchsbeweis. Dazu rufen wir uns nochmal genau die Aussage ins Gedächtnis, die wir beweisen wollen nämlich, dass es unendlich viele Primzahlen gibt. Und anstatt das direkt zu beweisen, gehen wir beim Widerspruchsbeweis von der logischen Verneinung aus! Weil wir bei diesem Verfahren nicht direkt vorgehen, heißt es auch indirekter Beweis. Bei logischen Verneinungen muss man aufpassen: Die Verneinung muss wirklich alles enthalten, was nicht die ursprüngliche Aussage ist. Zum Beispiel ist die Verneinung der Aussage "heute scheint die Sonne" eben nicht so etwas wie "heute ist es bewölkt", sondern schlicht "heute scheint die Sonne nicht". Die logische Verneinung der Aussage "es gibt unendlich viele Primzahlen" lautet "es gibt nur endlich viele Primzahlen". Wir nennen diese verneinte Aussage dann "Gegenannahme". Die Idee dieses Beweisverfahrens ist es, nun von der Gegenannahme aus zu einem Widerspruch zu gelangen. Wenn wir mit korrekten Schlüssen einen Widerspruch finden, muss die Gegenannahme falsch sein. Und da unsere Gegenannahme ja die Verneinung unserer gewünschten Aussage war, muss die also stimmen. Okay, das klingt kompliziert wir versuchen es einfach mal! Also: die Gegenannahme lautet: es gibt nur endlich viele Primzahlen. Dann gibt es auch eine größte Primzahl! Die nennen wir P. Also können wir alle Primzahlen, die es gibt, in eine Liste packen die Liste kann sehr lang sein, aber sie endet mit P, der größten Primzahl. Was können wir mit dieser Liste anfangen? Wenn wir alle Primzahlen auf der Liste miteinander multiplizieren und dann noch 1 addieren was ist das für eine Zahl? Nennen wir sie doch mal Omega, das klingt schön ominös. Irgendwie müssen wir eine Eigenschaft von Primzahlen benutzen, bis jetzt haben wir sie ja nur aufgelistet. Versuchen wir's mal mit der Primfaktorzerlegung. Was sind denn die Primfaktoren von Omega? Wenn wir Omega durch 2 teilen, ist dieses Produkt durch 2 teilbar aber weil wir noch 1 addieren, haben wir einen Rest von 1. Wenn wir durch 3 teilen, ist das Produkt wieder durch 3 teilbar, und wegen "plus 1" haben wir wieder einen Rest von 1 und so weiter bis P – da ist wieder das Produkt durch P teilbar und es bleibt ein Rest von 1. Egal, durch welche der Primzahlen wir Omega teilen, immer bleibt ein Rest von 1. Also ist Omega durch keine einzige Primzahl teilbar! Na aber Moment mal! Entweder ist Omega dann selbst eine Primzahl, weil Omega durch keine einzige Primzahl teilbar ist. Oder Omega hat noch eine Primzahl als Teiler, die nicht zwischen 2 und P liegt, sondern zwischen P und Omega. Aber beides kann nicht stimmen, denn unsere Liste sollte alle Primzahlen enthalten. Und da waren wir uns wiederum sicher, denn sie besteht aus allen Primzahlen von 2 bis hin zu P, der größten Primzahl. Die Existenz der größten Primzahl P haben wir aus der Gegenannahme gefolgert, dass es nur endlich viele Primzahlen gibt. Dann muss diese Gegenannahme also falsch gewesen sein! Und deshalb können wir schließen, dass es unendlich viele Primzahlen gibt! Beweis fertig – q.e.d. Also nochmal im Überblick: wie funktioniert ein Widerspruchsbeweis? Zuerst müssen wir die Aussage, die wir beweisen wollen, logisch verneinen. Das ist dann unsere Gegenannahme. Aus ihr versuchen wir mit logisch richtigen Schritten zu einem Widerspruch zu gelangen. Wenn wir das schaffen, war die Gegenannahme falsch und deshalb muss die ursprüngliche Aussage wahr gewesen sein! Ein ziemlich mächtiges Verfahren ist das wenn du etwas beweisen musst und nicht direkt auf eine Idee kommst, versuchs mal indirekt! Euklids prima Stimmung wird leider etwas getrübt denn auch, wenn er jetzt sicher weiß, dass es unendlich viele Primzahlen gibt findet seine Primadonna es gar nicht prima, dass er den ganzen Tag faul am Strand lag. Zur Strafe verdonnert sie ihn, den Strand zu fegen sein Widerspruch wurde nicht akzeptiert!

4 Kommentare
  1. cool
    lg

    𝒸𝒴®
    𝒸𝒴®

    Von Yiren Y., vor 7 Monaten
  2. Hallo Mousaalbakour 1975,
    Primzahlen sind nur durch 1 und sich selbst teilbar. Wäre 9 eine Primzahl, dürfte sie durch keine andere Zahl als 1 und 9 teilbar sein. Die 9 ist allerdings auch durch 3 teilbar, ohne dass ein Rest übrig bleibt (9:3=3). Deshalb ist die 9 keine Primzahl.
    Ich hoffe, dass wir dir weiterhelfen konnten.
    Liebe Grüße aus der Redaktion

    Von Jonas D., vor mehr als einem Jahr
  3. ist die neun keine Primzahl

    Von Rima A., vor mehr als einem Jahr
  4. Ich finde es einfach nur toll
    DANKE

    Von Rima A., vor etwa 2 Jahren

Widerspruchsbeweise – Unendlichkeit der Primzahlen Übung

Du möchtest dein gelerntes Wissen anwenden? Mit den Aufgaben zum Video Widerspruchsbeweise – Unendlichkeit der Primzahlen kannst du es wiederholen und üben.

  • Beschreibe, wie du allgemein bei einem Widerspruchsbeweis vorgehst.

    Tipps

    Möchten wir beweisen, dass es unendlich viele Primzahlen gibt, so 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 falsch 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 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, benutzt 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 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 nun 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 die beiden folgenden 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.

    Schau 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 im Folgenden 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

    Schau 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 mit Hilfe 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 beweisen. 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 nun $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.

    Schau 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! Und die Aussage, dass $\sqrt{2}$ eine irrationale Zahl ist, ist richtig!