Kurs:Vorkurs Mathematik (Osnabrück 2021)/Vorlesung 2/kontrolle

Wir erinnern an einige weitere Begriffe. Man sagt, dass eine ganze Zahl ${}a$ eine ganze Zahl ${}b$ teilt

Eine für manche Anfänger überraschende Beobachtung ist, dass an der Universität auch Sachen gemacht werden, die man doch schon in der Grundschule gemacht hat. Es werden scheinbar einfache Rechenoperationen wie zählen, addieren, multiplizieren, teilen thematisiert.

Der Punkt ist, dass diese Sachen allenfalls in ihrer rechnerischen Handhabung einfach sind, aber keineswegs in ihrer theoretischen Fundierung. Für das Erlernen von Grundprinzipien ist es wichtig, allein in begrenzten Zahlenbereichen wie ${}\mathbb {N}$ ohne Bezug auf umfassendere Zahlenbereiche wie ${}\mathbb {R}$ zu argumentieren. Das gilt in besonderem Maße für Lehramtsstudenten. Die Beschränkung der Mittel macht diese übersichtlicher und zwingt zu einer stringenteren Argumentation.

Es ist ein wichtiges Lernziel, Voraussetzungen von Argumentationsmöglichkeiten, Voraussetzungen von Rechenoperationen, logische Abhängigkeiten von Aussagen und Hierarchien von Strukturen zu erkennen. Die aus der Schule bekannten Möglichkeiten werden allesamt nach und nach (typischerweise im Laufe des ersten Semesters) in einer begründeten Weise erschlossen und stehen dann wieder zur Verfügung.

 

(oder dass ${}a$ ein Teiler von ${}b$ ist oder dass ${}b$ ein Vielfaches von ${}a$ ist), wenn es eine weitere ganze Zahl ${}c$ mit ${}b=ac$ gibt.

Gleichungen treten in der Mathematik mit recht verschiedenen Funktionen auf. Eine wichtige Funktion ist, dass man mit Gleichungen bzw. der Lösbarkeit von Gleichungen Sachverhalte kompakt ausdrücken kann. So kann man ${}x>y$ dadurch ausdrücken, dass es eine positive Zahl ${}z$ derart gibt, dass ${}x=y+z$ gilt, oder die Teilbarkeit einer natürlichen Zahl ${}b$ durch eine natürliche Zahl ${}a$ bedeutet die Existenz einer weiteren Zahl ${}c$ mit ${}b=ac$, eine Zahl ${}m$ ist gerade, wenn sie die Form ${}m=2k$ besitzt, und ungerade, wenn sie die Form ${}m=2k+1$ besitzt, die Division mit Rest bedeutet, dass man ${}n=qd+r$ schreiben kann (statt etwas zu sagen wie ${}n:d$ ist ${}q$ Rest ${}r$).

Die drei wesentlichen Vorteile dieser Vorgehensweise sind:

1. Man kann die Eigenschaften im gleichen Zahlenbereich formulieren (statt beispielsweise zu sagen, dass bei der in ${}\mathbb {Q}$ durchgeführten Division ${}n/2$ eine ganze Zahl rauskommt oder nicht).
2. Man kann Gleichungen gut weiterverarbeiten, in andere Zusammenhänge einsetzen.
3. Mit Gleichungen kann man Gesetzmäßigkeiten beweisen.

 

Beispielsweise ist ${}3$ ein Teiler von ${}15$, aber ${}2$ ist kein Teiler von ${}15$. Eine gerade Zahl ist eine ganze Zahl, die ein Vielfaches von ${}2$ ist, eine ungerade Zahl ist eine ganze Zahl, die kein Vielfaches von ${}2$ ist. Wenn ${}a$ ein Teiler von ${}b$ ist, so verwenden wir die Bezeichnung ${}{\frac {b}{a}}$ für diejenige (eindeutig bestimmte) ganze Zahl ${}c$, für die die Gleichheit ${}b=ac$ gilt.

Primzahlen

