Fermat-Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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, ….[1]

Fermatsche Primzahlen[Bearbeiten]

Eine Fermat-Zahl, die gleichzeitig Primzahl ist, wird Fermatsche Primzahl genannt. Fermat zeigte, dass die ersten fünf Fermat-Zahlen Primzahlen sind, und vermutete im Jahr 1637, dass dies auf alle Fermat-Zahlen zutreffe. Diese Vermutung wurde 1732 von Leonhard Euler widerlegt, indem er mit 641 einen echten Teiler von F_5=4.294.967.297 fand.[2]

Man vermutet inzwischen, dass es außer den ersten fünf keine weiteren Fermatschen Primzahlen gibt. Diese Vermutung beruht auf dem Primzahlsatz, wonach die Anzahl der Primzahlen, die nicht größer als x sind, näherungsweise gleich x/\ln(x) ist. Die Primzahldichte oder „Wahrscheinlichkeit“ dafür, dass F_n eine Primzahl ist, beträgt daher näherungsweise 1/\ln(F_n)\approx 1{,}443 \cdot 2^{-n}. Die Summe dieser Ausdrücke ist eine geometrische Reihe und für alle weder teilweise noch vollständig faktorisierten Fermat-Zahlen sehr klein.

Wenn 2^n+1 eine Primzahl ist, dann muss n=0 oder eine Zweierpotenz sein. Andernfalls gäbe es nämlich einen ungeraden Teiler c>1 des Exponenten n und dazu mit a\colon=2^{n/c} eine Zerlegung 2^n+1 = (a+1)(a^{c-1}-a^{c-2}+a^{c-3}-...+a^2-a+1) in zwei Faktoren, die beide größer als 1 sind, weil a-1 und c-1 positiv sind.

Faktorisierungsstatus von Fermat-Zahlen[Bearbeiten]

Die Zahlen F_0 bis F_4 sind Primzahlen.

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

Von F5 bis F7:

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

Ab F8:

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 F12 bis F32 und von einigen größeren Fermat-Zahlen ist bekannt, dass sie zusammengesetzt sind, hauptsächlich weil ein oder mehrere Faktoren gefunden wurden. Von zwei Fermat-Zahlen (F20 und F24) kennt man zwar keinen Faktor, hat aber auf andere Art gezeigt, dass sie zusammengesetzt sind. Für F14 wurde am 3. Februar 2010 ein Faktor veröffentlicht,[3] für F22 am 25. März 2010.[4]

Die kleinste Fermat-Zahl, von der nicht bekannt ist, ob sie prim oder zusammengesetzt ist, ist F33; F2478782 ist die größte, von der ein Faktor bekannt ist, nämlich die Pierpont-Primzahl 3\cdot 2^{2478785}+1. Er wurde 2003 von Cosgrave, Jobling, Woltman und Gallot entdeckt. Insgesamt weiß man von 230 Fermat-Zahlen, dass sie zusammengesetzt sind.[5]

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[Bearbeiten]

  • Für einen Teiler p einer Fermat-Zahl Fn, n ≥ 5, gilt p ≡ 1 (mod 2n+2) (z. B. Faktor 641 von F5: 641 = 27*5 +1 = 128*5 +1).
  • Fermat-Zahlen lassen sich durch Fn = F0F1…Fn-1 + 2 rekursiv berechnen.
  • Zwei Fermat-Zahlen sind gleich oder teilerfremd, wie aus der letzten Aussage folgt. Daraus lässt sich folgern, dass es unendlich viele Primzahlen gibt (siehe auch Beweisarchiv).

Geometrische Anwendung der Fermatschen Primzahlen[Bearbeiten]

Carl Friedrich Gauß zeigte, dass es einen Zusammenhang zwischen der Konstruktion von regelmäßigen Polygonen und den Fermatschen Primzahlen gibt: Ein regelmäßiges Polygon 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 mit verschiedenen Fermatschen Primzahlen ist.[6] Insbesondere zeigte Gauß so die Konstruierbarkeit des regelmäßigen Siebzehnecks.

Verallgemeinerte Fermatsche Zahlen[Bearbeiten]

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 prim, dann heißt sie verallgemeinerte Fermatsche Primzahl.

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

Am 19. November 2011 um 14:03:58 UTC fand PrimeGrid PRPNet die momentan größte verallgemeinerte Fermatsche Primzahl 75898^{(2^{19})}+1={75898^{524288}}+1 mit 2.558.647 Ziffern. Diese verdrängt somit die am 29. Oktober 2011 um 11:31:47 UTC von PrimeGrid mit Hilfe des Suchalgorithmus geneferCUDA gefundene, bislang größte verallgemeinerte Fermatsche Primzahl 361658^{(2^{18})}+1={361658^{262144}}+1 mit 1.457.075 Ziffern von Platz eins der Rangliste.[7]

Weitere bekannte verallgemeinerte Fermatsche Primzahlen sind die im März 2008 veröffentlichte Primzahl 24518^{2^{18}}+1=24518^{262144}+1 mit 1.150.678 Ziffern.[8] und die 2003 entdeckte Primzahl 1372930^{2^{17}}+1=1372930^{131072}+1 mit 804.474 Ziffern.[9] Diese beiden Primzahlen wurden vom Projekt Generalized Fermat Prime Search[10] entdeckt, das große verallgemeinerte Fermatsche Primzahlen sucht.

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

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Folge A000215 in OEIS
  2. Leonhard Euler: Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus. (PDF; 399 kB) [E26] In: Commentarii academiae scientiarum Petropolitanae 6 (1732/33) <St. Petersburg 1738>, S. 103-107, hier S. 104. Nachdruck in Opera Omnia, Bd. 1/2, S. 1-5. Englische Übersetzung von Ian Bruce: Observations concerning a certain theorem of Fermat and other considerations regarding prime numbers. (PDF; 100 kB) bzw. von David Zhao: Oberservations on a certain theorem of Fermat and on others regarding prime numbers. (PDF; 101 kB)
  3. MersenneForum.org: GIMPS' second Fermat factor! [1]
  4. MersenneForum.org: F22 factored! [2]
  5. Aktueller Faktorisierungsstatus aller Fermatzahlen (Englisch) (3. Aug. 2007)
  6. Emil Artin: Galoissche Theorie. Verlag Harri Deutsch, Zürich 1973, ISBN 3-87144-167-8, S. 85.
  7. www.seti-germany.de: PrimeGrid/Generalized Fermat Prime Search (Englisch), abgerufen am 25. November 2011.
  8. http://primes.utm.edu/primes/lists/short.txt The largest known primes (26. März 2008: Rangplatz 13)
  9. http://primes.utm.edu/primes/lists/short.txt Short list of largest known primes (Rangplatz 22 am 26. März 2008)
  10. http://perso.wanadoo.fr/yves.gallot/primes/index.html GFPS: Internationale Suche nach verallgemeinerten Fermatschen Primzahlen (Englisch)

Weblinks[Bearbeiten]