Hauptmenü öffnen

Fermat-Zahl

eine Zahl, die nach dem französischen Mathematiker Pierre de Fermat benannt wurde

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

mit einer ganzen Zahl .

Inhaltsverzeichnis

Fermat-ZahlenBearbeiten

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 PrimzahlenBearbeiten

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 1640, 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-ZahlenBearbeiten

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

n Fermat-Primzahl Fn
0 3
1 5
2 17
3 257
4 65537

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 305 Fermat-Zahlen, dass sie zusammengesetzt sind. 348 Primfaktoren sind bisher bekannt (Stand: 28. März 2019).[3][9]

Der folgenden Tabelle kann man entnehmen, in welchem Intervall wie viele zusammengesetzte Fermat-Zahlen bekannt sind (Stand: 28. März 2019):

Nachgewiesen keine Primzahl
n bekannt
zusammengesetzt
Anteil
05 ≤ n ≤ 32 028 100,0 %
033 ≤ n ≤ 100 031 045,6 %
101 ≤ n ≤ 500 061 015,3 %
0501 ≤ n ≤ 1000 022 004,4 %
1001 ≤ n ≤ 5000 048 001,2 %
05001 ≤ n ≤ 10000 027 000,5 %
TOTAL 217 002,2 %
Nachgewiesen keine Primzahl
n bekannt
zusammengesetzt
Anteil
10001 ≤ n ≤ 50000 35 0,0875 %
050001 ≤ n ≤ 100000 10 0,0200 %
100001 ≤ n ≤ 500000 25 0,0063 %
0500001 ≤ n ≤ 1000000 06 0,0012 %
1000001 ≤ n ≤ 5000000 12 0,0003 %
05000001 ≤ n ≤ 10000000 00 0,0000 %
TOTAL 88 0,0009 %

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.[10]

EigenschaftenBearbeiten

  • 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
  • Fermat-Zahlen lassen sich auf folgende Arten rekursiv berechnen:
  •    für   
  •    für   
  •    für   
  •    für   
  • Es gelten folgende Darstellungen von  :
  • Jede Fermat-Zahl   mit   ist von der Form  , wobei   positiv ganzzahlig ist. (mit anderen Worten:  )[11]
  • Jede Fermat-Zahl   mit   ist von der Form  , wobei   positiv ganzzahlig ist. (mit anderen Worten:  )
  • Jede Fermat-Zahl   mit   ist von der Form  , wobei   positiv ganzzahlig ist. (mit anderen Worten:  )
  • Jede Fermat-Zahl   mit   ist von der Form  , wobei   positiv ganzzahlig ist. (mit anderen Worten:  )
Anders formuliert: Mit Ausnahme von   und   endet jede Fermat-Zahl im Dezimalsystem mit der Ziffer 7. Die letzten beiden Ziffern sind 17, 37, 57 oder 97.[12]
  • Sei   die  -te Fermat-Zahl. Dann gilt:
  •   hat unendlich viele Darstellungen der Form   mit   positiv ganzzahlig, für alle  [13]
  •   hat mindestens eine Darstellung der Form   mit   positiv ganzzahlig. Ist   zusammengesetzt, gibt es mehrere Möglichkeiten dieser Darstellung.[14]
  •   kann niemals als Summe von zwei Primzahlen dargestellt werden, für alle  [15]
  für alle  
  •   kann niemals als Differenz von zwei p-ten Potenzen geschrieben werden, wenn   und p ungerade Primzahlen sind:[16]
  für alle  
  • Sei   die  -te Fermat-Zahl und sei   die Anzahl der Stellen von  . Dann gilt:[17]
 
wobei mit   die Floor-Funktion gemeint ist (also die größte ganze Zahl, die kleiner oder gleich   ist)
  • Sei   die  -te Fermat-Zahl mit  . Dann gilt:
  ist eine Primzahl genau dann, wenn gilt:  
Mit anderen Worten: Für   gilt:
 
Dieser Satz nennt sich Pépin-Test.
  • Für   gilt:[18]
 
  • Sei  ,   und   prim. Dann gilt:[18]
 
  • Sei   eine Primzahl und   eine ganze Zahl. Dann gilt für jede prime Fermat-Zahl   mit  :[19]
  teilt  
  • Sei  . Dann gilt:[20]
  für alle  
  • Sei   eine Primzahl. Dann gilt:[21][22]
  •   mit einer positiven ganzen Zahl  
  •  
Beispiele:
Für   erhält man  
Für   erhält man  
Für   erhält man   (eine 20-stellige Zahl)
Für   erhält man   (eine 617-stellige Zahl)
Für   erhält man   (eine 315653-stellige Zahl)
Auch für   (eine 41373247568-stellige Zahl) und   (die Anzahl der Stellen dieser Zahl hat 620 Stellen) erhält man keine Primzahlen. Für alle anderen   ist noch nicht bekannt, ob es sich um Primzahlen oder nicht handelt.
Könnte man zeigen, dass es keine weiteren Primzahlen der Form   gibt, so wäre auch gleichzeitig bewiesen, dass es unendlich viele zusammengesetzte Fermat-Zahlen gibt.
  • Sei   eine Primzahl. Dann gilt:[22]
  •   mit einer positiven ganzen Zahl  
  •  
  • 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).
  (Folge A051158 in OEIS)