Das Sieb des Eratosthenes liefert eine einfache Methode, eine Liste von Primzahlen unterhalb einer bestimmten Größe ${}k$ zu erstellen. Man streicht einfach die echten Vielfachen der kleinen (kleiner als oder gleich ${}{\sqrt {k}}$) schon etablierten Primzahlen durch, die verbleibenden Zahlen sind prim.

Definition Referenznummer erstellen

Eine natürliche Zahl ${}n\geq 2$ heißt eine Primzahl, wenn die einzigen natürlichen Teiler von ihr ${}1$ und ${}n$ sind.

Eine Primzahl ist also eine natürliche Zahl, die genau zwei Teiler hat, nämlich ${}1$ und ${}n$, und die müssen verschieden sein. ${}1$ ist also keine Primzahl.

Die ersten Primzahlen sind ${}2,3,5,7,11,13,17,19,23,29,31,{\ldots }$.

Satz Satz 2.2 ändern

Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

${}n=p_{1}\cdot p_{2}{\cdots }p_{r}\,$

mit Primzahlen ${}p_{i}$.

Beweis

Wir beweisen die Existenz durch Induktion über ${}n$.  Für ${}n=2$ liegt eine Primzahl vor.

In der Mathematik spielen Extremfälle eine gewichtige Rolle und werden in aller Regel miterfasst. So ist die leere Menge eine Menge, die ${}0$ eine natürliche Zahl, man arbeitet mit ${}\geq$ statt mit ${}>$, es gibt den Nullraum und konstante Funktionen, ein Produkt darf auch aus einem einzelnen Faktor bestehen. Man erlaubt also erst mal möglichst viel und schließt Sachen nur aus, wenn es wirklich sein muss.

Auf den ersten Blick sind solche Extremfälle untypisch, sie erfüllen aber häufig Eigenschaften, die für den strukturellen Aufbau wichtig sind. Die ${}0$ ist das neutrale Element der Addition und erfüllt somit eine zentrale algebraische Funktion, die Gleichheit von zwei Zahlen bedeutet, dass ihre Differenz gleich ${}0$ ist, die Disjunktheit von Mengen bedeutet, dass ihr Durchschnitt leer ist, mit dem Nullraum kann man über die Restklassenbildung die Übereinstimmung von Untervekorräumen ausdrücken.

Dieser inklusive Aspekt spiegelt sich auch in den Begriffen wider, so ist ein Quadrat auch ein Rechteck, ein Rechteck ist auch ein Viereck, eine natürliche Zahl ist auch eine ganze Zahl, etc.

 

 Bei

${}n\geq 3$ ist entweder ${}n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber ${}n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung ${}n=ab$ mit kleineren Zahlen ${}a,b<n$. Für diese Zahlen gibt es nach Induktionsvoraussetzung jeweils eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für ${}n$ zusammen.

Man nennt einen Existenzbeweis konstruktiv, wenn es die in ihm verwendete Methode für jede „Eingabe“ erlaubt, effektiv das im Satz behauptete zugehörige Objekt zu konstruieren. Ein konstruktiver Beweis liefert also zugleich eine Handlungsanweisung, wie das existierende Objekt zu finden ist. Dies schließt nicht aus, dass es einen Algorithmus gibt, mit dem man das Objekt schneller finden kann. Bei einem nichtkonstuktiven Existenzbeweis wird nur die reine Existenz gezeigt, ohne Hinweis, wie man das existierende Objekt finden könnte.

Typische Beispiele:

Der Beweis zur Existenz der Primfaktorzerlegung ist konstruktiv. Sobald man eine Faktorisierung gefunden hat, macht man mit den Faktoren weiter.

Der Beweis zur Darstellung im Zehnersystem ist konstruktiv (wegen der verwendeten Division mit Rest siehe den folgenden Punkt). Mit dieser Methode kann man aus einer Darstellung einer Zahl in einem anderen Stellenwertsystem die Darstellung im Zehnersystem ausrechnen (meistens beginnt man aber mit den hohen Zehnerpotenzen).

