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

Fermatsche Primzahlen

Definition Referenznummer erstellen

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

Lemma Referenznummer erstellen

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

Beweis

Wir schreiben ${}s=2^{k}u$ mit ${}u$ ungerade. Damit ist

{}2^{2^{k}u}+1={\left(2^{2^{k}}\right)}^{u}+1\,.

Für ungerades ${}u$ gilt generell die polynomiale Identität (da ${}-1$ eine Nullstelle ist)

X^{u}+1=(X+1){\left(X^{u-1}-X^{u-2}+X^{u-3}-\ldots +X^{2}-X+1\right)}\,.

Also ist ${}2^{2^{k}}+1\geq 3$ ein Teiler von ${}2^{2^{k}u}+1$ . Da diese Zahl nach Voraussetzung prim ist, müssen beide Zahlen gleich sein, und dies bedeutet ${}u=1$ .

\Box

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

Definition Referenznummer erstellen

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

Satz

Ein reguläres ${}n$ -Eck ist genau dann mit Zirkel und Lineal konstruierbar, wenn die Primfaktorzerlegung von ${}n$ die Gestalt

{}n=2^{\alpha }p_{1}\cdots p_{k}\,

hat, wobei die ${}p_{i}$ verschiedene Fermatsche Primzahlen sind.

Beweis

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

\Box

Konstruktion eines regulären Fünfecks mit Zirkel und Lineal

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

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.

Satz Referenznummer erstellen

Sei ${}F_{r}=2^{2^{r}}+1$ eine Fermat-Zahl mit ${}r\geq 2$ . Dann erfüllt jeder Primfaktor ${}p$ von ${}F_{r}$ die Bedingung

{}p=2^{r+2}a+1\,

mit einem ${}a\in \mathbb {N} _{+}$ .

Beweis

Es sei also ${}p$ ein Primteiler von ${}F_{r}=2^{2^{r}}+1$ . Dies bedeutet, dass in ${}\mathbb {Z} /(p)$ die Gleichung

{}2^{2^{r}}=-1\,

vorliegt. Nach quadrieren ist ${}2^{2^{r+1}}=1$ und die Ordnung von ${}2$ ist ${}2^{r+1}$ (eine kleinere Ordnung ist nicht möglich, da diese ein Teiler von ${}2^{r+1}$ sein muss, aber ${}2^{2^{r}}\neq 1$ ist). Diese Ordnung ist ein Teiler von ${}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 ${}x^{2}=2\mod p$ . Dann ist aber die Ordnung von ${}x$ genau ${}2^{r+2}$ . Nach dem Schluss von eben ist ${}2^{r+2}$ ein Teiler von ${}p-1$ , was ${}p=2^{r+2}a+1$ bedeutet.

\Box

Satz Satz 14.6 ändern

Zwei verschiedene Fermatsche Zahlen ${}F_{m}$ und ${}F_{n}$ sind teilerfremd.

Beweis

Sei ${}m>n$ . Dann ist

{}F_{m}-2=2^{2^{m}}-1={\left(2^{2^{n}}\right)}^{2^{m-n}}-1\,.

Hierbei ist ${}2^{m-n}$ gerade, und daher ist ${}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 ${}F_{m}-2$ ist, also ein Teiler von ${}2$ . Da alle Fermat-Zahlen ungerade sind, bleibt nur ${}1$ als gemeinsamer Teiler übrig.

\Box

Bemerkung Referenznummer erstellen

Aus Satz 14.6 folgt erneut, dass es unendlich viele Primzahlen gibt. Jede Fermatzahl ${}F_{r}=2^{2^{r}}+1$ hat mindestens einen Primfaktor ${}p_{r}$ , und diese sind alle verschieden.

Sophie Germain Primzahlen

Definition Referenznummer erstellen

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

Beispiele sind ${}(2,5)$ , ${}(3,7)$ , ${}(5,11)$ , ${}(11,23)$ , ${}(23,47)$ , ${}(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.

Satz Satz 14.9 ändern

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

Beweis

Es ist ${}q=2p+1$ ein Teiler von ${}M_{p}=2^{p}-1$ genau dann, wenn ${}2^{p}=1$ in ${}\mathbb {Z} /(q)$ ist. Wegen ${}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 ${}q=\pm 1\mod 8$ der Fall.

\Box

Bemerkung Referenznummer erstellen

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

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

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

Satz Referenznummer erstellen

Es sei ${}p$ eine ungerade Primzahl und ${}M_{p}=2^{p}-1$ die zugehörige Mersenne-Zahl. Ist ${}q$ ein Primfaktor von ${}M_{p}$ , so ist

q=1\mod 2p{\text{ und }}q=\pm 1\mod 8.

Beweis

Es sei ${}q$ ein Teiler von ${}M_{p}=2^{p}-1$ . Dies bedeutet

{}2^{p}=1\mod q\,.

Dann ist ${}p$ die Ordnung von ${}2$ in ${}\mathbb {Z} /(q)$ und nach Lemma 4.6 ist ${}p$ ein Teiler von ${}q-1$ . Dies bedeutet wiederum

{}q=1\mod p\,.

Da ${}p$ und ${}q$ ungerade sind, folgt sogar ${}q=1\mod 2p$ . Wenn ${}x$ ein primitives Element von ${}\mathbb {Z} /(q)$ ist, so ist ${}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$ .

\Box

Pseudo-Primzahlen

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

Definition Referenznummer erstellen

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

Definition Referenznummer erstellen

Eine natürliche Zahl ${}n$ , die nicht prim ist, und die die Eigenschaft besitzt, dass für jede zu ${}n$ teilerfremde ganze Zahl ${}a$

{}a^{n-1}=1\mod n\,

gilt, heißt Carmichael-Zahl.

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

Satz Satz 14.14 ändern

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

Beweis

Es sei ${}n=p_{1}^{r_{1}}\cdots p_{k}^{r_{k}}$ die kanonische Primfaktorzerlegung. Nach dem chinesischen Restsatz ist

{}{\left(\mathbb {Z} /(n)\right)}^{\times }\cong {\left(\mathbb {Z} /(p_{1}^{r_{1}})\right)}^{\times }\times \cdots \times {\left(\mathbb {Z} /(p_{k}^{r_{k}})\right)}^{\times }\,.

Es sei ${}a=(a_{1},\ldots ,a_{k})$ eine zu ${}n$ teilerfremde Zahl und sei vorausgesetzt, dass ${}n$ eine Carmichael-Zahl ist. Dann ist insbesondere

{}(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 ${}\mathbb {Z} /(p_{i}^{r_{i}})$ (was nach Satz 5.11 möglich ist; für ${}p_{i}=2$ ist nichts zu zeigen), so hat dies die Ordnung ${}(p_{i}-1)p_{i}^{r_{i}-1}$ . Da ${}n-1$ ein Vielfaches der Ordnung ist und da ${}p_{i}$ und ${}n-1$ teilerfremd sind, folgt, dass ${}n-1$ ein Vielfaches von ${}p-1$ ist. Bei ${}r_{i}\geq 2$ gibt es Elemente der Ordnung ${}p_{i}$ in ${}{\left(\mathbb {Z} /(p_{i}^{r_{i}})\right)}^{\times }$ (auch bei ${}p=2$ ), und es ergibt sich der Widerspruch ${}p{|}(n-1)$ . Also sind alle Exponenten einfach.