Kurs:Zahlentheorie (Osnabrück 2016-2017)/Vorlesung 13/latex
\setcounter{section}{13}
\zwischenueberschrift{Mersenne-Primzahlen}
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Marin_Mersenne.jpeg} }
\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
\mavergleichskette
{\vergleichskette
{ 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.
}
{
Es 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.
}
{
Es 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. Es sei umgekehrt $n$ vollkommen. Wir setzen
\zusatzklammer {in Anlehnung an das Ziel} {} {}
an
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {2^{k-1} u
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit $u$ ungerade und
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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}
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{ k
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine natürliche Zahl und seien
\mavergleichskette
{\vergleichskette
{ a
}
{ = }{ 3 \cdot 2^{k-1} -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{ b
}
{ = }{ 3 \cdot 2^k -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ 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}{ }
\renewcommand{\asiebzehnxeins}{ }
\renewcommand{\asiebzehnxzwei}{ }
\renewcommand{\asiebzehnxdrei}{ }
\renewcommand{\asiebzehnxvier}{ }
\renewcommand{\asiebzehnxfuenf}{ }
\renewcommand{\asiebzehnxsechs}{ }
\renewcommand{\asiebzehnxsieben}{ }
\renewcommand{\asiebzehnxacht}{ }
\renewcommand{\asiebzehnxneun}{ }
\renewcommand{\asiebzehnxzehn}{ }
\renewcommand{\asiebzehnxelf}{ }
\renewcommand{\asiebzehnxzwoelf}{ }
\renewcommand{\aachtzehnxeins}{ }
\renewcommand{\aachtzehnxzwei}{ }
\renewcommand{\aachtzehnxdrei}{ }
\renewcommand{\aachtzehnxvier}{ }
\renewcommand{\aachtzehnxfuenf}{ }
\renewcommand{\aachtzehnxsechs}{ }
\renewcommand{\aachtzehnxsieben}{ }
\renewcommand{\aachtzehnxacht}{ }
\renewcommand{\aachtzehnxneun}{ }
\renewcommand{\aachtzehnxzehn}{ }
\renewcommand{\aachtzehnxelf}{ }
\renewcommand{\aachtzehnxzwoelf}{ }
\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 \definitionsverweis {eulersche}{}{} $\varphi$-Funktion, die \definitionsverweis {Teileranzahlfunktion}{}{} und oben die \definitionsverweis {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}{.}
}
{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) | >> |
|---|