Der Beweis des Lemmas von Bezout ist konstruktiv und bildet in einer deutlich optimierten Form die Grundlage für den euklidischen Algorithmus.

Der Beweis der Division mit Rest ist zwar konstruktiv, es ist aber extrem umständlich, entlang des Beweises die Darstellung zu finden. Stattdessen schaut man nach dem maximalen Vielfachen von ${}d$, was noch unterhalb von ${}n$ liegt.

Der Beweis des Satzes von Euklid über die Unendlichkeit der Primzahlen ist nicht konstruktiv. Wenn man die ersten ${}k$ Primzahlen nimmt und das dortige Produkt ${}p_{1}p_{2}\cdots p_{k}+1$ betrachtet, so weiß man nach dem Beweis, dass diese Zahl einen neuen Primteiler haben muss, dieser ist aber um ein Vielfaches größer als die nächste Primzahl ${}p_{k+1}$, die man mit dem Sieb des Eratosthenes finden kann.

 

 

$\Box$

Für ${}105$ beispielsweise findet man den Primfaktor ${}3$ und kann daher ${}105=3\cdot 35$ schreiben. Für ${}35$ hat man die Zerlegung ${}35=5\cdot 7$ und man erhält

${}105=3\cdot 5\cdot 7\,.$

Wenn man mit dem Primfaktor ${}5$ startet, so ergibt sich ${}105=5\cdot 21=5\cdot 3\cdot 7$, insgesamt kommen also die gleichen Primfaktoren vor. Weiter unten werden wir zeigen, dass die Primfaktorzerlegung bis auf Reihenfolge eindeutig ist, was keineswegs selbstverständlich ist und einiger Vorbereitungen bedarf.

Der folgende Satz wird Euklid zugeschrieben.

Euklid (4. Jahrhundert v. C.)

Satz

Es gibt unendlich viele Primzahlen.

Beweis

Angenommen,

Bei einem Widerspruchsbeweis geht man folgendermaßen vor: Man möchte eine mathematische Aussage ${}A$ beweisen. Man nimmt dann an, dass ${}A$ nicht wahr ist, dass also die Negation von ${}A$ wahr ist. Dann führt man eine mathematische Argumentation durch, die zu einem Widerspruch führt, typischerweise zu einer Aussage ${}B$, die sowohl gilt als auch nicht gilt. Da dies nicht sein kann, muss die Annahme falsch gewesen sein, und damit ist ${}A$ bewiesen. Da die Argumentation mathematisch korrekt sein muss, bleibt als einzige Erklärung für den Widerspruch die Möglichkeit übrig, dass die Annahme falsch ist.

Typische Beispiele:

Beweis zu Satz 2.3.

Beweis zu Aufgabe 3.11.

Beweis zu Lemma 4.6.

Beweis zu Satz 10.13 (Analysis (Osnabrück 2021-2023)).

 

die Menge aller Primzahlen sei endlich, sagen wir ${}\{p_{1},p_{2},\ldots ,p_{r}\}$ sei eine vollständige Auflistung aller Primzahlen. Man betrachtet die natürliche Zahl

${}N=p_{1}\cdot p_{2}\cdot p_{3}{\cdots }p_{r}+1\,.$

Da bei Division von ${}N$ durch ${}p_{i}$ immer der Rest ${}1$ übrigbleibt ist diese Zahl durch keine der Primzahlen ${}p_{i}$ teilbar. Andererseits besitzt ${}N$ nach Satz 2.2 eine Primfaktorzerlegung. Insbesondere gibt es eine Primzahl ${}p$, die ${}N$ teilt (dabei könnte ${}N=p$ sein). Doch damit muss ${}p$ gleich einem der ${}p_{i}$ aus der Liste sein, und diese sind keine Teiler von ${}N$. Dies ist ein Widerspruch, da ein ${}p_{i}$ nicht gleichzeitig ein Teiler und kein Teiler von ${}N$ sein kann. Also muss die Annahme (nämlich die Endlichkeit der Primzahlmenge) falsch gewesen sein.

