Kurs:Vorkurs Mathematik (Osnabrück 2013)/Vorlesung 2/latex
\setcounter{section}{2}
\zwischenueberschrift{Primzahlen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {New Animation Sieve of Eratosthenes.gif} }
\end{center}
\bildtext {Das \stichwort {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
\zusatzklammer {kleiner als oder gleich $\sqrt{k}$} {} {}
schon etablierten Primzahlen durch, die verbleibenden Zahlen sind prim.} }
\bildlizenz { New Animation Sieve of Eratosthenes.gif } {} {M.qrius} {Commons} {CC-by-sa 3.0} {}
\inputdefinition
{}
{
Eine
\definitionsverweis {natürliche Zahl}{}{}
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt eine \definitionswort {Primzahl}{,} wenn die einzigen natürlichen
\definitionsverweis {Teiler}{}{}
von ihr $1$ und $n$ sind.
}
Eine Primzahl ist also eine natürliche Zahl, die genau zwei Teiler hat, nämlich \mathkor {} {1} {und} {n} {,} und die müssen verschieden sein. $1$ ist also keine Primzahl.
Die ersten Primzahlen sind
\mathl{2,3,5,7,11,13,17,19,23,29,31, { \ldots }}{.}
\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/Existenz/Fakt}
{Satz}
{}
{
Jede
\definitionsverweis {natürliche Zahl}{}{}
\mathbed {n \in \N} {}
{n \geq 2} {}
{} {} {} {,}
besitzt eine Zerlegung in Primfaktoren.
D.h. es gibt eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {p_1 \cdot p_2 { \cdots } p_r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\definitionsverweis {Primzahlen}{}{}
$p_i$.
}
{
Wir beweisen die Existenz durch Induktion über $n$.
Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt eine Primzahl vor Bei
\mavergleichskette
{\vergleichskette
{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
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ ab
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit kleineren Zahlen
\mavergleichskette
{\vergleichskette
{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
Für
\mathl{105}{} beispielsweise findet man den Primfaktor $3$ und kann daher
\mavergleichskette
{\vergleichskette
{105
}
{ = }{3 \cdot 35
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
schreiben. Von der kleineren Zahl $35$ ist die Zerlegung
\mavergleichskette
{\vergleichskette
{35
}
{ = }{5 \cdot 7
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nach Induktionsvoraussetzung schon bekannt und man erhält
\mavergleichskettedisp
{\vergleichskette
{105
}
{ =} {3 \cdot 5 \cdot 7
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wenn man mit dem Primfaktor $5$ startet, so ergibt sich
\mavergleichskette
{\vergleichskette
{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 einige Vorbereitungen bedarf.
\inputfaktbeweis
{Primzahlen/Unendlich viele/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktfolgerung {Es gibt unendlich viele Primzahlen.}
\faktzusatz {}
\faktzusatz {}
}
{
AngenommenDies ist ein Widerspruch, da ein $p_i$ nicht gleichzeitig ein Teiler und kein Teiler von $N$ sein kann. Also muss die Annahme
\zusatzklammer {nämlich die Endlichkeit der Primzahlmenge} {} {}
falsch gewesen sein. die Menge aller Primzahlen sei endlich, sagen wir
\mathl{\{p_1, p_2 , \ldots , p_r \}}{} sei eine vollständige Auflistung aller Primzahlen. Man betrachtet die natürliche Zahl
\mavergleichskettedisp
{\vergleichskette
{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
\zusatzklammer {dabei könnte
\mavergleichskettek
{\vergleichskettek
{N
}
{ = }{p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein} {} {.}
Doch damit muss $p$ gleich einem der $p_i$ aus der Liste sein, und diese sind keine Teiler von $N$.
\zwischenueberschrift{Teilerfremdheit}
\inputdefinition
{}
{
Zwei natürliche Zahlen heißen \definitionswort {teilerfremd}{,} wenn sie keinen gemeinsamen
\definitionsverweis {Teiler}{}{}
\mathl{\geq 2}{} besitzen.
}
Beispielsweise sind \mathkor {} {12} {und} {25} {} teilerfremd, \mathkor {} {15} {und} {25} {} sind nicht teilerfremd, da $5$ ein gemeinsamer Teiler ist. Die $1$ ist zu jeder natürlichen Zahl \zusatzklammer {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 \mathkor {} {p} {und} {n} {} sind teilerfremd. Ein gemeinsamer Teiler muss ja ein Teiler von $p$ sein, und da kommen nur \mathkor {} {1} {und} {p} {} in Frage.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Kielcanal.PNG} }
\end{center}
\bildtext {} }
\bildlizenz { Kielcanal.PNG } {} {Grunners} {Commons} {PD} {}
\inputaufgabe
{}
{
Die Wasserspedition \anfuehrung{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 fünfmal den $10$-Liter-Eimer in der Nordsee voll und transportiert dies in die Ostsee. Danach
\zusatzklammer {oder gleichzeitig} {} {}
macht man siebenmal den $7$-Liter-Eimer in der Ostsee voll und transportiert dies in die Nordsee. Unterm Strich hat man dann
\mavergleichskette
{\vergleichskette
{5 \cdot 10 - 7 \cdot 7
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Liter transportiert. Die dieser Überlegung zugrunde liegende Aussage heißt \stichwort {Lemma von Bezout} {.}
\inputfaktbeweis
{Lemma von Bezout/N/Teilerfremd/Induktion/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Es seien
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zwei
\definitionsverweis {teilerfremde}{}{}
natürliche Zahlen.}
\faktfolgerung {Dann gibt es ganze Zahlen
\mavergleichskette
{\vergleichskette
{r,s
}
{ \in }{\Z
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ ra+sb
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir beweisen die Aussage durch Induktion über das Maximum von
\mathkor {} {a} {und} {b} {,}
wobei wir ohne Einschränkung
\mavergleichskette
{\vergleichskette
{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
\mavergleichskette
{\vergleichskette
{b
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ergeben
\mavergleichskette
{\vergleichskette
{r
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{s
}
{ = }{1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Darstellung der $1$. Es seien nun
\mavergleichskette
{\vergleichskette
{a
}
{ \leq }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
teilerfremd,
\mavergleichskette
{\vergleichskette
{b
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als $b$ sind, schon bewiesen. Dann ist
\mavergleichskette
{\vergleichskette
{a
}
{ < }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
da bei
\mavergleichskette
{\vergleichskette
{a
}
{ = }{b
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die beiden Zahlen nicht teilerfremd sind. Ebenso können wir
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ausschließen. Wir betrachten das Zahlenpaar
\mathl{(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
\mathkor {} {a} {und} {b-a} {}
teilerfemd sind.
Dazu führen wir einen Widerspruchsbeweis. Nehmen wir also an, dass
\mathkor {} {a} {und} {b-a} {}
nicht teilerfremd sind. Dann gibt es eine natürliche Zahl
\mavergleichskette
{\vergleichskette
{t
}
{ \geq }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die sowohl
\mathkor {} {a} {als auch} {b-a} {}
teilt. Dies bedeutet wiederum, dass es natürliche Zahlen
\mathl{m,n}{} mit
\mathkor {} {a=mt} {und} {b-a =nt} {}
gibt. Doch dann ist
\mavergleichskettedisp
{\vergleichskette
{b
}
{ =} {(b-a)+a
}
{ =} { nt +mt
}
{ =} { (n+m)t
}
{ } {
}
}
{}{}{}
ebenfalls ein Vielfaches von $t$, im Widerspruch zur Teilerfremdheit von
\mathkor {} {a} {und} {b} {.}
Die Induktionsvoraussetzung ist also auf
\mathkor {} {a} {und} {b-a} {}
anwendbar und somit gibt es ganze Zahlen
\mathl{r,s}{} mit
\mavergleichskettedisp
{\vergleichskette
{ra+s(b-a)
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann ist aber auch
\mavergleichskettedisp
{\vergleichskette
{ (r-s)a +sb
}
{ =} { ra +s(b-a)
}
{ =} {1
}
{ } {
}
{ } {
}
}
{}{}{}
und wir haben eine Darstellung der $1$ mit
\mathkor {} {a} {und} {b} {}
gefunden.
\zwischenueberschrift{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
\mavergleichskettedisp
{\vergleichskette
{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 \stichwort {Lemma von Euklid} {,} das eine wichtige Eigenschaft einer Primzahl beschreibt.
\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Primzahl erfüllt Primelementeigenschaft/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $p$ eine
\definitionsverweis {Primzahl}{}{}
und}
\faktvoraussetzung {$p$ teile ein Produkt $ab$ von natürlichen Zahlen
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann teilt $p$ einen der Faktoren.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir setzen voraus, dass $a$ kein Vielfaches von $p$ ist
\zusatzklammer {andernfalls sind wir fertig} {} {.}
Dann müssen wir zeigen, dass $b$ ein Vielfaches von $p$ ist. Unter der gegebenen Voraussetzung sind
\mathkor {} {a} {und} {p} {}
\definitionsverweis {teilerfremd}{}{.}
Nach
dem Lemma von Bezout
gibt es ganze Zahlen
\mathl{r,s}{} mit
\mavergleichskettedisp
{\vergleichskette
{ ra +sp
}
{ =} {1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Da
\mathl{ab}{} ein Vielfaches von $p$ ist, gibt es ein $t$ mit
\mavergleichskettedisp
{\vergleichskette
{ab
}
{ =} {tp
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Daher ist
\mavergleichskettedisp
{\vergleichskette
{ b
}
{ =} { b \cdot 1
}
{ =} { b (ra +sp)
}
{ =} { ab r + bs p
}
{ =} { t p r +bsp
}
}
{
\vergleichskettefortsetzung
{ =} { p { \left( tr +bs \right) }
}
{ } {}
{ } {}
{ } {}
}{}{.}
Also ist $b$ ein Vielfaches von $p$.
Aus dem Lemma von Euklid folgt sofort die etwas stärkere Aussage: Wenn eine Primzahl $p$ ein beliebiges Produkt
\mathl{a_1 a_2 { \cdots } a_n}{} teilt, dann teilt $p$ mindestens einen Faktor. Man wendet das Lemma einfach auf
\mathl{(a_1 a_2 { \cdots } a_{n-1}) \cdot a_n}{} an
\zusatzklammer {formal ist das eine Induktion über die Anzahl der Faktoren} {} {.}
Dies wird im Beweis des folgenden \stichwort {Hauptsatzes der elementaren Zahlentheorie} {} verwendet.
\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/Fakt}
{Satz}
{}
{
Jede natürliche Zahl
\mathbed {n\in \N} {}
{n \geq 2} {}
{} {} {} {,}
besitzt eine eindeutige Zerlegung in Primfaktoren.
D.h. es gibt eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {p_1 { \cdots } p_r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\definitionsverweis {Primzahlen}{}{}
$p_i$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.
}
{
Die Existenz der Primfaktorzerlegung wurde bereits in
Satz 2.2
gezeigt.
Die Eindeutigkeit wird durch Induktion über $n$ gezeigt. Für
\mavergleichskette
{\vergleichskette
{n
}
{ = }{2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt eine Primzahl vor. Sei nun
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir
\mavergleichskettedisp
{\vergleichskette
{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.6
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
\mavergleichskette
{\vergleichskette
{p_1
}
{ = }{q_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein muss. Daraus ergibt sich durch Kürzen, dass
\mavergleichskettedisp
{\vergleichskette
{ p_2 { \cdots } p_r
}
{ =} {q_2 { \cdots } q_s
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist. Nennen wir diese Zahl $n'$. Da
\mavergleichskette
{\vergleichskette
{n'
}
{ < }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, können wir die Induktionsvoraussetzung auf $n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen.
\zwischenueberschrift{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 \stichwort {offenen Problemen} {,} oder, wenn man eine bestimmte Erwartung hat, von einer \stichwort {Vermutung} {.} Als Beispiel besprechen wir das Problem der Primzahlzwillinge, zu dem es vor einigen Jahren \zusatzklammer {2013} {} {} einen wichtigen Fortschritt gab.
\inputdefinition
{}
{
Ein \definitionswort {Primzahlzwilling}{} ist ein Paar bestehend aus \mathkor {} {p} {und} {p+2} {,} wobei diese beiden Zahlen \definitionsverweis {Primzahlen}{}{} sind.
}
Die ersten Beispiele für Primzahlzwillinge sind
\mathdisp {(3,5),\, (5,7), \,(11,13),\,(17,19),\,(29,31), \ldots} { . }
Übrigens ist
\mathl{3,5,7}{} der einzige Doppel-Primzahlzwilling
,
siehe
Aufgabe 1.12.
\inputproblem{}
{
Gibt es unendlich viele \definitionsverweis {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.
\inputbemerkung
{}
{
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, so dass es für hohe Hunderterintervalle, sagen wir für die Zahlen von
\mathdisp {1 000 000 000 000 000 \text{ bis } 1 000 000 000 000 100} { }
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
\zusatzklammer {\mathlk{m=2}{} wäre die positive Lösung des Primzahlzwillingsproblems} {} {.}
Im Jahr 2013 bewies Zhang Yitang, dass man
\mavergleichskette
{\vergleichskette
{m
}
{ = }{70 000 000
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nehmen kann, dass es also unendlich viele Intervalle der Form
\mathdisp {[k,k+70 000 000]} { }
gibt, in denen zwei Primzahlen liegen. Dieses Resultat ist ein Durchbruch in der Primzahlzwillingforschung, da es erstmals zeigt, dass sich Primzahlen unendlich oft \anfuehrung{ziemlich nahe}{} kommen. Zwischenzeitlich wurde die Schranke von
\mathl{70 000 000}{} auf
\mathl{252}{} gesenkt, siehe http://arxiv.org/pdf/1402.4849v2.pdf.
}
| << | Kurs:Vorkurs Mathematik (Osnabrück 2013) | >> |
|---|