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 lauten:[1]

n Fn Anzahl der Stellen von Fn
0 3 1
1 5 1
2 17 2
3 257 3
4 65537 5
5 4294967297 10
6 18446744073709551617 20
7 340282366920938463463374607431768211457 39
8 115792089237316195423570985008687907853269984665640564039457584007913129639937 78

Die Anzahl der Stellen verdoppelt sich beinahe jedes Mal.

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 Zahlen F_5 bis F_{11} sind mittlerweile vollständig faktorisiert.[3]

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

Von F5 bis F8:

n Primfaktoren von Fn Entdecker der Faktoren
5 641 • 6700417 Euler (1732)
6 274177 • 67280421310721 Landry & Le Lasseur (1880)
7 59649589127497217 • 5704689200685129054721 Morrison & Brillhart (1970)[4]
8 1238926361552897 • 93461639715357977769163558199606896584051237541638188580280321 Brent & Pollard (1980)

Ab F9 wird hier wegen der Länge der Primfaktoren nur noch die Anzahl der Stellen von Fn und die Entdecker der Faktoren bekanntgegeben:

n Anzahl der Stellen von Fn Entdecker der Faktoren
9 155 Western (1903), Lenstra & Manasse (1990)
10 309 Selfridge (1953), Brillhart (1962), Brent (1995)
11 617 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,[5] für F22 am 25. März 2010.[6]

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.[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 Zahlen 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.[7] Insbesondere zeigte Gauß so die Konstruierbarkeit des regelmäßigen Siebzehnecks.

Verallgemeinerte Fermatsche Zahlen[Bearbeiten]

Eine Zahl der Form b^{2^n}+ a^{2^n} 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 F_n(b)=b^{2^n}+1 bezeichnet. Den Faktor b nennt man Basis.

Ist a=1 und b=2, so handelt es sich um die schon weiter oben erwähnten Fermat-Zahlen F_n(2)=F_n=2^{2^n}+1.

Insgesamt sind schon 11620 Faktoren von verallgemeinerten zusammengesetzten Fermat-Zahlen bekannt[8][9] (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]

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

Beispiel: b = 8, n = 3 ergibt die zusammengesetzte Zahl F_3(8)=8^{2^3}+1=8^8+1=16.777.217=97 \cdot 257 \cdot 673.

Beispiel: b = 6, n = 2 ergibt die Primzahl F_2(6)=6^{2^2}+1=6^4+1=1297.

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 keine Primzahl, sondern zusammengesetzt. In diesem Fall wird häufig die Zahl \frac{F_n(b)}{2}=\frac{b^{2^n}+1}{2} 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 F_2(3)=3^{2^2}+1=3^4+1=81+1=82=2 \cdot 41.

Es ist aber \frac{F_2(3)}{2}=\frac{3^{2^2}+1}{2}=\frac{82}{2}=41 eine Primzahl.

Beispiel: b = 5, n = 3 ergibt die gerade und somit zusammengesetzte Zahl F_3(5)=5^{2^3}+1=5^8+1=390625+1=390626=2 \cdot 17 \cdot 11489.

Es ist aber \frac{F_3(5)}{2}=\frac{5^{2^3}+1}{2}=\frac{390626}{2}=195313=17 \cdot 11489 eine zusammengesetzte Zahl.

Liste der Primzahlen der Form Fn(b)[Bearbeiten]

Verallgemeinerte Fermatsche Zahlen der Form F_n(b)=b^{2^n}+1 sind in den meisten Fällen zusammengesetzt. Weil diese Zahlen sehr schnell sehr hoch werden, sind nicht besonders viele Primzahlen dieser Art bekannt. Es folgt eine Auflistung dieser momentan bekannten Primzahlen:

n Fn(b) b, für welche Fn(b) prim ist OEIS-Sequenz
0 b+1 1, 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, 138, 148, 150, 156, 162, 166, 172, 178, 180, 190, 192, 196, 198, 210, 222, 226, 228, 232, 238, 240, 250, 256, 262, 268, 270, ... (alle Primzahlen minus 1) A006093[10]
1 b^2+1 1, 2, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, 176, 180, 184, 204, 206, 210, 224, 230, 236, 240, 250, 256, 260, 264, 270, 280, 284, 300, 306, 314, 326, 340, 350, 384, 386, 396,… A005574[11]
2 b^4+1 1, 2, 4, 6, 16, 20, 24, 28, 34, 46, 48, 54, 56, 74, 80, 82, 88, 90, 106, 118, 132, 140, 142, 154, 160, 164, 174, 180, 194, 198, 204, 210, 220, 228, 238, 242, 248, 254, 266, 272, 276, 278, 288, 296, 312, 320, 328, 334, 340, 352, 364, 374, 414, 430, 436, 442, 466, ... A000068[12]
3 b^8+1 1, 2, 4, 118, 132, 140, 152, 208, 240, 242, 288, 290, 306, 378, 392, 426, 434, 442, 508, 510, 540, 542, 562, 596, 610, 664, 680, 682, 732, 782, 800, 808, 866, 876, 884, 892, 916, 918, 934, 956, 990, 1022, 1028, 1054, 1106, 1120, 1174, 1224, 1232, 1256, 1284, ... A006314[13]
4 b^{16}+1 1, 2, 44, 74, 76, 94, 156, 158, 176, 188, 198, 248, 288, 306, 318, 330, 348, 370, 382, 396, 452, 456, 470, 474, 476, 478, 560, 568, 598, 642, 686, 688, 690, 736, 774, 776, 778, 790, 830, 832, 834, 846, 900, 916, 946, 956, 972, 982, 984, 1018, 1044, 1078, ... A006313[14]
5 b^{32}+1 1, 30, 54, 96, 112, 114, 132, 156, 332, 342, 360, 376, 428, 430, 432, 448, 562, 588, 726, 738, 804, 850, 884, 1068, 1142, 1198, 1306, 1540, 1568, 1596, 1678, 1714, 1754, 1812, 1818, 1878, 1906, 1960, 1962, 2046, 2098, 2118, 2142, 2330, 2418, 2434, 2654, 2668, ... A006315[15]
6 b^{64}+1 1, 102, 162, 274, 300, 412, 562, 592, 728, 1084, 1094, 1108, 1120, 1200, 1558, 1566, 1630, 1804, 1876, 2094, 2162, 2164, 2238, 2336, 2388, 2420, 2494, 2524, 2614, 2784, 3024, 3104, 3140, 3164, 3254, 3278, 3628, 3694, 3738, 3750, 4000, 4030, 4058, 4166, ... A006316[16]
7 b^{128}+1 1, 120, 190, 234, 506, 532, 548, 960, 1738, 1786, 2884, 3000, 3420, 3476, 3658, 4258, 5788, 6080, 6562, 6750, 7692, 8296, 9108, 9356, 9582, 9706, 10238, 10994, 11338, 11432, 11466, 11554, 11778, 12704, 12766, 13082, 13478, 13700, ... A056994[17]
8 b^{256}+1 1, 278, 614, 892, 898, 1348, 1494, 1574, 1938, 2116, 2122, 2278, 2762, 3434, 4094, 4204, 4728, 5712, 5744, 6066, 6508, 6930, 7022, 7332, 8524, 8644, 8762, 8808, 9024, 9142, 9412, 10892, 12206, 13220, 13222, 13246, 13370, 13738, 14114, 14930, ... A056995[18]
9 b^{512}+1 1, 46, 1036, 1318, 1342, 2472, 2926, 3154, 3878, 4386, 4464, 4474, 4482, 4616, 4688, 5374, 5698, 5716, 5770, 6268, 6386, 6682, 7388, 7992, 8678, 8792, 9448, 9452, 9972, 10086, 10448, 10926, 11468, 12754, 13198, 13776, 14734, 16826, 16914, 18334, ... A057465[19]
10 b^{1024}+1 1, 824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, 18336, 19564, 20624, 22500, 24126, 26132, 26188, 26240, 29074, 29658, 30778, 31126, 32244, 33044, 34016, ... A057002[20]
11 b^{2048}+1 1, 150, 2558, 4650, 4772, 11272, 13236, 15048, 23302, 26946, 29504, 31614, 33308, 35054, 36702, 37062, 39020, 39056, 43738, 44174, 45654, 46502, 47348, 49190, 49204, 49544, 54514, 57210, 59770, 61184, 66894, 68194, 70574, 72446, 82642, ... A088361[21]
12 b^{4096}+1 1, 1534, 7316, 17582, 18224, 28234, 34954, 41336, 48824, 51558, 51914, 57394, 61686, 62060, 89762, 96632, 98242, 100540, 101578, 109696, 110540, 114690, 125440, 125442, 127596, 138068, 144362, 154908, 157310, 161822, 161900, 166224, ... A088362[22]
13 b^{8192}+1 1, 30406, 71852, 85654, 111850, 126308, 134492, 144642, 147942, 150152, 165894, 176206, 180924, 201170, 212724, 222764, 225174, 241600, 241860, 248744, 268032, 270674, 302368, 316970, 326260, 347962, 350830, 397468, 410938, 416010, 441238, 443718, 458520, 462678, 463012, 475158, 481750, ... A226528[23]
14 b^{16384}+1 1, 67234, 101830, 114024, 133858, 162192, 165306, 210714, 216968, 229310, 232798, 422666, 426690, 449732, 462470, 468144, 498904, 506664, 509622, 528614, 572934, 581424, 638980, 641762, 656210, 698480, 704930, 730352, 795810, 840796, 908086, 975248, 976914, 990908, 1007874, 1037748, 1039970, 1067896, 1082054, 1097352, 1102754, 1132526, 1162996, 1171010, 1177808, 1181388, ... A226529[24]
15 b^{32768}+1 1, 70906, 167176, 204462, 249830, 321164, 330716, 332554, 429370, 499310, 524552, 553602, 743788, 825324, 831648, 855124, 999236, 1041870, 1074542, 1096382, 1113768, 1161054, 1167528, 1169486, 1171824, 1210354, 1217284, 1277444, 1519380, 1755378, 1909372, 1922592, 1986700, 2034902, 2147196, 2167350, ... A226530[25]
16 b^{65536}+1 1, 48594, 108368, 141146, 189590, 255694, 291726, 292550, 357868, 440846, 544118, 549868, 671600, 843832, 857678, 1024390, 1057476, 1087540, 1266062, 1361846, 1374038, 1478036, 1483076, 1540550, 1828502, 1874512, 2162068, 2177038, 2187182, 2251082, 2313394, ... A251597[26]
17 b^{131072}+1 1, 62722, 130816, 228188, 386892, 572186, 689186, 909548, 1063730, 1176694, 1361244, 1372930, 1560730, ... A253854[27]
18 b^{262144}+1 1, 24518, 40734, 145310, 361658, 525094, 676754, 773620, ... A244150[28]
19 b^{524288}+1 1, 75898, 341112, 356926, 475856, ... A243959[29]

Die 10 größten bekannten verallgemeinerten Fermatschen Primzahlen[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.

Rang wievieltgrößte
bekannte
Primzahla[30][31]
Primzahl Fn(b) Anzahl der Stellen von Fn(b) Entdeckungsdatum Entdecker Referenz
1 16. 475856524288 + 1 F19(475856) 2,976,633 8. August 2012 Masashi Kumagai (JAP) [32]
2 17. 356926524288 + 1 F19(356926) 2,911,151 20. Juni 2012 anonym (JAP) [33]
3 18. 341112524288 + 1 F19(341112) 2,900,832 15. Juni 2012 Peyton Hayslette (USA) [34]
4 21. 75898524288 + 1 F19(75898) 2,558,647 19. November 2011 Michael Goetz (USA) [35]
5 43. 773620262144 + 1 F18(773620) 1,543,643 19. April 2012 Senji Yamashita (JAP) [36]
6 46. 676754262144 + 1 F18(676754) 1,528,413 12. Februar 2012 Carlos Loureiro (POR) [37]
7 49. 525094262144 + 1 F18(525094) 1,499,526 18. Januar 2012 David Tomecko (USA) [38]
8 54. 361658262144 + 1 F18(361658) 1,457,075 29. Oktober 2011 Michel Johnson (DEU) [39]
9 65. 145310262144 + 1 F18(145310) 1,353,265 8. Februar 2011 Ricky L Hubbard (USA) [40]
10 77. 40734262144 + 1 F18(40734) 1,208,473 8. März 2011 Senji Yamashita (JAP) [41]
a Stand: 19.11.2015

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. a b Faktorisierungsstatus aller Fermatzahlen. Stand: 30. April 2015 (englisch).
  4. siehe Algorithmus_nach_Morrison_und_Brillhart
  5. GIMPS' second Fermat factor! Bei: MersenneForum.org.
  6. F22 factored! Bei: MersenneForum.org.
  7. Emil Artin: Galoissche Theorie. Verlag Harri Deutsch, Zürich 1973, ISBN 3-87144-167-8, S. 85.
  8. Faktoren von verallgemeinerten Fermat-Zahlen, die von Björn und Riesel gefunden wurden. Abgerufen am 12. September 2015.
  9. Faktoren von verallgemeinerten Fermat-Zahlen, die nach Björn und Riesel gefunden wurden. Abgerufen am 12. September 2015.
  10. https://oeis.org/A006093
  11. https://oeis.org/A005574
  12. https://oeis.org/A000068
  13. https://oeis.org/A006314
  14. https://oeis.org/A006313
  15. https://oeis.org/A006315
  16. https://oeis.org/A006316
  17. https://oeis.org/A056994
  18. https://oeis.org/A056995
  19. https://oeis.org/A057465
  20. https://oeis.org/A057002
  21. https://oeis.org/A088361
  22. https://oeis.org/A088362
  23. https://oeis.org/A226528
  24. https://oeis.org/A226529
  25. https://oeis.org/A226530
  26. https://oeis.org/A251597
  27. https://oeis.org/A253854
  28. https://oeis.org/A244150
  29. https://oeis.org/A243959
  30. Die 20 größten verallgemeinerten Fermatschen Primzahlen (englisch). Abgerufen am 19. November 2015.
  31. Liste der größten bekannten Primzahlen (englisch). Abgerufen am 19. November 2015.
  32. http://www.primegrid.com/download/GFN-475856_524288.pdf
  33. http://www.primegrid.com/download/GFN-356926_524288.pdf
  34. http://www.primegrid.com/download/GFN-341112_524288.pdf
  35. http://www.primegrid.com/download/gfn-75898_524288.pdf
  36. http://www.primegrid.com/download/gfn-773620_262144.pdf
  37. http://www.primegrid.com/download/gfn-676754_262144.pdf
  38. url=http://www.primegrid.com/download/gfn-525094_262144.pdf
  39. url=http://www.primegrid.com/download/gfn-361658_262144.pdf
  40. http://www.primegrid.com/download/gfn-145310_262144.pdf
  41. http://www.primegrid.com/download/gfn-40734_262144.pdf

Weblinks[Bearbeiten]