Fermat-Zahl

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Fermatsche Primzahl)
Wechseln zu: Navigation, Suche

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

wobei eine nichtnegative ganze Zahl ist.

Liste[Bearbeiten | Quelltext bearbeiten]

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 | Quelltext 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 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 sind, näherungsweise gleich ist. Die Primzahldichte oder „Wahrscheinlichkeit“ dafür, dass eine Primzahl ist, beträgt daher näherungsweise Die Summe dieser Ausdrücke ist eine geometrische Reihe und für alle weder teilweise noch vollständig faktorisierten Fermat-Zahlen sehr klein.

Wenn eine Primzahl ist, dann muss oder eine Zweierpotenz sein. Andernfalls gäbe es nämlich einen ungeraden Teiler des Exponenten und dazu mit eine Zerlegung in zwei Faktoren, die beide größer als 1 sind, weil und positiv sind.

Faktorisierungsstatus von Fermat-Zahlen[Bearbeiten | Quelltext bearbeiten]

Die Zahlen bis sind Primzahlen. Die Zahlen bis 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 Dieser Faktor wurde am 25. Juli 2014 von Raymond Ottusch mit Computer-Programmen von Geoffrey Reynolds, Jean Penné und Jim Fougeron entdeckt und hat Stellen. Die Fermat-Zahl F3.329.780 hat mehr als 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. Quadratlichtjahren, also eine Seitenlänge von ca. Lichtjahren. Zum Vergleich: Das beobachtbare Universum hat einen Durchmesser von weniger als 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 | Quelltext 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 | 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 Seiten kann dann und nur dann mit Zirkel und Lineal konstruiert werden, wenn 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 | 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. 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 .

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 | Quelltext 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

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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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, 1927034, 1966374, 2019300, 2041898, 2056292, 2162068, 2177038, 2187182, 2251082, 2313394, ... A251597[26]
17 1, 62722, 130816, 228188, 386892, 572186, 689186, 909548, 1063730, 1176694, 1361244, 1372930, 1560730, 1660830, 1717162, 1722230, 1766192, 1955556, 2194180, 2280466, ... A253854[27]
18 1, 24518, 40734, 145310, 361658, 525094, 676754, 773620, 1415198, 1488256, 1615588, ... A244150[28]
19 1, 75898, 341112, 356926, 475856, ... A243959[29]

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.

Rang wievieltgrößte
bekannte
Primzahla[30][31]
Primzahl Fn(b) Anzahl der Stellen von Fn(b) Entdeckungsdatum Entdecker Referenz
1 17. 475856524288 + 1 F19(475856) 2,976,633 8. August 2012 Masashi Kumagai (JAP) [32]
2 18. 356926524288 + 1 F19(356926) 2,911,151 20. Juni 2012 anonym (JAP) [33]
3 19. 341112524288 + 1 F19(341112) 2,900,832 15. Juni 2012 Peyton Hayslette (USA) [34]
4 23. 75898524288 + 1 F19(75898) 2,558,647 19. November 2011 Michael Goetz (USA) [35]
5 44. 1615588262144 + 1 F18(1615588) 1,627,477 5. Mai 2016 Brook Harste [36]
6 45. 1488256262144 + 1 F18(1488256) 1,618,131 6. März 2016 Stefan Larsson [37]
7 46. 1415198262144 + 1 F18(1415198) 1,612,400 17. Februar 2016 Frank Matillek [38]
8 48. 773620262144 + 1 F18(773620) 1,543,643 19. April 2012 Senji Yamashita (JAP) [39]
9 51. 676754262144 + 1 F18(676754) 1,528,413 12. Februar 2012 Carlos Loureiro (POR) [40]
10 55. 525094262144 + 1 F18(525094) 1,499,526 18. Januar 2012 David Tomecko (USA) [41]
a Stand: 5.5.2016

Die meisten der oben genannten Ergebnisse konnten natürlich nur mit Computerhilfe gefunden werden.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Weblinks[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. 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 5. Mai 2016.
  31. Liste der größten bekannten Primzahlen (englisch). Abgerufen am 1. Juni 2016.
  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. https://primes.utm.edu/primes/page.php?id=121619
  37. https://primes.utm.edu/primes/page.php?id=121375
  38. https://primes.utm.edu/primes/page.php?id=121187
  39. http://www.primegrid.com/download/gfn-773620_262144.pdf
  40. http://www.primegrid.com/download/gfn-676754_262144.pdf
  41. http://www.primegrid.com/download/gfn-525094_262144.pdf