Fermat-Zahl

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

$F_n = 2^{(2^n)} + 1$

wobei n eine nichtnegative ganze Zahl ist. Die ersten Fermat-Zahlen sind

3, 5, 17, 257, 65537, … (Folge A000215 in OEIS)

Eine Fermat-Zahl, die gleichzeitig Primzahl ist, wird Fermat'sche Primzahl genannt. Fermat zeigte, dass die ersten fünf Fermat-Zahlen Primzahlen sind und vermutete im Jahr 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 es außer den ersten fünf keine weiteren Fermat'schen Primzahlen gibt. Diese umgekehrte Vermutung beruht auf dem Primzahlsatz, wonach die Anzahl der Primzahlen kleiner oder gleich x näherungsweise x / ln(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ⁿ + 1 eine Primzahl ist, dann ist notwendig n eine Zweierpotenz: Ist n = ab 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 außer 1 hat, dann ist 2ⁿ + 1 zusammengesetzt. (2^a + 1 ist dann gerade ein echter Teiler von 2ⁿ + 1.) Falls n eine ungerade Primzahl ist, so ist 2ⁿ + 1 > 3, aber durch 3 teilbar.

Mit anderen Worten, für jede Primzahl der Form 2ⁿ + 1 ist n eine Zweierpotenz und die Primzahl 2ⁿ + 1 ist eine Fermat'sche Primzahl. Dies gilt auch für verallgemeinerte Fermat'schen Zahlen (siehe unten).

Faktorisierungsstatus von Fermat-Zahlen

Die Zahlen F₀ bis F₄ sind Primzahlen.

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

Von F₅ bis F₇:

n	Fn	Entdecker der Faktoren
5	641 · 6700417	Euler (1732)
6	274177 · 67280421310721	Landry & Le Lasseur (1880)
7	59649589127497217 · 5704689200685129054721	Morrison & Brillhart (1970)

Ab F₈

n	Entdecker der Faktoren
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 zwei Fermat-Zahlen (F₂₀ und F₂₄) kennt man allerdings keinen Faktor, hat aber gezeigt, dass sie zusammengesetzt sind. Für F₁₄ wurde am 3. Februar 2010 ein Faktor veröffentlicht^[1], für F₂₂ am 25. März 2010 ^[2].

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 230 Fermat-Zahlen, dass sie zusammengesetzt sind.^[3]

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

Eigenschaften

• Für einen Teiler p einer Fermat-Zahl F_n, n ≥ 5, gilt p ≡ 1 (mod 2ⁿ⁺²); (z. B. Faktor 641 von F₅: 641 = 2⁷*5 +1 = 128*5 +1)

• Fermat-Zahlen lassen sich rekursiv berechnen aus

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

• Je zwei Fermat-Zahlen sind zueinander teilerfremd, wie aus der letzten Aussage folgt. Daraus lässt sich schließen, dass es unendlich viele Primzahlen gibt (siehe auch Beweisarchiv).

Geometrische Anwendung der Fermat'schen 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 Fermat'schen Primzahlen gibt: Ein regelmäßiges Vieleck mit n Seiten kann dann und nur dann mit Zirkel und Lineal konstruiert werden, wenn n eine Potenz von 2 oder das Produkt einer Potenz von 2 und verschiedenen Fermat'schen Primzahlen ist ^[4]. Insbesondere zeigte Gauß so die Konstruierbarkeit des regelmäßigen Siebzehnecks.

Verallgemeinerte Fermat'sche 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 Fermat'sche Zahl. Ist eine solche Zahl auch noch prim, dann heißt sie Verallgemeinerte Fermat'sche Primzahl.

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

Am 29. Oktober 2011 um 11:31:47 UTC fand PrimeGrid mit Hilfe des Suchalgorithmus geneferCUDA die momentan größte verallgemeinerte Fermat'sche Primzahl $361658^{(2^{18})}+1={361658^{262144}}+1$ mit einer Länge von 1.457.075 Ziffern. Dies ist damit die 24. größte Primzahl, die je gefunden wurde. ^[5] Die zweitgrößte bekannte verallgemeinerte Fermat'sche Primzahl ist derzeit die im März 2008 veröffentlichte Primzahl $24518^{2^{18}}+1=24518^{262144}+1$ mit 1150678 Ziffern.^[6] Die drittgrößte bekannte verallgemeinerte Fermat'sche Primzahl ist die 2003 entdeckte Primzahl $1372930^{2^{17}}+1=1372930^{131072}+1$ mit 804474 Ziffern.^[7] Diese beiden Primzahlen wurden vom Projekt Generalized Fermat Prime Search^[8] entdeckt, das große verallgemeinerte Fermat'sche Primzahlen sucht.

Die meisten der oben genannten Ergebnisse konnten natürlich nur mit Computerhilfe gefunden werden.

Siehe auch

• Mersenne-Primzahlen
• Prothsche Primzahl
• 257-Eck

Einzelnachweise

1. ↑ MersenneForum.org: GIMPS' second Fermat factor! [1]
2. ↑ MersenneForum.org: F22 factored! [2]
3. ↑ Aktueller Faktorisierungsstatus aller Fermatzahlen (englisch) (3. Aug. 2007)
4. ↑ Emil Artin: Galoissche Theorie. Verlag Harri Deutsch, Zürich 1973, ISBN 3-87144-167-8, S 85.
5. ↑ http://www.primegrid.com/forum_thread.php?id=3726#42828
6. ↑ http://primes.utm.edu/primes/lists/short.txt The largest known primes (26. März 2008: Rangplatz 13)
7. ↑ http://primes.utm.edu/primes/lists/short.txt Short list of largest known primes (Rangplatz 22 am 26. März 2008)
8. ↑ http://perso.wanadoo.fr/yves.gallot/primes/index.html GFPS Internationale Suche nach Verallgemeinerten Fermatschen Primzahlen (englisch)

Weblinks

• http://www.fermatsearch.org Distributed Search for Fermat Number Divisors (englisch)
• http://mathworld.wolfram.com/FermatNumber.html (englisch)