Kurs:Zahlentheorie (Osnabrück 2008)/Vorlesung 14/latex
\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
\mavergleichskette
{\vergleichskette
{ 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}{.}
}
{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.