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

mit einer ganzen Zahl .

Fermat-Zahlen[Bearbeiten | Quelltext bearbeiten]

Die ersten Fermat-Zahlen lauten und .[1]

Eine etwas längere Liste bis findet man in der folgenden aufklappbaren Box.

Wegen hat die Fermatzahl ungefähr doppelt so viele Stellen wie ihre Vorgängerin .

Fermatsche Primzahlen[Bearbeiten | Quelltext bearbeiten]

Die Idee hinter Fermatschen Primzahlen ist der Satz, dass nur für mit prim sein kann:

Die Umkehrung dieses Satzes, dass also jede Fermat-Zahl prim sei, ist falsch. bis sind sogar die einzigen bisher bekannten Fermatschen Primzahlen:

Schon Fermat zeigte, dass diese ersten fünf Fermat-Zahlen Primzahlen sind und vermutete 1637, dass dies auf alle Fermat-Zahlen zutreffe. Diese Vermutung wurde aber schon 1732 von Leonhard Euler einfach widerlegt, indem er mit 641 einen echten Teiler von F5 = 4.294.967.297 fand.[2]

Man vermutet inzwischen, dass außer den ersten fünf keine weiteren Fermatschen Primzahlen existieren. Diese Vermutung beruht auf statistischen Abschätzungen: Der Primzahlsatz besagt, dass 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 Fn als ungerade Zahl eine Primzahl ist, beträgt daher näherungsweise 2 / ln Fn ≈ 3/2n. Die Wahrscheinlichkeit, dass die Fermatzahl Fn oder eine der folgenden Fermatzahlen eine Primzahl ist, ergibt sich durch Summation der geometrische Reihe ungefähr zu 6/2n.

Für verbliebene weder teilweise noch vollständig faktorisierte Fermat-Zahlen ist diese Wahrscheinlichkeit mit etwa 6 · 10−10 mittlerweile aber sehr klein geworden.

Faktorisierungsergebnisse von Fermat-Zahlen[Bearbeiten | Quelltext bearbeiten]

Die Zahlen F0 bis F4 sind, wie schon Fermat erkannt hat, Primzahlen:

Die Zahlen F5 bis F11 sind entgegen der Vermutung Fermats zusammengesetzt. Sie sind bereits vollständig faktorisiert:[3]

Ab F12 ist keine Fermat-Zahl mehr vollständig faktorisiert. Die ersten drei lauten:

Von 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.[5][6]

Für F14 wurde am 3. Februar 2010 ein Faktor veröffentlicht,[7] für F22 am 25. März 2010.[8]

Die kleinste Fermat-Zahl, von der bislang nicht bekannt ist, ob sie prim oder zusammengesetzt ist, ist F33. Diese Zahl hat 2.585.827.973 Stellen.

F3.329.780 ist die größte Fermat-Zahl, von der ein Faktor bekannt ist, nämlich die Primzahl 193 · 23.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 1.002.367 Stellen. Die Fermat-Zahl F3.329.780 selbst hat allerdings mehr als 4,55997 · 101.002.363 Stellen.

Insgesamt weiß man von 288 Fermat-Zahlen, dass sie zusammengesetzt sind. 331 Primfaktoren sind bisher bekannt (Stand: 29. Juni 2016).[3][9]

Der folgenden Tabelle kann man entnehmen, in welchem Intervall wie viele zusammengesetzte Fermat-Zahlen bekannt sind (Stand: 29. Juni 2016):

Nachgewiesen keine Primzahl
n bekannt
zusammengesetzt
Anteil n bekannt
zusammengesetzt
Anteil
5 ≤ n ≤ 32 28 100,0 % 10001 ≤ n ≤ 50000 30 0,0750 %
33 ≤ n ≤ 100 31 045,6 % 50001 ≤ n ≤ 100000 09 0,0180 %
101 ≤ n ≤ 500 58 014,5 % 100001 ≤ n ≤ 500000 25 0,0063 %
501 ≤ n ≤ 1000 22 004,4 % 500001 ≤ n ≤ 1000000 06 0,0012 %
1001 ≤ n ≤ 5000 42 001,1 % 1000001 ≤ n ≤ 5000000 12 0,0003 %
5001 ≤ n ≤ 10000 25 000,5 % 5000001 ≤ n ≤ 10000000 00 0,0000 %

