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

Aus Wikiversity

\setcounter{section}{14}






\zwischenueberschrift{Fermatsche Primzahlen}




\inputdefinition
{}
{

Eine \definitionsverweis {Primzahl}{}{} der Form
\mathl{2^{s}+1}{,} wobei $s$ eine positive \definitionsverweis {natürliche Zahl}{}{} ist, heißt \definitionswort {Fermatsche Primzahl}{.}

}





\inputfaktbeweis
{Fermatsche Primzahlen/Exponentenlemma/Fakt}
{Lemma}
{}
{

Bei einer \definitionsverweis {Fermatschen Primzahl}{}{}
\mathl{2^{s}+1}{} hat der Exponent die Form
\mavergleichskette
{\vergleichskette
{s }
{ = }{2^r }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit einem
\mathl{r \in \N}{.}

}
{

Wir schreiben
\mavergleichskette
{\vergleichskette
{s }
{ = }{ 2^k u }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} mit $u$ ungerade. Damit ist
\mavergleichskettedisp
{\vergleichskette
{ 2^{2^ku}+1 }
{ =} { { \left( 2^{2^k} \right) }^{u} +1 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Für ungerades $u$ gilt generell die polynomiale Identität \zusatzklammer {da $-1$ eine Nullstelle ist} {} {}
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{ X^{u}+1 }
{ =} {(X+1) { \left( X^{u-1}-X^{u-2}+X^{u-3}- \ldots + X^2 - X +1 \right) } }
{ } { }
{ } { }
{ } { }
} {}{}{.} Also ist
\mavergleichskette
{\vergleichskette
{ 2^{2^k}+1 }
{ \geq }{ 3 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ein Teiler von
\mathl{2^{2^ku}+1}{.} Da diese Zahl nach Voraussetzung prim ist, müssen beide Zahlen gleich sein, und dies bedeutet
\mavergleichskette
{\vergleichskette
{u }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}


Eine Fermatsche Primzahl ist nach diesem Lemma also insbesondere eine Fermat-Zahl im Sinne der folgenden Definition.


\inputdefinition
{}
{

Eine Zahl der Form
\mathl{2^{2^r}+1}{,} wobei $r$ eine \definitionsverweis {natürliche Zahl}{}{} ist, heißt \definitionswort {Fermat-Zahl}{.}

}


\inputfaktbeweis
{Konstruktionen Zirkel Lineal/Regelmäßige n-Ecke/Charakterisierung mit Fermatsche Primzahlen/Fakt}
{Satz}
{}
{

Ein reguläres $n$-Eck ist genau dann mit Zirkel und Lineal konstruierbar, wenn die Primfaktorzerlegung von $n$ die Gestalt
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {2^\alpha p_1 \cdots p_k }
{ } { }
{ } { }
{ } { }
} {}{}{} hat, wobei die $p_i$ verschiedene \definitionsverweis {Fermatsche Primzahlen}{}{} sind.

}
{

Dieser Satz wird in einer Vorlesung über Körpertheorie bzw. Galoistheorie bewiesen.

}







\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Pentagon_construct.gif} }
\end{center}
\bildtext {Konstruktion eines regulären Fünfecks mit Zirkel und Lineal} }

\bildlizenz { Pentagon_construct.gif } {TokyoJunkie} {Mosmas} {PD} {en.wikipedia.org} {en:Image:Pentagon_construct.gif}


Es ist unbekannt, ob es unendlich viele Fermatsche Primzahlen gibt. Es ist noch nicht mal bekannt, ob es außer den ersten fünf Fermat-Zahlen
\mathdisp {3,5,17,257,65537} { }
überhaupt weitere Fermat-Zahlen gibt, die prim sind. Der folgende Satz hilft bei der Auffindung von Primteilern, da er die Suche wesentlich einschränkt.





\inputfaktbeweis
{Fermat-Zahlen/Eigenschaften von Primteilern/Fakt}
{Satz}
{}
{

Sei
\mavergleichskette
{\vergleichskette
{ F_r }
{ = }{2^{2^r}+1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} eine \definitionsverweis {Fermat-Zahl}{}{} mit
\mathl{r \geq 2}{.} Dann erfüllt jeder Primfaktor $p$ von $F_r$ die Bedingung
\mavergleichskettedisp
{\vergleichskette
{p }
{ =} { 2^{r+2} a +1 }
{ } { }
{ } { }
{ } { }
} {}{}{} mit einem
\mathl{a \in \N_+}{.}

}
{

Es sei also $p$ ein Primteiler von
\mathl{F_r=2^{2^r}+1}{.} Dies bedeutet, dass in
\mathl{\Z/(p)}{} die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ 2^{2^r} }
{ =} { -1 }
{ } { }
{ } { }
{ } { }
} {}{}{} vorliegt. Nach quadrieren ist
\mathl{2^{2^{r+1} }=1}{} und die Ordnung von $2$ ist
\mathl{2^{r+1}}{} \zusatzklammer {eine kleinere Ordnung ist nicht möglich, da diese ein Teiler von
\mathl{2^{r+1}}{} sein muss, aber
\mathl{2^{2^{r} } \neq 1}{} ist} {} {.} Diese Ordnung ist ein Teiler von
\mathl{p-1}{,} woraus folgt, dass $p=1 \mod 8$ ist. Dies bedeutet nach dem zweiten Ergänzungssatz zum quadratischen Reziprozitätsgesetz, dass $2$ ein Quadratrest modulo $p$ ist. Es sei
\mathl{x^2=2 \mod p}{.} Dann ist aber die Ordnung von $x$ genau
\mathl{2^{r+2}}{.} Nach dem Schluss von eben ist
\mathl{2^{r+2}}{} ein Teiler von
\mathl{p-1}{,} was
\mavergleichskette
{\vergleichskette
{p }
{ = }{ 2^{r+2}a+1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} bedeutet.

}





\inputfaktbeweis
{Fermat-Zahlen/Paarweise teilerfremd/Fakt}
{Satz}
{}
{

\faktsituation {Zwei verschiedene \definitionsverweis {Fermatsche Zahlen}{}{} $F_m$ und $F_n$ sind teilerfremd.}
\faktfolgerung {}
\faktzusatz {}
\faktzusatz {}

}
{

Sei
\mavergleichskette
{\vergleichskette
{ m }
{ > }{ n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Dann ist
\mavergleichskettedisp
{\vergleichskette
{ F_m-2 }
{ =} { 2^{2^m}-1 }
{ =} { { \left( 2^{2^n} \right) }^{2^{m-n} }-1 }
{ } { }
{ } { }
} {}{}{.} Hierbei ist
\mathl{2^{m-n}}{} gerade, und daher ist
\mavergleichskette
{\vergleichskette
{ F_n }
{ = }{ 2^{2^n}+1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} ein Teiler von dieser Zahl. Das bedeutet, dass ein gemeinsamer Teiler von $F_m$ und von $F_n$ auch ein Teiler von
\mathl{F_m -2}{} ist, also ein Teiler von $2$. Da alle Fermat-Zahlen ungerade sind, bleibt nur $1$ als gemeinsamer Teiler übrig.

}







\inputbemerkung
{}
{

Aus Satz 14.6 folgt erneut, dass es unendlich viele Primzahlen gibt. Jede Fermatzahl
\mavergleichskette
{\vergleichskette
{ F_r }
{ = }{2^{2^r}+1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} hat mindestens einen Primfaktor
\mathl{p_r}{,} und diese sind alle verschieden.

}






\zwischenueberschrift{Sophie Germain Primzahlen}




\inputdefinition
{}
{

Eine \definitionsverweis {Primzahl}{}{} $p$ mit der Eigenschaft, dass auch
\mathl{2p+1}{} eine Primzahl ist, heißt \definitionswort {Sophie-Germain-Primzahl}{.}

}

Beispiele sind
\mathl{(2,5)}{,}
\mathl{(3,7)}{,}
\mathl{(5,11)}{,}
\mathl{(11,23)}{,}
\mathl{(23,47)}{,}
\mathl{(29,59)}{,} etc. Es ist unbekannt, ob es unendlich viele Sophie Germain Zahlen gibt.

Wir kommen nochmal zurück zu Mersenne-Zahlen und besprechen einige Situation, wo man Aussagen über mögliche Primteiler machen kann.




\inputfaktbeweis
{Mersenne Zahlen zu Germain Primzahlen/q als Primteiler/Charakterisierung/Fakt}
{Satz}
{}
{

Es sei $p$ eine \definitionsverweis {Sophie-Germain-Primzahl}{}{,}
\mathl{q=2p+1}{} und $M_p$ die zugehörige \definitionsverweis {Mersenne-Zahl}{}{.} Dann ist $q$ ein Teiler von $M_p$ genau dann, wenn
\mathl{q=\pm1 \mod 8}{} ist.

}
{

Es ist
\mathl{q=2p+1}{} ein Teiler von
\mathl{M_p=2^p-1}{} genau dann, wenn
\mathl{2^p=1}{} in
\mathl{\Z/(q)}{} ist. Wegen
\mathl{p=\frac{q-1}{2}}{} ist dies nach dem Euler-Kriterium genau dann der Fall, wenn $2$ ein Quadratrest modulo $q$ ist. Dies ist nach dem zweiten Ergänzungssatz genau bei
\mathl{q=\pm 1 \mod 8}{} der Fall.

}







\inputbemerkung
{}
{

Ist $p$ eine Sophie-Germain Primzahl, die modulo $4$ den Rest $3$ hat, so ist
\mathl{q=2p+1 = -1 \mod 8}{} und nach Satz 14.9 ist $q$ ein Teiler von $M_p$. Bei
\mathl{p>3}{} ist dies ein echter Teiler und $M_p$ ist nicht prim.

Für
\mathl{p=3}{} ist
\mathl{M_3=2^3-1=7=2p+1}{.} Für
\mathl{p=11}{} ist
\mathl{q=23}{} prim und es ist
\mathl{23{{|}} M_{11}=2047}{.} Für
\mathl{p=23}{} ist
\mathl{q=47}{} wieder prim und es folgt, dass
\mathl{M_{23}}{} ein Vielfaches von $47$ ist.

}

Andere notwendige Bedingungen für Primteiler von Mersenne-Zahlen werden im folgenden Satz ausgedrückt.




\inputfaktbeweis
{Mersenne-Zahlen/Primteiler/Kongruenzbedingungen/Fakt}
{Satz}
{}
{

Es sei $p$ eine ungerade Primzahl und
\mathl{M_p=2^p-1}{} die zugehörige Mersenne-Zahl. Ist $q$ ein Primfaktor von $M_p$, so ist
\mathdisp {q=1 \mod 2p \text{ und } q= \pm 1 \mod 8} { . }

}
{

Es sei $q$ ein Teiler von
\mavergleichskette
{\vergleichskette
{M_p }
{ = }{2^p-1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Dies bedeutet
\mavergleichskettedisp
{\vergleichskette
{ 2^p }
{ =} { 1 \mod q }
{ } { }
{ } { }
{ } { }
} {}{}{.} Dann ist $p$ die Ordnung von $2$ in
\mathl{\Z/(q)}{} und nach Lemma 4.6 ist $p$ ein Teiler von
\mathl{q-1}{.} Dies bedeutet wiederum
\mavergleichskettedisp
{\vergleichskette
{ q }
{ =} { 1 \mod p }
{ } { }
{ } { }
{ } { }
} {}{}{.} Da $p$ und $q$ ungerade sind, folgt sogar
\mavergleichskette
{\vergleichskette
{ q }
{ = }{ 1 \mod 2p }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.} Wenn $x$ ein primitives Element von
\mathl{\Z/(q)}{} ist, so ist
\mavergleichskette
{\vergleichskette
{ 2 }
{ = }{ x^{\frac{q-1}{p} j} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} da alle Elemente der Ordnung $p$ sich so schreiben lassen. Da dieser Exponent gerade ist, muss $2$ ein Quadratrest sein, und der zweite Ergänzungssatz liefert die Kongruenzbedingung modulo $8$.

}







\zwischenueberschrift{Pseudo-Primzahlen}

Als Pseudo-Primzahlen bezeichnet man grob gesprochen solche Zahlen, die zwar nicht prim sind, aber wesentliche Eigenschaften mit Primzahlen gemeinsam haben.




\inputdefinition
{}
{

Eine natürliche Zahl $n$ heißt \definitionswort {quasiprim}{} zur Basis $a$, wenn
\mathl{a^{ n-1}=1}{} modulo $n$ gilt.

}




\inputdefinition
{}
{

Eine natürliche Zahl $n$, die nicht prim ist, und die die Eigenschaft besitzt, dass für jede zu $n$ teilerfremde ganze Zahl $a$
\mavergleichskettedisp
{\vergleichskette
{ a^{n-1} }
{ =} { 1 \mod n }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt, heißt \definitionswort {Carmichael-Zahl}{.}

}

Eine Carmichael-Zahl hat also die Eigenschaft, dass sie \definitionsverweis {quasiprim}{}{} zu jeder zu $n$ teilerfremden Basis $a$ ist.





\inputfaktbeweis
{Carmichael Zahlen/Charakterisierung mit Primteilern/Fakt}
{Satz}
{}
{

Eine natürliche nicht-prime Zahl
\mathl{n \geq 2}{} ist genau dann eine \definitionsverweis {Carmichael-Zahl}{}{,} wenn jeder Primteiler $p$ von $n$ einfach ist und
\mathl{p-1}{} die Zahl
\mathl{n-1}{} teilt.

}
{

Es sei
\mathl{n=p_1^{r_1} \cdots p_k^{r_k}}{} die kanonische Primfaktorzerlegung. Nach dem chinesischen Restsatz ist
\mavergleichskettedisp
{\vergleichskette
{ { \left( \Z/(n) \right) }^{\times} }
{ \cong} { { \left( \Z/(p_1^{r_1} ) \right) }^{\times} \times \cdots \times { \left( \Z/(p_k^{r_k} ) \right) }^{\times} }
{ } { }
{ } { }
{ } { }
} {}{}{.} Es sei
\mathl{a=(a_1, \ldots , a_k)}{} eine zu $n$ teilerfremde Zahl und sei vorausgesetzt, dass $n$ eine Carmichael-Zahl ist. Dann ist insbesondere
\mavergleichskettedisp
{\vergleichskette
{ (a_i)^{n-1} }
{ =} { 1 \mod p_i^{r_i} }
{ } { }
{ } { }
{ } { }
} {}{}{} für jeden Index $i$. Wählt man für $a_i$ ein primitives Element in
\mathl{\Z/( p_i^{r_i} )}{} \zusatzklammer {was nach Satz 5.11 möglich ist; für
\mathl{p_i=2}{} ist nichts zu zeigen} {} {,} so hat dies die Ordnung
\mathl{(p_i-1)p_i^{r_i-1}}{.} Da
\mathl{n-1}{} ein Vielfaches der Ordnung ist und da \mathkor {} {p_i} {und} {n-1} {} teilerfremd sind, folgt, dass
\mathl{n-1}{} ein Vielfaches von
\mathl{p-1}{} ist. Bei
\mathl{r_i \geq 2}{} gibt es Elemente der Ordnung $p_i$ in
\mathl{{ \left( \Z/(p_i^{r_i} ) \right) }^{\times}}{} \zusatzklammer {auch bei $p=2$} {} {,} und es ergibt sich der Widerspruch
\mathl{p {{|}} (n-1)}{.} Also sind alle Exponenten einfach.

Für die Umkehrung ist nach Voraussetzung
\mathl{r_i=1}{.} Es sei wieder
\mathl{a=(a_1, \ldots , a_k)}{} eine Einheit. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ a^{n-1} }
{ =} { \left( a_1^{n-1} , \, \ldots , \, a_k^{n-1} \right) }
{ =} { \left( { \left( a_1^{p_1-1} \right) }^{ \frac{n-1}{p_1-1} } , \, \ldots , \, { \left( a_k^{p_k-1} \right) }^{\frac{n-1}{p_k-1} } \right) }
{ =} { \left( 1 , \, \ldots , \, 1 \right) }
{ =} {1 }
} {}{}{.} Also ist $n$ eine Carmichael-Zahl.

}





\inputbeispiel{}
{

Die kleinste \definitionsverweis {Carmichael-Zahl}{}{} ist
\mavergleichskettedisp
{\vergleichskette
{561 }
{ =} {3 \cdot 11 \cdot 17 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Dies folgt aus Satz 14.14, da $2$, $10$ und $16$ Teiler von
\mathl{560}{} sind.


}

Es ist inzwischen bekannt, dass es unendlich viele Carmichael-Zahlen gibt.


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

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)