Fermat-Zahl

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 F5 = 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 Fn eine Primzahl ist, beträgt daher näherungsweise 1,44/2n. Die Summe dieser Ausdrücke ist eine geometrische Reihe und für alle weder teilweise noch vollständig faktorisierten Fermat-Zahlen sehr gering.

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

2n + 1 ≡ (2a)b + 1 ≡ (−1)b + 1 ≡ 0 (mod 2a + 1). Wenn also n einen ungeraden Teiler außer 1 hat, dann ist 2n + 1 zusammengesetzt. (2a + 1 ist dann gerade ein echter Teiler von 2n + 1.) Falls n eine ungerade Primzahl ist, so ist 2n + 1 > 3, aber durch 3 teilbar.

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

Inhaltsverzeichnis

Faktorisierungsstatus von Fermat-Zahlen

Die Zahlen F0 bis F4 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, 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 (F20 und F24) kennt man allerdings keinen Faktor, hat aber gezeigt, dass sie zusammengesetzt sind. Für F14 wurde am 3. Februar 2010 ein Faktor veröffentlicht[1], für F22 am 25. März 2010 [2].

Die kleinste Fermat-Zahl, von der nicht bekannt ist, ob sie prim oder zusammengesetzt ist, ist F33; die größte, von der ein Faktor bekannt ist, ist F2478782, deren Faktor 3 * 22478785 + 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 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 rekursiv berechnen aus
Fn = F0F1...Fn-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 64 + 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

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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Fermat'sche Primzahl — Eine Fermat Zahl, benannt nach dem französischen Mathematiker Pierre de Fermat, ist eine Zahl der Form wobei n eine natürliche Zahl ist. Die ersten Fermat Zahlen sind 3, 5, 17, 257, 65537, … (Folge A000215 in OEIS) Eine Fermat Zahl, die… …   Deutsch Wikipedia

  • Fermat — Pierre de Fermat Pierre de Fermat [pjɛːʀ dəfɛʀˈma] (* vermutlich Ende 1607 oder Anfang 1608 in Beaumont de Lomagne; † 12. Januar 1665 in Castres) war ein französischer Mathematiker und Jurist …   Deutsch Wikipedia

  • Fermat — Fermat, Pierre de F., geb. 1590, war Geometer u. Parlamentsrath in Toulouse u. st. 1665; er schr.: Varia opera mathematica, Toulouse 1674, 2 Bde., Fol. Fermats Lehrsätze von den Polygonalzahlen sind: Jede (ganze) Zahl ist entweder eine Trian… …   Pierer's Universal-Lexikon

  • Fermat'scher Primzahltest — Mit dem fermatschen Primzahltest kann man Primzahlen von zusammengesetzten Zahlen unterscheiden. Der Test erhält eine Zahl n und eine Basis a als Eingabe. n muss eine ungerade Zahl > 3 sein. Außerdem muss a die Bedingung 1 < a < n − 1… …   Deutsch Wikipedia

  • Mersenne-Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Mersennesche Zahl — Eine Mersenne Zahl ist eine Zahl der Form 2n − 1. Im Speziellen bezeichnet man mit Mn = 2n − 1 die n te Mersenne Zahl. Die Primzahlen unter den Mersenne Zahlen werden Mersenne Primzahlen genannt. Die ersten acht Mersenne Primzahlen Mp sind 3, 7,… …   Deutsch Wikipedia

  • Pierre De Fermat — [pjɛːʀ dəfɛʀˈma] (* vermutlich Ende 1607 oder Anfang 1608 in Beaumont de Lomagne; † 12. Januar 1665 in Castres) war ein französischer Mathematiker und Jurist …   Deutsch Wikipedia

  • Faktorisierungsmethode von Fermat — Die Faktorisierungsmethode von Fermat ist ein Algorithmus aus dem mathematischen Teilgebiet Zahlentheorie. Er berechnet zu einer ungeraden, zusammengesetzten Zahl n zwei Teiler a und b, für die gilt. Die Faktorisierungsmethode von Fermat hat nur… …   Deutsch Wikipedia

  • Großer Satz von Fermat — Pierre de Fermat. Der große fermatsche Satz wurde im 17. Jahrhundert von Pierre de Fermat formuliert, aber erst 1993 von Wiles und Taylor bewiesen (1995 veröffentlicht). Er besagt, dass die n te Potenz einer Zahl, wenn n > 2 ist, nicht in die… …   Deutsch Wikipedia

  • Kleiner Fermat — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”