$\Box$

Teilerfremdheit

Definition Referenznummer erstellen

Zwei natürliche Zahlen heißen teilerfremd, wenn sie keinen gemeinsamen Teiler ${}\geq 2$ besitzen.

Beispielsweise sind ${}12$ und ${}25$ teilerfremd, ${}15$ und ${}25$ sind nicht teilerfremd, da ${}5$ ein gemeinsamer Teiler ist. Die ${}1$ ist zu jeder natürlichen Zahl (auch zu ${}0$ und ${}1$) teilerfremd. Für eine Primzahl ${}p$ und eine natürliche Zahl ${}n$ gilt folgende Alternative: Entweder teilt ${}p$ die Zahl ${}n$, oder aber ${}p$ und ${}n$ sind teilerfremd. Ein gemeinsamer Teiler muss ja ein Teiler von ${}p$ sein, und da kommen nur ${}1$ und ${}p$ in Frage.

Aufgabe Referenznummer erstellen

Die Wasserspedition „Alles im Eimer“ verfügt über einen ${}7$- und einen ${}10$-Liter-Eimer, die allerdings keine Markierungen haben. Sie erhält den Auftrag, insgesamt genau einen Liter Wasser von der Nordsee in die Ostsee zu transportieren. Kann sie diesen Auftrag erfüllen?

Die Aufgabe ist lösbar: Man macht dreimal den ${}7$-Liter-Eimer in der Nordsee voll und transportiert dies in die Ostsee. Danach (oder gleichzeitig) macht man zweimal den ${}10$-Liter-Eimer in der Ostsee voll und transportiert dies in die Nordsee. Unterm Strich hat man dann

${}3\cdot 7-2\cdot 10=1\,$

Liter transportiert (eine andere Möglichkeit ist ${}5\cdot 10-7\cdot 7=1$). Die dieser Überlegung zugrunde liegende Aussage heißt Lemma von Bezout.

Satz Referenznummer erstellen

Es seien ${}a,b\in \mathbb {N}$ zwei teilerfremde natürliche Zahlen.

Dann gibt es ganze Zahlen ${}r,s\in \mathbb {Z}$ mit ${}ra+sb=1$.

Beweis

Wir beweisen die Aussage durch Induktion über das Maximum von ${}a$ und ${}b$, wobei wir ohne Einschränkung ${}a\leq b$ wählen können. Wenn das Maximum ${}0$ ist, so sind beide Zahlen ${}0$ und somit nicht teilerfremd. Wenn das Maximum ${}1$ ist, so ist ${}b=1$ und somit ergeben ${}r=0$ und ${}s=1$ eine Darstellung der ${}1$. Es seien nun ${}a\leq b$ teilerfremd, ${}b\geq 2$ und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als ${}b$ sind, schon bewiesen. Dann ist ${}a<b$, da bei ${}a=b$ die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ${}a=0$ ausschließen. Wir betrachten das Zahlenpaar ${}(a,b-a)$ und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als ${}b$. Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch ${}a$ und ${}b-a$ teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis.  Nehmen wir also an, dass ${}a$ und ${}b-a$ nicht teilerfremd sind. Dann gibt es eine natürliche Zahl ${}t\geq 2$, die sowohl ${}a$ als auch ${}b-a$ teilt. Dies bedeutet wiederum, dass es natürliche Zahlen ${}m,n$ mit ${}a=mt$ und ${}b-a=nt$ gibt. Doch dann ist

${}b=(b-a)+a=nt+mt=(n+m)t\,$

ebenfalls ein Vielfaches von ${}t$, im Widerspruch zur Teilerfremdheit von ${}a$ und ${}b$.  Die Induktionsvoraussetzung ist also auf ${}a$ und ${}b-a$ anwendbar und somit gibt es ganze Zahlen ${}r,s$ mit

${}ra+s(b-a)=1\,.$

