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 & 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 bislang nicht bekannt ist, ob sie prim oder zusammengesetzt ist, ist F33.

F3.329.780 ist die größte Fermat-Zahl, von der ein Faktor bekannt ist, nämlich die Primzahl 193 \cdot 2^{3.329.782}+1. Dieser Faktor wurde am 25. Juli 2014 von Raymond Ottusch mit Computer-Programmen von Geoffrey Reynolds, Jean Penné und Jim Fougeron entdeckt und hat 1002367 \approx 10^6 Stellen. Die Fermat-Zahl F3.329.780 hat mehr als 10^{1.002.363} Stellen. Würde man diese Zahl auf ein quadratisches Blatt Papier schreiben wollen mit 16 Ziffern pro cm2, so hätte das quadratische Blatt Papier eine Fläche von ca. 10^{1.002.326} Quadratlichtjahren, also eine Seitenlänge von ca. 10^{501.163} Lichtjahren. Zum Vergleich: Das beobachtbare Universum hat einen Durchmesser von weniger als 10^{11} Lichtjahren.

Insgesamt weiß man von 281 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 8. August 2012 um 8:58:58 UTC fand der Japaner Masashi Kumagai [7] als Teilnehmer des Projekts PrimeGrid die momentan größte verallgemeinerte Fermatsche Primzahl 475856^{(2^{19})}+1={475856^{524288}}+1 mit 2.976.633 Ziffern [8] [9].

Diese verdrängt somit die am 20. Juni 2012 um 04:26:47 UTC von einem unbekannten japanischen Teilnehmer [10] des Projekts PrimeGrid gefundene, bislang größte verallgemeinerte Fermatsche Primzahl 356926^{(2^{19})}+1={356926^{524288}}+1 mit 2.911.151 Ziffern von Platz eins der Rangliste. [11] [12]

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. GIMPS' second Fermat factor! Bei: MersenneForum.org.
  4. F22 factored! Bei: MersenneForum.org.
  5. Faktorisierungsstatus aller Fermatzahlen. Stand: 30. April 2015 (englisch).
  6. Emil Artin: Galoissche Theorie. Verlag Harri Deutsch, Zürich 1973, ISBN 3-87144-167-8, S. 85.
  7. http://www.primegrid.com/download/GFN-475856_524288.pdf
  8. the top twenty Generalized Fermat: [1] (Englisch), abgerufen am 31. Mai 2015.
  9. http://primes.utm.edu/primes/lists/short.txt The largest known primes (31. Mai 2015: Rangplatz 15)
  10. http://www.primegrid.com/download/GFN-356926_524288.pdf
  11. the top twenty Generalized Fermat: [2] (Englisch), abgerufen am 31. Mai 2015.
  12. http://primes.utm.edu/primes/lists/short.txt The largest known primes (31. Mai 2015: Rangplatz 16)

Weblinks[Bearbeiten]