Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 13/latex

Aus Wikiversity
Zur Navigation springen Zur Suche springen

\setcounter{section}{13}






\zwischenueberschrift{Mersenne-Primzahlen}






\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Marin_Mersenne.eps} }
\end{center}
\bildtext {Marin Mersenne (1588-1648)} }

\bildlizenz { Marin Mersenne.jpeg } {} {Maksim} {Commons} {PD} {http://www-history.mcs.st-and.ac.uk/history/PictDisplay/Mersenne.html}





\inputdefinition
{}
{

Eine \definitionsverweis {Primzahl}{}{} der Form
\mathl{2^n-1}{} heißt \definitionswort {Mersennesche Primzahl}{.}

}

Generell nennt man die Zahl
\mathl{M_n = 2^n-1}{} die $n$-te \stichwort {Mersenne-Zahl} {.} Mit dieser Bezeichnung sind die Mersenne-Primzahlen genau diejenigen Mersenne-Zahlen, die Primzahlen sind. Eine Mersenne-Zahl besitzt im Zweiersystem die Ziffernentwicklung
\mathl{11111 \ldots 1111}{.} Das ist auch die Anzahl der Spiele in einem im K.-o.-System ausgetragenen Pokalwettbewerb mit $2^n$ Mannschaften.





\inputfaktbeweis
{Primzahlen/Mersennesche_Primzahlen/Exponent ist prim/Fakt}
{Lemma}
{}
{

Ist
\mathl{2^n-1}{} eine \definitionsverweis {Primzahl}{}{,} so ist auch $n$ eine Primzahl.

}
{

Sei eine Darstellung
\mathl{n=ab}{} mit natürlichen Zahlen $a,b$ gegeben. Wir setzen in der polynomialen Identität
\mavergleichskettedisp
{\vergleichskette
{ X^k-1 }
{ =} {(X-1)(X^{k-1}+X^{k-2} + \cdots + X +1) }
{ } { }
{ } { }
{ } { }
} {}{}{}
\mathl{X=2^a}{} und
\mathl{k=b}{} ein und erhalten, dass
\mathl{2^a-1 {{|}} 2^n-1}{.} Da
\mathl{2^n-1}{} als prim vorausgesetzt wurde, folgt
\mathl{2^a-1=1}{} oder
\mathl{2^a-1=2^n-1}{,} also $a=1$ oder
\mathl{a=n}{.}

}







\inputbemerkung
{}
{

Die Mersenne-Zahl
\mavergleichskette
{\vergleichskette
{ M_n }
{ = }{ 2^n -1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} hat im Dualsystem eine Entwicklung, die aus genau $n$ Einsen besteht. Die ersten Mersenne-Primzahlen sind
\mathdisp {2^2-1=3, 2^3-1=7, 2^5-1= 31, 2^7-1 = 127} { . }
Die Zahl
\mathl{2^{11}-1=2047= 23 \cdot 89}{} ist die erste Mersenne-Zahl, wo der Exponent zwar prim ist, die aber selbst keine Mersenne-Primzahl ist. Dies wurde 1536 von Hudalrichus Regius \zusatzklammer {Walter Hermann Ryff} {} {} gezeigt. Der nächste Kandidat, nämlich
\mathl{2^{13}-1=8191}{,} ist wieder prim. Bis ca. 1950 war bekannt, dass für die Exponenten
\mathdisp {2,3,5,7,13,17,19,31,61,89,107 \text{ und } 127} { }
Mersenne-Primzahlen vorliegen, und keine weiteren unterhalb des Exponenten
\mathl{258}{.} Von verschiedenen Leuten, unter anderem von Cataldi und Mersenne selbst, wurden falsche Behauptungen aufgestellt. Ab ca. 1950 kamen Computer zum Bestimmen von Mersenne-Primzahlen zum Einsatz, und es wurden bisher insgesamt $49$ Mersenne-Primzahlen gefunden. Die größte ist
\mathdisp {2^{74 207 281}-1} { . }
Es ist unbekannt, ob es unendlich viele Mersenne-Primzahlen gibt.

Alle größten bekannten Primzahlen sind Mersenne-Zahlen. Das liegt daran, dass es für diese Zahlen einen vergleichsweise einfachen Primzahltest gibt, nämlich den \stichwort {Lucas-Lehmer-Test} {.} Mit diesem Test wird etwa alle zwei Jahre eine neue größte Primzahl gefunden. Für eine Rekordliste siehe \definitionsverweis {Mersenne-Primzahlen}{}{.}

}

Mersenne-Zahlen stehen in direktem Verhältnis zu den vollkommenen Zahlen.






\zwischenueberschrift{Vollkommene Zahlen}




\inputdefinition
{}
{

Eine natürliche Zahl $n$ heißt \definitionswort {vollkommen}{,} wenn sie mit der Summe all ihrer von $n$ verschiedenen Teiler übereinstimmt.

}

Bereits Euklid stellte fest, dass die ersten vier vollkommenen Zahlen sich als
\mathdisp {2^{k-1}(2^k-1)} { }
darstellen lassen: \auflistungvier{Für
\mathl{k=2}{:}
\mathl{2^1(2^2-1) = 6 = 1+ 2 + 3}{} }{Für
\mathl{k=3}{:}
\mathl{2^2(2^3-1) = 28 = 1+ 2+ 4+ 7+ 14}{} }{Für
\mathl{k=5}{:}
\mathl{2^4(2^5-1) = 496 = 1+ 2+ 4+ 8+ 16+ 31+ 62+ 124+ 248}{} }{Für
\mathl{k=7}{:}
\mathl{2^6(2^7-1) = 8128 = 1+ 2+ 4+ 8+ 16+ 32+ 64+ 127+ 254+ 508+ 1016+ 2032+ 4064}{.} }

Euklid bewies, dass
\mathl{2^{k-1}(2^k-1)}{} immer dann eine vollkommene Zahl ist, wenn
\mathl{2^k-1}{} eine Primzahl, also eine Mersenne-Primzahl ist. Euler bewies, dass auf diese Weise alle geraden vollkommenen Zahlen erzeugt werden können. Bevor wir diesen Satz von Euklid-Euler beweisen, brauchen wir eine kleine Vorüberlegung.




\inputdefinition
{}
{

Zu einer natürlichen Zahl $n$ bezeichnet man die Summe aller natürlichen Teiler von $n$ als $\sigma(n)$, also
\mavergleichskettedisp
{\vergleichskette
{ \sigma(n) }
{ =} { \sum_{t {{|}} n} t }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}

Eine vollkommene Zahl kann man also dadurch charakterisieren, dass
\mathl{\sigma(n)=2n}{} ist.





\inputfaktbeweis
{Zahlentheoretische Funktionen/Teilersumme/Multiplikativität/Fakt}
{Lemma}
{}
{

Zu zwei natürlichen teilerfremden Zahlen $n$ und $m$ gilt
\mavergleichskettedisp
{\vergleichskette
{ \sigma(n m) }
{ =} {\sigma(n) \sigma(m) }
{ } { }
{ } { }
{ } { }
} {}{}{.}

}
{

Bei zwei teilerfremden Zahlen $n$ und $m$ hat jeder positive Teiler $t$ des Produkts $nm$ die eindeutige Form
\mavergleichskette
{\vergleichskette
{t }
{ = }{ab }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} wobei $a$ ein Teiler von $n$ und $b$ ein Teiler von $m$ ist. Also gilt
\mavergleichskettedisp
{\vergleichskette
{ \sigma(n m) }
{ =} {\sum_{t {{|}} mn} t }
{ =} { \sum_{a {{|}} m \mbox{ und } b {{|}} n} ab }
{ =} { { \left( \sum_{a {{|}} n } a \right) } { \left( \sum_{b {{|}} m } b \right) } }
{ =} { \sigma(n) \sigma(m) }
} {}{}{.}

}


Damit können wir beweisen.





\inputfaktbeweis
{Vollkommene Zahlen/Gerade/Charakterisierung mit Mersenne-Primzahlen/Fakt}
{Satz}
{}
{

Eine gerade Zahl $n$ ist genau dann vollkommen, wenn
\mavergleichskette
{\vergleichskette
{n }
{ = }{ 2^{k-1}(2^k-1) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ist mit
\mathl{2^k-1}{} prim.

}
{

Sei zunächst
\mavergleichskette
{\vergleichskette
{n }
{ = }{ 2^{k-1} { \left( 2^k-1 \right) } }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mathl{2^k-1}{} prim. Dann sind die von $n$ verschiedenen Teiler von $n$ durch
\mathdisp {2^{i},\, i=0 , \ldots , k-1, \text{ und } 2^{i} (2^k-1) ,\, i=0 , \ldots , k-2} { }
gegeben. Daher ist ihre Summe gleich
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ \sum_{i = 0}^{k-1} 2^{i} + (2^k-1) \sum_{i = 0}^{k-2} 2^{i} }
{ =} {2^k-1 + { \left( 2^k-1 \right) } { \left( 2^{k-1} -1 \right) } }
{ =} { { \left( 2^k-1 \right) } 2^{k-1} }
{ =} {n }
{ } { }
} {}{}{,} also ist $n$ vollkommen. Sei umgekehrt $n$ vollkommen. Wir setzen \zusatzklammer {in Anlehnung an das Ziel} {} {} an
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {2^{k-1} u }
{ } { }
{ } { }
{ } { }
} {}{}{} mit $u$ ungerade und
\mathl{k \geq 2}{,} da ja $n$ gerade ist. Für teilerfremde Zahlen ist nach Lemma 13.6 die Teilersumme gleich dem Produkt der beiden Teilersummen. Daher ist einerseits
\mavergleichskettedisp
{\vergleichskette
{ \sigma(n) }
{ =} { \sigma { \left( 2^{k-1} u \right) } }
{ =} { \sigma { \left( 2^{k-1} \right) } \sigma(u) }
{ =} { { \left( 2^k-1 \right) } \sigma(u) }
{ } { }
} {}{}{} und andererseits wegen der Vollkommenheit
\mavergleichskette
{\vergleichskette
{\sigma (n) }
{ = }{2n }
{ = }{2^{k} u }
{ }{ }
{ }{ }
} {}{}{.} Insgesamt ergibt sich also
\mavergleichskette
{\vergleichskette
{ { \left( 2^k-1 \right) } \sigma(u) }
{ = }{ 2^{k} u }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Da
\mathl{2^k-1}{} ungerade ist, gilt
\mathdisp {\sigma(u) =x 2^{k} \text{ und } u = x(2^k-1)} { . }
Die Annahme
\mathl{x >1}{} führt schnell zum Widerspruch, da es dann zumindest die drei verschiedenen Teiler
\mathl{1,x,x(2^k -1)}{} von $u$ gibt, was zu
\mavergleichskettedisp
{\vergleichskette
{ \sigma(u) }
{ \geq} { { \left( 2^k-1 \right) } x+1+x }
{ >} {2^k x }
{ } { }
{ } { }
} {}{}{} führt. Also ist
\mavergleichskette
{\vergleichskette
{x }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und somit
\mavergleichskette
{\vergleichskette
{ \sigma(u) }
{ = }{2^k }
{ = }{u+1 }
{ }{ }
{ }{ }
} {}{}{.} Die Teilersumme einer Zahl $u$ ist aber gleich
\mathl{u+1}{} nur dann, wenn eine Primzahl vorliegt.

}


Es ist unbekannt, ob es unendlich viele vollkommene Zahlen gibt, da es ja auch unbekannt ist, ob es unendlich viele Mersenne-Primzahlen gibt. Es ist unbekannt, ob es überhaupt auch ungerade vollkommene Zahlen gibt.






\zwischenueberschrift{Befreundete Zahlen}




\inputdefinition
{}
{

Zwei verschiedene natürliche Zahlen $m$ und $n$ heißen \definitionswort {befreundet}{,} wenn $m$ gleich der Summe der echten Teiler von $n$ ist und umgekehrt.

}

Das klassische Beispiel für ein befreundetes Zahlenpaar ist
\mathl{220}{} und
\mathl{284}{.} Die Summe der echten Teiler von
\mathl{220}{} ist
\mavergleichskettedisp
{\vergleichskette
{1+2+4+5+10+11+20+22+44+55+110 }
{ =} {284 }
{ } { }
{ } { }
{ } { }
} {}{}{} und die Summe der echten Teiler von
\mathl{284}{} ist
\mavergleichskettedisp
{\vergleichskette
{1+2+4+71+142 }
{ =} {220 }
{ } { }
{ } { }
{ } { }
} {}{}{.}

Zwei verschiedene Zahlen sind genau dann befreundet, wenn
\mavergleichskettedisp
{\vergleichskette
{ \sigma(m) }
{ =} {m+n }
{ =} { \sigma(n) }
{ } { }
{ } { }
} {}{}{} ist. Der folgende Satz erlaubt es, einige weitere befreundete Zahlenpaare zu finden, aber keineswegs alle. Man spricht von der \stichwort {Regel von Thabit} {.}





\inputfaktbeweis
{Befreundete Zahlen/Regel von Thabit/Fakt}
{Satz}
{}
{

Sei
\mathl{k \geq 2}{} eine natürliche Zahl und seien
\mathl{a = 3 \cdot 2^{k-1} -1}{,}
\mathl{b= 3 \cdot 2^k -1}{} und
\mathl{c =9 \cdot 2^{2k-1} -1}{} allesamt \definitionsverweis {Primzahlen}{}{.} Dann sind
\mathdisp {m =2^k ab \text{ und } n =2^k c} { }

\definitionsverweis {befreundet}{}{.}

}
{

Wir berechnen
\mathl{\sigma(m)}{,}
\mathl{\sigma(n)}{} und
\mathl{m+n}{.} Es ist
\mavergleichskettealign
{\vergleichskettealign
{ \sigma(m) }
{ =} { \sigma (2^k ab) }
{ =} {\sigma (2^k) \sigma( a) \sigma(b) }
{ =} { { \left( 2^{k+1}-1 \right) } { \left( 3 \cdot 2^{k-1} \right) } { \left( 3\cdot 2^k \right) } }
{ =} { { \left( 2^{k+1}-1 \right) } \cdot 9 \cdot 2^{2k-1} }
} {} {}{.} Weiter ist
\mavergleichskettealign
{\vergleichskettealign
{ \sigma(n) }
{ =} { \sigma (2^k c) }
{ =} { \sigma (2^k) \sigma(c) }
{ =} { (2^{k+1}-1) (1+c) }
{ =} { (2^{k+1}-1) \cdot 9 \cdot 2^{2k-1} }
} {} {}{.} Schließlich ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{m+n }
{ =} { 2^k (ab+c) }
{ =} { 2^k { \left( { \left( 3 \cdot 2^{k-1}-1 \right) } { \left( 3 \cdot 2^k-1\right) } + 9 \cdot 2^{2k-1}-1 \right) } }
{ =} { 2^k { \left( 9 \cdot 2^{2k-1}-3 \cdot 2^{k-1} -3 \cdot 2^{k} + 9 \cdot 2^{2k-1} \right) } }
{ =} { 2^k { \left( 9 \cdot 2^{2k}- 9 \cdot 2^{k-1} \right) } }
} {
\vergleichskettefortsetzungalign
{ =} { 2^k 2^{k-1} \cdot 9 { \left( 2^{k+1}-1 \right) } }
{ } {}
{ } {}
{ } {}
}{}{.}

}


%Daten für folgende Tabelle


\renewcommand{\leitzeilenull}{ }

\renewcommand{\leitzeileeins}{ $a = 3 \cdot 2^{k-1} -1$ }

\renewcommand{\leitzeilezwei}{
\mathl{b= 3 \cdot 2^k -1}{} }

\renewcommand{\leitzeiledrei}{
\mathl{c =9 \cdot 2^{2k-1} -1}{} }

\renewcommand{\leitzeilevier}{
\mathl{m =2^k ab}{} }

\renewcommand{\leitzeilefuenf}{
\mathl{n =2^k c}{} }

\renewcommand{\leitzeilesechs}{ }

\renewcommand{\leitzeilesieben}{ }

\renewcommand{\leitzeileacht}{ }

\renewcommand{\leitzeileneun}{ }

\renewcommand{\leitzeilezehn}{ }

\renewcommand{\leitzeileelf}{ }

\renewcommand{\leitzeilezwoelf}{ }


\renewcommand{\leitspaltenull}{ $k$ }

\renewcommand{\leitspalteeins}{ $2$ }

\renewcommand{\leitspaltezwei}{ $3$ }

\renewcommand{\leitspaltedrei}{ $4$ }

\renewcommand{\leitspaltevier}{ $5$ }

\renewcommand{\leitspaltefuenf}{ $6$ }

\renewcommand{\leitspaltesechs}{ $7$ }

\renewcommand{\leitspaltesieben}{ }

\renewcommand{\leitspalteacht}{ }

\renewcommand{\leitspalteneun}{ }

\renewcommand{\leitspaltezehn}{ }

\renewcommand{\leitspalteelf}{ }

\renewcommand{\leitspaltezwoelf}{ }

\renewcommand{\leitspaltedreizehn}{ }

\renewcommand{\leitspaltevierzehn}{ }

\renewcommand{\leitspaltefuenfzehn}{ }

\renewcommand{\leitspaltesechzehn}{ }

\renewcommand{\leitspaltesiebzehn}{ }

\renewcommand{\leitspalteachtzehn}{ }

\renewcommand{\leitspalteneunzehn}{ }

\renewcommand{\leitspaltezwanzig}{ }



\renewcommand{\aeinsxeins}{ 5 }

\renewcommand{\aeinsxzwei}{ 11 }

\renewcommand{\aeinsxdrei}{ 71 }

\renewcommand{\aeinsxvier}{ 220 }

\renewcommand{\aeinsxfuenf}{ 284 }

\renewcommand{\aeinsxsechs}{ }

\renewcommand{\aeinsxsieben}{ }

\renewcommand{\aeinsxacht}{ }

\renewcommand{\aeinsxneun}{ }

\renewcommand{\aeinsxzehn}{ }

\renewcommand{\aeinsxelf}{ }

\renewcommand{\aeinsxzwoelf}{ }



\renewcommand{\azweixeins}{ 11 }

\renewcommand{\azweixzwei}{ 23 }

\renewcommand{\azweixdrei}{ 287 = 7 \cdot 41 \text{ (nicht prim)} }

\renewcommand{\azweixvier}{ \, }

\renewcommand{\azweixfuenf}{ \, }

\renewcommand{\azweixsechs}{ }

\renewcommand{\azweixsieben}{ }

\renewcommand{\azweixacht}{ }

\renewcommand{\azweixneun}{ }

\renewcommand{\azweixzehn}{ }

\renewcommand{\azweixelf}{ }

\renewcommand{\azweixzwoelf}{ }



\renewcommand{\adreixeins}{ 23 }

\renewcommand{\adreixzwei}{ 47 }

\renewcommand{\adreixdrei}{ 1151 }

\renewcommand{\adreixvier}{ 17296 }

\renewcommand{\adreixfuenf}{ 18416 }

\renewcommand{\adreixsechs}{ }

\renewcommand{\adreixsieben}{ }

\renewcommand{\adreixacht}{ }

\renewcommand{\adreixneun}{ }

\renewcommand{\adreixzehn}{ }

\renewcommand{\adreixelf}{ }

\renewcommand{\adreixzwoelf}{ }



\renewcommand{\avierxeins}{ 47 }

\renewcommand{\avierxzwei}{ 95 }

\renewcommand{\avierxdrei}{ 4607 = 17 \cdot 271 \text{ (nicht prim)} }

\renewcommand{\avierxvier}{ \, }

\renewcommand{\avierxfuenf}{ \, }

\renewcommand{\avierxsechs}{ }

\renewcommand{\avierxsieben}{ }

\renewcommand{\avierxacht}{ }

\renewcommand{\avierxneun}{ }

\renewcommand{\avierxzehn}{ }

\renewcommand{\avierxelf}{ }

\renewcommand{\avierxzwoelf}{ }


\renewcommand{\afuenfxeins}{ 95=5 \cdot 19 \text{ (nicht prim)} }

\renewcommand{\afuenfxzwei}{ 191 }

\renewcommand{\afuenfxdrei}{ 18431 = 7 \cdot 2633 \text{ (nicht prim)} }

\renewcommand{\afuenfxvier}{ \, }

\renewcommand{\afuenfxfuenf}{ \, }

\renewcommand{\afuenfxsechs}{ }

\renewcommand{\afuenfxsieben}{ }

\renewcommand{\afuenfxacht}{ }

\renewcommand{\afuenfxneun}{ }

\renewcommand{\afuenfxzehn}{ }

\renewcommand{\afuenfxelf}{ }

\renewcommand{\afuenfxzwoelf}{ }


\renewcommand{\asechsxeins}{ 191 }

\renewcommand{\asechsxzwei}{ 383 }

\renewcommand{\asechsxdrei}{ 73727 }

\renewcommand{\asechsxvier}{ 9363584 }

\renewcommand{\asechsxfuenf}{ 9437056 }

\renewcommand{\asechsxsechs}{ }

\renewcommand{\asechsxsieben}{ }

\renewcommand{\asechsxacht}{ }

\renewcommand{\asechsxneun}{ }

\renewcommand{\asechsxzehn}{ }

\renewcommand{\asechsxelf}{ }

\renewcommand{\asechsxzwoelf}{ }


\renewcommand{\asiebenxeins}{ }

\renewcommand{\asiebenxzwei}{ }

\renewcommand{\asiebenxdrei}{ }

\renewcommand{\asiebenxvier}{ }

\renewcommand{\asiebenxfuenf}{ }

\renewcommand{\asiebenxsechs}{ }

\renewcommand{\asiebenxsieben}{ }

\renewcommand{\asiebenxacht}{ }

\renewcommand{\asiebenxneun}{ }

\renewcommand{\asiebenxzehn}{ }

\renewcommand{\asiebenxelf}{ }

\renewcommand{\asiebenxzwoelf}{ }


\renewcommand{\aachtxeins}{ }

\renewcommand{\aachtxzwei}{ }

\renewcommand{\aachtxdrei}{ }

\renewcommand{\aachtxvier}{ }

\renewcommand{\aachtxfuenf}{ }

\renewcommand{\aachtxsechs}{ }

\renewcommand{\aachtxsieben}{ }

\renewcommand{\aachtxacht}{ }

\renewcommand{\aachtxneun}{ }

\renewcommand{\aachtxzehn}{ }

\renewcommand{\aachtxelf}{ }

\renewcommand{\aachtxzwoelf}{ }


\renewcommand{\aneunxeins}{ }

\renewcommand{\aneunxzwei}{ }

\renewcommand{\aneunxdrei}{ }

\renewcommand{\aneunxvier}{ }

\renewcommand{\aneunxfuenf}{ }

\renewcommand{\aneunxsechs}{ }

\renewcommand{\aneunxsieben}{ }

\renewcommand{\aneunxacht}{ }

\renewcommand{\aneunxneun}{ }

\renewcommand{\aneunxzehn}{ }

\renewcommand{\aneunxelf}{ }

\renewcommand{\aneunxzwoelf}{ }


\renewcommand{\azehnxeins}{ }

\renewcommand{\azehnxzwei}{ }

\renewcommand{\azehnxdrei}{ }

\renewcommand{\azehnxvier}{ }

\renewcommand{\azehnxfuenf}{ }

\renewcommand{\azehnxsechs}{ }

\renewcommand{\azehnxsieben}{ }

\renewcommand{\azehnxacht}{ }

\renewcommand{\azehnxneun}{ }

\renewcommand{\azehnxzehn}{ }

\renewcommand{\azehnxelf}{ }

\renewcommand{\azehnxzwoelf}{ }



\renewcommand{\aelfxeins}{ }

\renewcommand{\aelfxzwei}{ }

\renewcommand{\aelfxdrei}{ }

\renewcommand{\aelfxvier}{ }

\renewcommand{\aelfxfuenf}{ }

\renewcommand{\aelfxsechs}{ }

\renewcommand{\aelfxsieben}{ }

\renewcommand{\aelfxacht}{ }

\renewcommand{\aelfxneun}{ }

\renewcommand{\aelfxzehn}{ }

\renewcommand{\aelfxelf}{ }

\renewcommand{\aelfxzwoelf}{ }



\renewcommand{\azwoelfxeins}{ }

\renewcommand{\azwoelfxzwei}{ }

\renewcommand{\azwoelfxdrei}{ }

\renewcommand{\azwoelfxvier}{ }

\renewcommand{\azwoelfxfuenf}{ }

\renewcommand{\azwoelfxsechs}{ }

\renewcommand{\azwoelfxsieben}{ }

\renewcommand{\azwoelfxacht}{ }

\renewcommand{\azwoelfxneun}{ }

\renewcommand{\azwoelfxzehn}{ }

\renewcommand{\azwoelfxelf}{ }

\renewcommand{\azwoelfxzwoelf}{ }



\renewcommand{\adreizehnxeins}{ }

\renewcommand{\adreizehnxzwei}{ }

\renewcommand{\adreizehnxdrei}{ }

\renewcommand{\adreizehnxvier}{ }

\renewcommand{\adreizehnxfuenf}{ }

\renewcommand{\adreizehnxsechs}{ }

\renewcommand{\adreizehnxsieben}{ }

\renewcommand{\adreizehnxacht}{ }

\renewcommand{\adreizehnxneun}{ }

\renewcommand{\adreizehnxzehn}{ }

\renewcommand{\adreizehnxelf}{ }

\renewcommand{\adreizehnxzwoelf}{ }



\renewcommand{\avierzehnxeins}{ }

\renewcommand{\avierzehnxzwei}{ }

\renewcommand{\avierzehnxdrei}{ }

\renewcommand{\avierzehnxvier}{ }

\renewcommand{\avierzehnxfuenf}{ }

\renewcommand{\avierzehnxsechs}{ }

\renewcommand{\avierzehnxsieben}{ }

\renewcommand{\avierzehnxacht}{ }

\renewcommand{\avierzehnxneun}{ }

\renewcommand{\avierzehnxzehn}{ }

\renewcommand{\avierzehnxelf}{ }

\renewcommand{\avierzehnxzwoelf}{ }


\renewcommand{\afuenfzehnxeins}{ }

\renewcommand{\afuenfzehnxzwei}{ }

\renewcommand{\afuenfzehnxdrei}{ }

\renewcommand{\afuenfzehnxvier}{ }

\renewcommand{\afuenfzehnxfuenf}{ }

\renewcommand{\afuenfzehnxsechs}{ }

\renewcommand{\afuenfzehnxsieben}{ }

\renewcommand{\afuenfzehnxacht}{ }

\renewcommand{\afuenfzehnxneun}{ }

\renewcommand{\afuenfzehnxzehn}{ }

\renewcommand{\afuenfzehnxelf}{ }

\renewcommand{\afuenfzehnxzwoelf}{ }


\renewcommand{\asechzehnxeins}{ }

\renewcommand{\asechzehnxzwei}{ }

\renewcommand{\asechzehnxdrei}{ }

\renewcommand{\asechzehnxvier}{ }

\renewcommand{\asechzehnxfuenf}{ }

\renewcommand{\asechzehnxsechs}{ }

\renewcommand{\asechzehnxsieben}{ }

\renewcommand{\asechzehnxacht}{ }

\renewcommand{\asechzehnxneun}{ }

\renewcommand{\asechzehnxzehn}{ }

\renewcommand{\asechzehnxelf}{ }

\renewcommand{\asechzehnxzwoelf}{ }


\tabelleleitsechsxfuenf

Das Paar
\mathl{1184}{} und
\mathl{1210}{} ist befreundet, aber nicht über die Regel von Thabit erhältlich.






\zwischenueberschrift{Zahlentheoretische Funktionen}




\inputdefinition
{}
{

Eine Funktion \maabbdisp {} {\N_+} { {\mathbb C} } {} nennt man \definitionswort {zahlentheoretische Funktion}{.}

}

Eine zahlentheoretische Funktion ist also einfach eine komplexwertige Folge. Im zahlentheoretischen Kontext sind die beiden folgenden Definitionen wichtig.


\inputdefinition
{}
{

Eine \definitionsverweis {zahlentheoretische Funktion}{}{} \maabbdisp {f} {\N_+} {{\mathbb C} } {} heißt \definitionswort {multiplikativ}{,} wenn für \definitionsverweis {teilerfremde}{}{} Zahlen
\mathl{m,n}{} stets
\mavergleichskettedisp
{\vergleichskette
{f(mn) }
{ =} { f(m) f(n) }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.

}

An multiplikativen zahlentheoretischen Funktionen haben wir bisher die eulersche $\varphi$-Funktion, die Teileranzahlfunktion und oben die Teilersummenfunktion kennengelernt.




\inputdefinition
{}
{

Zu \definitionsverweis {zahlentheoretischen Funktionen}{}{} \maabb {f,g} {\N_+} {{\mathbb C} } {} heißt die durch
\mavergleichskettedisp
{\vergleichskette
{(f *g)(n) }
{ \defeq} { \sum_{d \text{ teilt } n } f(d)g { \left( { \frac{ n }{ d } } \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{} definierte Funktion die \definitionswort {Faltung}{} von \mathkor {} {f} {und} {g} {.}

} Diese Summe kann man auch in der Form
\mathdisp {\sum_{n = de} f(d)g(e)} { }
schreiben. Summiert wird nur über die positiven Teilerpaare, was bei dieser Schreibweise übersehen werden könnte.





\inputfaktbeweis
{Zahlentheoretische Funktion/Faltung/Multiplikativ/Fakt}
{Lemma}
{}
{

\faktsituation {Zu \definitionsverweis {multiplikativen}{}{} \definitionsverweis {zahlentheoretischen Funktionen}{}{} \maabb {f,g} {\N_+} {{\mathbb C} } {}}
\faktfolgerung {ist auch die \definitionsverweis {Faltung}{}{}
\mathl{f *g}{} multiplikativ.}
\faktzusatz {}
\faktzusatz {}

}
{

Es seien
\mathl{f,g}{} multiplikativ und es seien
\mathl{m,n}{} \definitionsverweis {teilerfremde}{}{} natürliche Zahlen. Zu einer Faktorzerlegung
\mavergleichskettedisp
{\vergleichskette
{de }
{ =} {mn }
{ } { }
{ } { }
{ } { }
} {}{}{} gibt es aufgrund der Teilerfremdheit eine eindeutige Aufspaltung
\mavergleichskette
{\vergleichskette
{d }
{ = }{ru }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{e }
{ = }{sv }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit
\mathl{r,u}{} und
\mathl{s,v}{} teilerfremd und mit
\mavergleichskette
{\vergleichskette
{rs }
{ = }{m }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und
\mavergleichskette
{\vergleichskette
{uv }
{ = }{n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Daher ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{(f *g) (m \cdot n) }
{ =} { \sum_{ d\cdot e = m \cdot n} f(d) g(e) }
{ =} { \sum_{rs =m,\, uv = n} f(r u)g(s v) }
{ =} { \sum_{rs =m,\, uv = n} f(r)f(u)g(s) g(v) }
{ =} { { \left( \sum_{ r \cdot s = m} f(r)g(s) \right) } \cdot { \left( \sum_{ u \cdot v = n} f(u)g(v) \right) } }
} {
\vergleichskettefortsetzungalign
{ =} { (f *g) (m) \cdot (f*g)( n) }
{ } {}
{ } {}
{ } {}
}{}{,} also ist auch
\mathl{f *g}{} multiplikativ.

}





\inputdefinition
{}
{

Die zahlentheoretische Funktion \maabb {} {\N_+} {{\mathbb C} } {,} die für $1$ den Wert $1$ und sonst überall den Wert $0$ besitzt, wird mit $I$ bezeichnet. Sie heißt die \definitionswort {Faltungseinheit}{.}

}




\inputdefinition
{}
{

Die zahlentheoretische Funktion \maabb {} {\N_+} {{\mathbb C} } {,} die überall den Wert $1$ besitzt, wird mit $U$ bezeichnet.

}




\inputdefinition
{}
{

Die zahlentheoretische Funktion \maabb {\mu} {\N_+} {{\mathbb C} } {,} die durch
\mavergleichskettedisp
{\vergleichskette
{ \mu(n) }
{ \defeq} { \begin{cases} 0,\, \text{falls in der Primfaktorzerlegung von } n \text{ manche Primfaktoren mehrfach auftreten} , \\ (-1)^ k, \, \text{ falls } n = p_1 \cdots p_k \text{ mit verschiedenen Primfaktoren} \, . \end{cases} }
{ } { }
{ } { }
{ } { }
} {}{}{} gegeben ist, heißt \definitionswort {Möbius-Funktion}{.}

}


\inputfaktbeweis
{Zahlentheoretische Funktion/Faltung/Neutrales Element/Möbius/Fakt}
{Lemma}
{}
{

\faktsituation {}
\faktuebergang {Für die Faltung von zahlentheoretischen Funktionen gelten die folgenden Aussagen.}
\faktfolgerung {\aufzaehlungdrei{Die \definitionsverweis {Faltung}{}{} ist eine kommutative und assoziative Verknüpfung. }{Die Faltungseinheit $I$ ist das neutrale Element der Verküpfung. }{Es ist
\mavergleichskettedisp
{\vergleichskette
{U * \mu }
{ =} {I }
{ } { }
{ } { }
{ } { }
} {}{}{.} }}
\faktzusatz {}
\faktzusatz {}

}
{ Siehe Aufgabe 13.9. }


<< | Kurs:Zahlentheorie (Osnabrück 2016-2017) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)