Kurs:Zahlentheorie (Osnabrück 2025)/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]{ \bildeinlesunggif {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} { , }
die alle prim sind, ü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}
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{ F_r
}
{ = }{ 2^{2^r}+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {Fermat-Zahl}{}{}
mit
\mavergleichskette
{\vergleichskette
{ r
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann erfüllt jeder Primfaktor $p$ von $F_r$ die Bedingung
\mavergleichskettedisp
{\vergleichskette
{p
}
{ =} { 2^{r+2} a +1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit einem
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
{
Es sei also $p$ ein Primteiler von
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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 \mathlk{2^{r+1}}{} sein muss, aber
\mavergleichskettek
{\vergleichskettek
{ 2^{2^{r} }
}
{ \neq }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist} {} {.}
Diese Ordnung ist ein Teiler von
\mathl{p-1}{,} woraus folgt, dass
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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 {}
}
{
Es 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 $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-Primzahlen 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}{}{,}
\mavergleichskette
{\vergleichskette
{ q
}
{ = }{ 2p+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und $M_p$ die zugehörige
\definitionsverweis {Mersenne-Zahl}{}{.}
Dann ist $q$ ein Teiler von $M_p$ genau dann, wenn
\mavergleichskette
{\vergleichskette
{ q
}
{ = }{ \pm 1 \mod 8
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist.
}
{
Es ist
\mavergleichskette
{\vergleichskette
{ q
}
{ = }{ 2p+1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Teiler von
\mavergleichskette
{\vergleichskette
{ M_p
}
{ = }{ 2^p-1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau dann, wenn
\mavergleichskette
{\vergleichskette
{ 2^p
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in
\mathl{\Z/( q )}{} ist. Wegen
\mavergleichskettedisp
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ q
}
{ = }{ \pm 1 \mod 8
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der Fall.
\inputbemerkung
{}
{
Ist $p$ eine
\definitionsverweis {Sophie-Germain-Primzahl}{}{,}
die modulo $4$ den Rest $3$ hat, so ist
\mavergleichskette
{\vergleichskette
{ q
}
{ = }{ 2p+1
}
{ = }{ -1 \mod 8
}
{ }{
}
{ }{
}
}
{}{}{}
und nach
Satz 14.9
ist $q$ ein Teiler von $M_p$. Bei
\mavergleichskette
{\vergleichskette
{ p
}
{ > }{ 3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist dies ein echter Teiler und $M_p$ ist nicht prim.
Für
\mavergleichskette
{\vergleichskette
{ p
}
{ = }{ 3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ M_3
}
{ = }{ 2^3-1
}
{ = }{ 7
}
{ = }{ 2p+1
}
{ }{
}
}
{}{}{.}
Für
\mavergleichskette
{\vergleichskette
{ p
}
{ = }{ 11
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ q
}
{ = }{ 23
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
prim und es ist
\mathl{23{{|}} M_{11}=2047}{.} Für
\mavergleichskette
{\vergleichskette
{ p
}
{ = }{ 23
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{ 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
\definitionsverweis {Primzahl}{}{}
und
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ n
}
{ \geq }{ 3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskettek
{\vergleichskettek
{ p_1
}
{ = }{ 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
\mavergleichskette
{\vergleichskette
{ r_i
}
{ \geq }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es Elemente der Ordnung $p_i$ in
\mathl{{ \left( \Z/(p_i^{r_i } ) \right) }^{\times}}{}
\zusatzklammer {auch bei
\mavergleichskettek
{\vergleichskettek
{ p
}
{ = }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {,}
und es ergibt sich der Widerspruch
\mathl{p {{|}} (n-1)}{.} Also sind alle Exponenten einfach.
Für die Umkehrung ist nach Voraussetzung
\mavergleichskette
{\vergleichskette
{ r_i
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei wieder
\mavergleichskettedisp
{\vergleichskette
{ a
}
{ =} { (a_1 , \ldots , a_k)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
eine Einheit. Dann ist
\mavergleichskettealign
{\vergleichskettealign
{ 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.