Die kleinsten 25 Fermat-Primfaktoren sind die folgenden:

3, 5, 17, 257, 641, 65537, 114689, 274177, 319489, 974849, 2424833, 6700417, 13631489, 26017793, 45592577, 63766529, 167772161, 825753601, 1214251009, 6487031809, 70525124609, 190274191361, 646730219521, 2710954639361, 2748779069441, … (Folge A023394 in OEIS)

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 Zahlen zugeschnitten und sehr schnell sind.

Die folgenden 16 Primfaktoren von Fermat-Zahlen wurden vor 1950 entdeckt. Seit 1950 wurden alle weiteren Faktoren durch Einsatz von Computern gefunden.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • Für hat jeder Teiler von die Form (bewiesen von Euler und Lucas):
Beispiele:
Der Teiler 641 von F5: 641 = 5 · 27 + 1 = 5 · 128 + 1
Der Teiler 6700417 von F5: 6700417 = 52347 · 27 + 1 = 52347 · 128 + 1
 für 
 für 
 für 
 für 
  • Zwei Fermat-Zahlen sind gleich oder teilerfremd, wie aus der letzten Aussage folgt (Goldbachs Theorem, nach Christian Goldbach, 1730). Daraus lässt sich folgern, dass es unendlich viele Primzahlen gibt (siehe auch Beweisarchiv).
  • Mit Ausnahme von F0 = 3 und F1 = 5 endet jede Fermat-Zahl in Dezimalsystem mit der Ziffer 7. Die vorletzte Ziffer ist ungerade.
(Folge A051158 in OEIS)
Sei die Menge aller Primzahlen, die irgendeine Fermat-Zahl teilen. Dann gilt:
ist konvergent.
  • Sei eine Primzahl. Dann ist mit einer ganzen Zahl .[13]
In diesem Fall gilt:
  • Sei der größte Primteiler der Fermat-Zahl . Dann gilt:[14]
für alle  (bewiesen von Aleksander Grytczuk, Florian Luca und Marek Wójtowicz im Jahr 2001).
für mindestens ein (im Speziellen für ).
  • Jede zusammengesetzte Fermat-Zahl ist eine fermatsche Pseudoprimzahl zur Basis 2. Das heißt, für alle Fermat-Zahlen gilt:
  • Eine prime Fermat-Zahl ist niemals eine Wieferich-Primzahl.[16] Das heißt, für alle primen Fermat-Zahlen gilt:
  • Ein Produkt
von Fermat-Zahlen mit ist eine fermatsche Pseudoprimzahl zur Basis 2 genau dann, wenn (bewiesen von Michele Cipolla im Jahr 1904).[17]
  • Jede Fermat-Zahl mit ist von der Form [18]
  • Keine Fermat-Zahl kann als Differenz von zwei p-ten Potenzen geschrieben werden, wenn p eine ungerade Primzahl ist:[19]
für alle
  • Jede Fermat-Zahl hat im Binärsystem die Form
mit Nullen zwischen den beiden Einsern.[20]

Ungelöste Probleme[Bearbeiten | Quelltext bearbeiten]

  • Ist Fn eine zusammengesetzte Zahl für alle n ≥ 5?
  • Gibt es unendlich viele zusammengesetzte Fermatsche Zahlen? (Diese Behauptung ist etwas schwächer als die vorherige.)
  • Gibt es unendlich viele Fermatsche Primzahlen? (Diese Behauptung steht nicht im Widerspruch zur vorherigen; es könnten beide Behauptungen gelten.)
  • Gibt es Fermatsche Zahlen, die nicht quadratfrei sind?