Sei   die Menge aller Primzahlen, die irgendeine Fermat-Zahl   teilen. Dann gilt:
  ist konvergent.
  • Sei   der größte Primteiler der Fermat-Zahl  . Dann gilt:[27]
 
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.[29] 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).[30]
  • Jede Fermat-Zahl   hat im Binärsystem die Form
 
mit   Nullen zwischen den beiden Einsern.[31]

Ungelöste ProblemeBearbeiten

  • 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 PrimzahlenBearbeiten

 
Anzahl der Seiten bekannter konstruierbarer Polygone. Rot: Seitenzahlen der 31 bekannten regulären Polygone mit ungerader Seitenzahl (Lesart von oben nach unten: Gleichseitiges Dreieck – regelmäßiges Fünfeck – regelmäßiges Fünfzehneck - ... – 4294967295-Eck)
Schwarz: Seitenzahlen der (unendlich vielen) bekannten Polygone mit gerader Seitenzahl

Carl Friedrich Gauß zeigte (in seinem Lehrbuch Disquisitiones Arithmeticae), 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.[32]

Mit anderen Worten:

Das  -seitige regelmäßige Polygon kann mit Zirkel und Lineal konstruiert werden
  mit   und   verschiedene Fermatsche Primzahlen

Konkret zeigte Gauß die Konstruierbarkeit des regelmäßigen Siebzehnecks.

Die nach der obigen Formel konstruierbaren regelmäßigen Polygone lassen sich in zwei Gruppen unterteilten: solche mit ungerader Seitenzahl und solche mit gerader Seitenzahl. Alle Polygone in denen   ist, sind offensichtlich solche mit gerader Seitenzahl (durch 2 teilbar). Alle Polygone mit   sind solche mit ungerader Seitenzahl (ein Produkt von Primzahlen größer als 2 ist immer eine ungerade Zahl). Da nur wenige Fermatsche Primzahlen bekannt sind, ist auch die Zahl der konstruierbaren regulären Polygone mit ungerader Seitenzahl begrenzt.

Das regelmäßige Polygon mit der bisher größten bekannten ungeraden Eckenzahl ist somit das 4294967295-Eck.

Verallgemeinerte Fermatsche ZahlenBearbeiten

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.

Insgesamt sind schon über 11719 Faktoren von verallgemeinerten zusammengesetzten Fermat-Zahlen bekannt[33][34] (Stand: 13. August 2018). Davon wurden alleine über 5100 von Anders Björn und Hans Riesel vor 1998 entdeckt.

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

 .

Es folgt eine Auflistung der ersten verallgemeinerten Fermatschen Primzahlen der Form  . Die beiden Basen   und   müssen, damit   prim sein kann, teilerfremd sein. Außerdem ist es auch notwendig, dass man   durch den größten gemeinsamen Teiler   dividiert, da die Zahl   bei ungeradem   und   immer eine gerade Zahl wäre und somit niemals eine Primzahl sein könnte. Weiters kann man ohne Einschränkung annehmen, dass   sein muss, da man bei   das   bedenkenlos mit   vertauschen kann und somit zum Beispiel   ist. Der Fall   führt niemals zu Primzahlen, da dann   wäre und sicher nicht prim ist (es wären in diesem Fall auch die beiden Basen   und   nicht wie vorausgesetzt teilerfremd).

Fast alle verallgemeinerten Fermatschen Zahlen sind wahrscheinlich zusammengesetzt. Bewiesen ist diese Aussage aber nicht, denn schon für   und   (das sind die ursprünglichen Fermat-Zahlen) wurde weiter oben im Kapitel „Ungelöste Probleme“ erwähnt, dass man noch nicht weiß, ob ab   alle weiteren   zusammengesetzt sind oder nicht. Ähnlich verhält es sich mit anderen Basen und Hochzahlen. Und obwohl schon über 11000 Faktoren von verallgemeinerten Fermatschen Zahlen bekannt sind (siehe weiter oben), ist es schwierig, solche Faktoren zu finden, zumal   sehr schnell sehr groß wird. Zum Teil weiß man zwar, dass diese Zahlen zusammengesetzt sein müssen, aber Primteiler kennt man von den wenigsten. Bekannt ist, dass solche Primteiler die Form   haben müssen. Es folgt eine Auflistung von Primfaktoren kleinerer verallgemeinerter Fermatschen Zahlen inklusive zwei etwas höherer Zahlenbeispiele, anhand derer man erkennen kann, wie schnell die Zahlen sehr hoch werden.