Dann ist aber auch

${}(r-s)a+sb=ra+s(b-a)=1\,$

und wir haben eine Darstellung der ${}1$ mit ${}a$ und ${}b$ gefunden.

$\Box$

Der Hauptsatz der elementaren Zahlentheorie

Wir möchten nun zur Primfaktorzerlegung, deren Existenz wir bereits gezeigt haben, beweisen, dass sie eindeutig ist. Natürlich kann man

${}12=3\cdot 2\cdot 2=2\cdot 3\cdot 2=2\cdot 2\cdot 3\,$

schreiben, mit eindeutig ist also eindeutig bis auf Reihenfolge gemeint. Um dies zu zeigen brauchen wir zunächst das sogenannte Lemma von Euklid, das eine wichtige Eigenschaft einer Primzahl beschreibt.

Satz

Es sei ${}p$ eine Primzahl und ${}p$ teile ein Produkt ${}ab$ von natürlichen Zahlen ${}a,b\in \mathbb {N}$.

Dann teilt ${}p$ einen der Faktoren.

Beweis

Wir setzen voraus, dass ${}a$ kein Vielfaches von ${}p$ ist (andernfalls sind wir fertig).

Dann müssen wir zeigen, dass ${}b$ ein Vielfaches von ${}p$ ist. Unter der gegebenen Voraussetzung

Ein direkter Beweis ist die Hauptform eines Beweises. Aus den Voraussetzungen, die in der zu beweisenden Aussage formuliert sind, werden Zwischeneigenschaften erschlossen, daraus werden, oft unter Verwendung von anderen Sätzen und den schon etablierten Zwischeneigenschaften, weitere Zwischeneigenschaften begründet, bis man schließlich bei der in der zu beweisenden Aussage formulierten Schlussfolgerung ankommt. Die Grundstruktur ist also: Es gilt dieses und jenes. Deshalb gilt auch dieses und jenes. Deshalb gilt dieses und jenes. Deshalb gilt dieses. Es findet keine Aufspaltung der Argumentation (wie bei einer Fallunterscheidung) und keine Richtungsumkehr (wie bei Beweis durch Widerspruch bzw. Kontraposition statt).

Typische Beispiele:

Beweis des Lemma von Euklids.

Beweis zu Lemma 3.5.

Beweis zu Lemma 4.7.

Beweis zu Satz 5.2.

 

sind

${}a$ und ${}p$ teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen ${}r,s$ mit

${}ra+sp=1\,$

Da ${}ab$ ein Vielfaches von ${}p$ ist, gibt es ein ${}t$ mit

${}ab=tp\,.$

Daher ist

${}b=b\cdot 1=b(ra+sp)=abr+bsp=tpr+bsp=p{\left(tr+bs\right)}\,.$

Also ist ${}b$ ein Vielfaches von ${}p$.

$\Box$

Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl ${}p$ ein beliebiges Produkt ${}a_{1}a_{2}{\cdots }a_{n}$ teilt, dann teilt ${}p$ mindestens einen Faktor. Man wendet das Lemma einfach auf ${}(a_{1}a_{2}{\cdots }a_{n-1})\cdot a_{n}$ an (formal ist das eine Induktion über die Anzahl der Faktoren). Dies wird im Beweis des folgenden Hauptsatzes der elementaren Zahlentheorie verwendet.

Satz

Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung

${}n=p_{1}{\cdots }p_{r}\,$

mit Primzahlen ${}p_{i}$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

Beweis

Die Existenz der Primfaktorzerlegung wurde bereits in Satz 2.2 gezeigt. Die Eindeutigkeit wird durch Induktion über ${}n$ gezeigt. Für ${}n=2$ liegt eine Primzahl vor. Sei nun ${}n\geq 3$ und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir

