Fermat-Zahl

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Eine Fermat-Zahl, benannt nach dem französischen Mathematiker Pierre de Fermat, ist eine natürliche Zahl der Form

$F_n := 2^{2^n}+1,$

wobei n eine ganze Zahl größer oder gleich 0 ist. Eine Fermat-Zahl, die gleichzeitig Primzahl ist, wird Fermatsche Primzahl genannt. Fermat zeigte, dass die ersten fünf Fermatzahlen F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257 und F₄ = 65537 Primzahlen sind und vermutete 1637, dass dies auf alle Fermat-Zahlen zutrifft. Diese Vermutung wurde von Leonhard Euler 1732 widerlegt, indem er mit 641 einen echten Teiler von F₅ = 4294967297 berechnete. Man vermutet inzwischen, dass alle Fermat-Zahlen, außer den ersten fünf, keine Primzahlen sind. Diese umgekehrte Vermutung beruht auf dem Primzahlsatz, wonach die Anzahl der Primzahlen kleiner oder gleich x näherungsweise $x / l n (x)$ beträgt. Die Primzahlendichte oder "Wahrscheinlichkeit" dafür, dass F_n eine Primzahl ist beträgt daher näherungsweise 1,44/2ⁿ. Die Summe dieser Ausdrücke ist eine geometrische Reihe und für alle weder teilweise noch vollständig faktorisierten Fermat-Zahlen sehr gering.

Wenn $2 n + 1$ eine Primzahl ist, dann ist notwendig n eine Zweierpotenz: Ist $n = a b$ mit $1 < a, b < n$ und ungeradem b, dann ist

2ⁿ + 1 ≡ (2^a)^b + 1 ≡ (−1)^b + 1 ≡ 0 (mod 2^a + 1).

Wenn also n einen ungeraden Teiler hat, dann ist $2 n + 1$ zusammengesetzt. Mit anderen Worten, für jede Primzahl der Form $2 n + 1$ ist n eine Zweierpotenz und die prime $2 n + 1$ ist eine Fermatsche Primzahl. Dies gilt auch für verallgemeinerte Fermatschen Zahlen (s.u.).

Inhaltsverzeichnis

1 Faktorisierungsstatus von Fermat-Zahlen
2 Eigenschaften
3 Geometrische Anwendung der Fermatschen Primzahlen
4 Verallgemeinerte Fermatsche Zahlen
5 Quellen
6 Weblinks

[Bearbeiten] Faktorisierungsstatus von Fermat-Zahlen

Die Zahlen F₀ bis F₄ sind Primzahlen.

Die vollständig faktorisierten Fermat-Zahlen entnimmt man folgender Tabelle:

Von F₅ - F₇:

n	F_n	Entdecker
5	641 * 6700417	Euler (1732)
6	274177*67280421310721	Landry & Le Lasseur (1880)
7	59649589127497217*5704689200685129054721	Morrison & Brillhart (1970)

Ab F₈

n	Entdecker
8	Brent & Pollard (1980)
9	Western (1903), Lenstra & Lenstra & Manasse & Pollard (1990)
10	Selfridge (1953), Brillhart (1962), Brent (1995)
11	Cunningham (1899), Brent & Morain (1988)

Von den Zahlen F₁₂ bis F₃₂, sowie von etlichen größeren Fermat-Zahlen ist bekannt, dass sie zusammengesetzt sind, hauptsächlich weil ein oder mehrere Faktoren gefunden wurden. Von vier Fermat-Zahlen (F₁₄,F₂₀,F₂₂ und F₂₄) kennt man allerdings keinen Faktor, hat aber gezeigt, dass sie zusammengesetzt sind. Die kleinste Fermat-Zahl, von der nicht bekannt ist, ob sie prim oder zusammengesetzt ist, ist F₃₃; die größte, von der ein Faktor bekannt ist, ist F_2478782, deren Faktor 3*2 ^2478785 +1 wurde 2003 von Cosgrave, Jobling, Woltman und Gallot entdeckt. Insgesamt weiß man von 227 Fermat-Zahlen, dass sie zusammengesetzt sind.^[1]

Um von einer Fermat-Zahl nachzuweisen, dass sie zusammengesetzt ist, benutzt man in der Regel den Pepin-Test und den Suyama-Test, die beide besonders auf diese Zahl zugeschnitten und sehr schnell sind.

[Bearbeiten] Eigenschaften

Für einen Teiler p einer Fermat-Zahl F_n, n ≥ 5, gilt p ≡ 1 (mod 2ⁿ⁺²)

Fermat-Zahlen lassen sich rekursiv berechnen aus

F_n = F₀F₁...F_n-1 + 2

Je zwei Fermat-Zahlen sind zueinander teilerfremd. Zusammen mit der letzten Aussage folgt daraus auch, dass es unendlich viele Primzahlen gibt (siehe auch Beweisarchiv).

[Bearbeiten] Geometrische Anwendung der Fermatschen Primzahlen

Carl Friedrich Gauß zeigte (Erstveröffentlichung von Pierre Wantzel im Jahre 1837), dass es einen Zusammenhang zwischen der Konstruktion von regelmäßigen Vielecken und den Fermatschen Primzahlen gibt: Ein regelmäßiges Vieleck mit n Seiten kann nur dann mit Zirkel und Lineal konstruiert werden, wenn n eine Potenz von 2 oder das Produkt einer Potenz von 2 und verschiedenen Fermatschen Primzahlen ist ^[2].

[Bearbeiten] Verallgemeinerte Fermatsche Zahlen

Statt der Basis 2 kann man auch eine andere Basis wählen. Eine Zahl der Form $b^{2^n}+1$ , mit einer natürlichen Zahl b heißt Verallgemeinerte Fermatsche Zahl. Ist eine solche Zahl auch noch prim, dann heißt sie Verallgemeinerte Fermatsche Primzahl.

Beispiel: b=6, n=2 ergibt die Primzahl $64 + 1 = 1297$ .

Die größte bekannte verallgemeinerte Fermatsche Primzahl ist derzeit die 2003 entdeckte Primzahl $1372930^{2^{17}}+1=1372930^{131072}+1$ mit 804474 Ziffern.^[3] Diese wurde vom Projekt Generalized Fermat Prime Search^[4] entdeckt, das große verallgemeinerte Fermatsche Primzahlen sucht.