Geometrische Anwendung der Fermatschen Primzahlen[Bearbeiten | Quelltext 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 paarweise verschiedenen Fermatschen Primzahlen ist.[21]

Insbesondere zeigte Gauß so die Konstruierbarkeit des regelmäßigen Siebzehnecks.

Verallgemeinerte Fermatsche Zahlen[Bearbeiten | Quelltext bearbeiten]

Eine Zahl der Form mit zwei teilerfremden natürlichen Zahlen a > 0 und b > 0 heißt verallgemeinerte Fermatsche Zahl. Ist eine solche Zahl prim, dann heißt sie verallgemeinerte Fermatsche Primzahl.

Ist a = 1, so werden die so erhaltenen verallgemeinerten Fermatschen Zahlen üblicherweise mit

bezeichnet. Die Zahl b nennt man Basis.

Ist a = 1 und b = 2, so handelt es sich um die schon weiter oben erwähnten Fermat-Zahlen

.

Insgesamt sind schon über 11620 Faktoren von verallgemeinerten zusammengesetzten Fermat-Zahlen bekannt[22][23] (Stand: 12. September 2015). Davon wurden alleine über 5000 von Anders Björn und Hans Riesel vor 1998 entdeckt.

Verallgemeinerte Fermatsche Zahlen der Form Fn(b)[Bearbeiten | Quelltext bearbeiten]

Ist b eine gerade Zahl, so kann Fn(b) sowohl zusammengesetzt als auch prim sein.

Beispiel:

b = 8, n = 3 ergibt die zusammengesetzte Zahl
.

Beispiel:

b = 6, n = 2 ergibt die Primzahl
.

Ist b eine ungerade Zahl, so ist Fn(b) als Summe einer Potenz einer ungeraden Zahl (die selbst wieder ungerade ist) und 1 immer eine gerade Zahl, somit durch 2 teilbar und deshalb für b > 1 keine Primzahl, sondern zusammengesetzt. In diesem Fall wird häufig die Zahl

auf ihre Primalität untersucht. Diese Zahlen werden auch halbe verallgemeinerte Fermatsche Zahlen genannt.

Beispiel:

b = 3, n = 2 ergibt die gerade und somit zusammengesetzte Zahl
.
Es ist aber
eine Primzahl.

Beispiel:

b = 5, n = 3 ergibt die gerade und somit zusammengesetzte Zahl
Es ist aber
eine zusammengesetzte Zahl.

Liste der Primzahlen der Form Fn(b)[Bearbeiten | Quelltext bearbeiten]

Verallgemeinerte Fermatsche Zahlen der Form sind in den meisten Fällen zusammengesetzt. Weil diese Zahlen sehr schnell sehr groß werden, sind nicht besonders viele Primzahlen dieser Art bekannt. Es folgt eine Auflistung (aller) bekannten Primzahlen:

Die 10 größten bekannten verallgemeinerten Fermatschen Primzahlen[Bearbeiten | Quelltext bearbeiten]

Der folgenden Liste kann man die 10 größten bekannten verallgemeinerten Fermatschen Primzahlen entnehmen. Sämtliche Entdecker dieser Primzahlen sind Teilnehmer des PrimeGrid-Projektes. In der zweiten Spalte steht, die wievieltgrößte bekannte Primzahl diese Fermatsche Primzahl im Moment ist.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext 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. a b Faktorisierungsstatus aller Fermatzahlen. Stand: 30. April 2015 (englisch).
  4. Siehe Algorithmus nach Morrison und Brillhart.
  5. Jeff Young und Duncan A. Buell: The Twentieth Fermat Number is Composite. Mathematics of Computation, Vol. 50, Nr. 181, Januar 1988, S. 261–263, abgerufen am 14. August 2016.
  6. Richard E. Crandall, Ernst W. Mayer und Jason S. Papadopoulos: The Twenty-Fourth Fermat Number is Composite. Mathematics of Computation, Vol. 72, Nr. 243, 6. Dezember 2002, S. 1555–1572, abgerufen am 14. August 2016.
  7. GIMPS’ second Fermat factor! Bei: MersenneForum.org.
  8. F22 factored! Bei: MersenneForum.org.
  9. Luigi Morelli: Distributed Search for Fermat Number Divisors – NEWS. Abgerufen am 12. August 2016.
  10. Solomon W. Golomb: On the sum of the reciprocals of the Fermat numbers and related irrationalities. Canad. J. Math., Vol. 15, 1963, S. 475–478, abgerufen am 9. August 2016.
  11. Florian Luca: The Anti-Social Fermat Number. The American Mathematical Monthly, Vol. 107, Nr. 2, Februar 2000, S. 171–173, abgerufen am 9. August 2016.
  12. Michal Křížek, Florian Luca, Lawrence Somer: On the Convergence of Series of Reciprocals of Primes Related to the Fermat Numbers. Journal of Number Theory, Vol. 97, Nr. 1, November 2002, S. 95–112, abgerufen am 9. August 2016.
  13. Jeppe Stig Nielsen: S(n) = n^n+1. Abgerufen am 9. August 2016.
  14. Aleksander Grytczuk, Florian Luca & Marek Wójtowicz: Another note on the greatest prime factors of Fermat numbers. Southeast Asian Bulletin of Mathematics, Vol. 25, Nr. 1, Juli 2001, S. 111–115, abgerufen am 9. August 2016.
  15. a b Michal Křížek, Florian Luca und Lawrence Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Theorem 12.16. Canadian Mathematical Society, S. 138, abgerufen am 14. August 2016.
  16. Fredrick Kennard: Unsolved Problems in Mathematics. S. 56, abgerufen am 21. September 2016.
  17. Michal Křížek, Florian Luca und Lawrence Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Theorem 12.1. Canadian Mathematical Society, S. 132, abgerufen am 14. August 2016.
  18. Michal Křížek, Florian Luca und Lawrence Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Theorem 3.12. Canadian Mathematical Society, S. 31, abgerufen am 23. August 2016.
  19. Michal Křížek, Florian Luca und Lawrence Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Theorem 3.14. Canadian Mathematical Society, S. 31, abgerufen am 23. August 2016.
  20. Michal Křížek, Florian Luca und Lawrence Somer: 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Theorem 3.17. Canadian Mathematical Society, S. 32, abgerufen am 23. August 2016.
  21. Emil Artin: Galoissche Theorie. Verlag Harri Deutsch, Zürich 1973, ISBN 3-87144-167-8, S. 85.
  22. Faktoren von verallgemeinerten Fermat-Zahlen, die von Björn und Riesel gefunden wurden. Abgerufen am 12. September 2015.
  23. Faktoren von verallgemeinerten Fermat-Zahlen, die nach Björn und Riesel gefunden wurden. Abgerufen am 12. September 2015.
  24. Die 20 größten verallgemeinerten Fermatschen Primzahlen (englisch). Abgerufen am 20. August 2016.
  25. Liste der größten bekannten Primzahlen (englisch). Abgerufen am 20. August 2016.
  26. http://www.primegrid.com/download/GFN-475856_524288.pdf
  27. http://www.primegrid.com/download/GFN-356926_524288.pdf
  28. http://www.primegrid.com/download/GFN-341112_524288.pdf
  29. http://www.primegrid.com/download/gfn-75898_524288.pdf
  30. https://primes.utm.edu/primes/page.php?id=122018
  31. https://primes.utm.edu/primes/page.php?id=121619
  32. https://primes.utm.edu/primes/page.php?id=121375
  33. https://primes.utm.edu/primes/page.php?id=121187
  34. http://www.primegrid.com/download/gfn-773620_262144.pdf
  35. http://www.primegrid.com/download/gfn-676754_262144.pdf

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]