${}n=p_{1}{\cdots }p_{r}=q_{1}{\cdots }q_{s}\,.$

Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl ${}p_{1}$ das Produkt rechts teilt. Nach Satz 2.7 muss dann ${}p_{1}$ einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass ${}q_{1}$ von ${}p_{1}$ geteilt wird. Da ${}q_{1}$ selbst eine Primzahl ist, folgt, dass ${}p_{1}=q_{1}$ sein muss. Daraus ergibt sich durch Kürzen, dass

${}p_{2}{\cdots }p_{r}=q_{2}{\cdots }q_{s}\,$

ist. Nennen wir diese Zahl ${}n'$. Da ${}n'<n$ ist, können wir die Induktionsvoraussetzung auf ${}n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen. 

$\Box$

Primzahlprobleme

Die treibende Kraft der Mathematik ist es, Probleme zu lösen. Schwierige Probleme gibt es in allen Bereichen der Mathematik, besonders prägnant sind sie in der Zahlentheorie, da es dort eine Vielzahl von elementar formulierten ungelösten Problemen gibt. Man spricht von offenen Problemen, oder, wenn man eine bestimmte Erwartung hat, von einer Vermutung. Als Beispiel besprechen wir das Problem der Primzahlzwillinge, zu dem es vor einigen Jahren (2013) einen wichtigen Fortschritt gab.

Definition Referenznummer erstellen

Ein Primzahlzwilling ist ein Paar bestehend aus ${}p$ und ${}p+2$, wobei diese beiden Zahlen Primzahlen sind.

Die ersten Beispiele für Primzahlzwillinge sind

$(3,5),\,(5,7),\,(11,13),\,(17,19),\,(29,31),\ldots .$

Übrigens ist ${}3,5,7$ der einzige Doppel-Primzahlzwilling , siehe Aufgabe 2.31.

Problem

Gibt es unendlich viele Primzahlzwillinge?

Eine Lösung dieses Problems wäre ein mathematischer Satz, der entweder besagt, dass es unendlich viele Primzahlzwillinge gibt, oder dass es nur endlich viele Primzahlzwillinge gibt. D.h. das eine oder das andere müsste bewiesen werden. Bei schwierigen Problemen erwartet man nicht, dass jemand plötzlich einen Beweis hinschreibt, sondern dass eine neue und weit verzweigte Theorie entwickelt wird, mit der man letztlich einen Beweis geben kann.

Bemerkung   Bemerkung 2.11 ändern

Die Frage, ob es unendlich viele Primzahlzwillinge gibt, besitzt verschiedene schwächere Varianten. Man kann sich zum Beispiel fragen, ob es unendlich oft vorkommt, dass es in einem Zehnerintervall zwei Primzahlen gibt, oder dass es in einem Hunderterintervall zwei Primzahlen gibt, und so weiter. Die ersten Primzahlen vermitteln dabei ein Bild, dass Primzahlen ziemlich häufig sind. Sie werden aber zunehmend seltener, sodass es für hohe Hunderterintervalle, sagen wir für die Zahlen von

$1000000000000000\,\,{\text{ bis }}\,\,1000000000000100$

ziemlich unwahrscheinlich ist, eine Primzahl zu enthalten, geschweige denn zwei Primzahlen. Bis vor kurzem war es nicht bekannt, ob es überhaupt eine Zahl ${}m$ mit der Eigenschaft gibt, dass es unendlich viele Intervalle der Länge ${}m$ gibt, die zwei Primzahlen enthalten ($m=2$ wäre die positive Lösung des Primzahlzwillingsproblems). Im Jahr 2013 bewies Zhang Yitang, dass man ${}m=70000000$

nehmen kann, dass es also unendlich viele Intervalle der Form

$[k,k+70000000]$

gibt, in denen zwei Primzahlen liegen. Dieses Resultat ist ein Durchbruch in der Primzahlzwillingforschung, da es erstmals zeigt, dass sich Primzahlen unendlich oft „ziemlich nahe“ kommen. Zwischenzeitlich wurde die Schranke von ${}70000000$ auf ${}252$ gesenkt, siehe [1].

<< | Kurs:Vorkurs Mathematik (Osnabrück 2021) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)