Fermatsche Primzahlen


Hierbei handelt es sich um Primzahlen der Form p = 2n + 1. Damit eine Zahl p dieser Art eine Primzahl sein kann, muß n selbst eine Potenz von 2 sein, also von der Form n = 2m. Denn besitzt etwa n einen ungeraden Faktor u > 1, gilt also n = c*u mit einer natürlichen Zahl c, so hat man für p = 2c*u + 1 = au + 1 mit a = 2c die Zerlegung

p = au + 1 = (a + 1)*(au-1 - au-2 + - ... + a2 - a + 1),

d. h. p ist keine Primzahl. Man nennt also Fm = 22m + 1 die m-te Fermatsche Zahl und fragt danach, ob es sich tatsächlich um eine Primzahl handelt.

Für m = 0, 1, 2, 3, 4 ergeben sich in der Tat die Primzahlen

3, 5, 17, 257, 65537,

und Pierre de Fermat äußerte 1640 die Vermutung, daß dies stets der Fall sei. Aber schon 1732 konnte Leonhard Euler für m = 5 die Zerlegbarkeit gemäß

F5 = 4294967297 = 641*6700417

zeigen. Wegen 641 = 625 + 16 = 54 + 24 teilt nämlich 641 die Zahl
A = 228*(54 + 24) = 54*228 + 232. Andererseits teilt 641 wegen 641 = 640 + 1 = 5*128 + 1 = 5*27 + 1 auch die Zahl (5*27 + 1)*(5*27 - 1) = 52*214 - 1, also auch B = (52*214 - 1)*(52*214 + 1) = 54*228 - 1. Insgesamt teilt 641 daher die Differenz A - B = 232 + 1 = F5.

Im Jahre 1880 widerlegte Landry die Vermutung von Fermat auch für den Fall m = 6, indem er die folgende Zerlegung fand

F6 = 274177*67280421310721.

Nachdem man auch für größere Fermatsche Zahlen schon einige Primfaktoren gefunden hatte (vgl. die unten stehenden Tabellen), gelang die vollständige Zerlegung von F7 erst 1970 durch Morrison und Brillhart:

F7 = 59649589127497217*5704689200685129054721.

Euler und Lucas hatten gezeigt, daß Primfaktoren p einer Fermatschen Zahl stets von der Form

p = k*2n+2 + 1

sind, beispielsweise

F5 = (5*27 + 1)*(52347*27 + 1),
F6 = (1071*28 + 1)*(262814145745*28 + 1) und
F7 = (116503103764643*29 + 1)*(11141971095088142685*29 + 1).

Bis heute ist keine weitere Fermatsche Primzahl außer den oben angegebenen bekannt, man weiß aber von 213 Fermatschen Zahlen definitiv, daß sie zusammengesetzt sind. F2145451 ist die größte von ihnen. Obwohl die Fermatschen Zahlen Fm mit wachsendem Index m schnell anwachsen, hat man mittlerweile etliche weitere in Primfaktoren zerlegt. Die kleinste Fermatsche Zahl, für die noch keine vollständige Primfaktorzerlegung bekannt ist, ist die 1234-stellige Zahl F12. Von ihr kennt man die ersten fünf Primfaktoren, nämlich 114689 = 7*214 + 1, 26017793 = 397*216 + 1, 63766529 = 973*216 + 1, 190274191361 = 11613415*214 + 1 und 1256132134125569 = 76668221077*214 + 1. Man weiß weiterhin, daß der restliche Faktor C1187, der immerhin noch aus 1187 Stellen besteht, zusammengesetzt (Composite) ist, jedoch hat man noch keine konkrete Zerlegung für ihn.

Von einigen Fermatschen Zahlen ( m = 14, 20, 22 , 24), weiß man bisher nur, daß sie zusammengesetzt sind, ohne einen einzigen Faktor zu kennen. Von vielen Fermatschen Zahlen ( m = 33, 34, 35, 40, 41, 44, 45, 46, 47, 50, ...) ist bisher weder bekannt, ob sie Primzahlen sind, noch daß sie zusammengesetzt sind.


Die folgenden Übersichten und Tabellen geben den augenblicklichen Stand der Suche nach Primfaktoren von Fermatschen Zahlen wieder, die seit einigen Jahren auch mit dem Programm FERMAT von Leonid Durman im Internet durchgeführt wird. Insgesamt sind 246 Primfaktoren von Fermatschen Zahlen bekannt.

Die vollständigen Informationen zu F0 bis F7 finden sich bereits im oben stehenden Text.

F8

Prent und Pollard fanden 1980 die Zerlegung

F8 = (604944512477*211 + 1)*P62 = 1238926361552897*P62,

wobei P62=k*211 + 1 eine 62-stellige Primzahl ist und k selbst 59 Stellen besitzt.

F9

Nachdem Western bereits 1903 den Faktor 37*216 + 1 = 2424833 gefunden hatte, gelang die vollständige Faktorisierung

F9 = 2424833*7455602825647884208337395736200454918783366342657*P99,

erst 1990 Lenstra, Manasse und anderen. Dabei ist der zweite Faktor gleich

3640431067210880961102244011816628378312190597*211 + 1

und im dritten Faktor P99 = k*211 + 1 besitzt die Zahl k bereits 96 Stellen.

F10

Der erste Faktor 45592577 = 11131*212 + 1 wurde 1953 von Selfridge gefunden, der zweite 6487031809 = 395937*214 + 1 im Jahre 1962 von Brillhart. 1995 gelang dann Brent die vollständige Faktorisierung, indem er den dritten Faktor

4659775785220018543264560743076778192897= 1137640572563481089664199400165229051*212 + 1

und den vierten Faktor P252 =k*213 + 1 bestimmte. Dabei besitzt die Zahl k schon 248 Stellen.

F11

Bereits 1899 hatte Cunningham die ersten beiden Faktoren 319489 = 39*213 + 1 und 974849 = 119*213 + 1 gefunden. Die vollständige Faktorisierung gelang dann 1988 Brent und Morain, wobei Brent zunächst die beiden weiteren Faktoren 167988556341760475137 = 10253207784531279*214 + 1 und 3560841906445833920513 = 434673084282938711*213 + 1 fand und dann zusammen mit Morain den letzten Faktor P564 = k*213 + 1, in dem k selbst 560 Stellen hat.

F12

Die bekannten Primfaktoren wurden bereits oben angegeben. Den ersten fanden Lucas und Pervushin 1877, die beiden n&aumnl;chsten Western 1903. Den vierten Faktor fanden Hallyburton und Brillhart 1974 und den vorläufig letzten Baillie 1986, der auch nachwies, daß der weitere Faktor C1187 zusammengesetzt ist.

F13

Den ersten Primfaktor 2710954639361 = 41365885*216 + 1 fanden Hallyburton und Brillhart 1974, den zweiten 2663848877152141313 = 20323554055421*217 + 1 und dritten 3603109844542291969 = 6872386635861*219 + 1 fand Crandall 1991, und den bisher letzten 319546020820551643220672513 = 609485665932753836099*219 + 1 Brent 1995, der auch nachwies, daß der verbleibende Faktor C2391 zusammengesetzt ist.

F14

1963 bewiesen Selfridge und Hurwitz, daß die 4933-stellige Zahl F14 zusammengesetzt ist. Mehr ist bisher nicht bekannt.

F15

Den ersten Primfaktor 1214251009 = 579*221 + 1 fand Kraitchik bereits 1925, den zweiten 2327042503868417 = 17753925353*217 + 1 Gostin 1987, den vorläufig letzten 168768817029516972383024127016961 = 1287603889690528658928101555*217 + 1 Crandall und van Halewyn 1997. Ebenfalls 1997 wies Brent nach, daß der restliche Faktor C9808 zusammengesetzt ist.

F16

Den ersten Primfaktor 825753601 = 1575*219 + 1 fand Selfridge 1953, den bisher letzten 188981757975021318420037633 = 180227048850079840107*220 + 1 Crandall und Dilcher 1996. Im selben Jahr bewies Brent, daß der fehlende Faktor C19694 zusammengesetzt ist.

F17

Den bisher einzigen Primfaktor 31065037602817 = 59251857*219 + 1 fand Gostin 1978. Im Jahre 1987 bewies Baillie, daß der restliche Faktor C39444 zusammengesetzt ist.

F18

Den ersten Primfaktor 13631489 = 13*220 + 1 fand Western bereits 1903, den zweiten 81274690703860512587777 = 9688698137266697*223 + 1 Crandall, McIntosh und Tardif 1999. Von dem restlichen Faktor C78884 bewies Crandall 1999, daß er zusammengesetzt ist.

F19

Den ersten Primfaktor 70525124609 = 33629*221 + 1 fand Riesel 1962, den zweiten 646730219521 = 308385*221 + 1 Wrathall 1963. Von dem restlichen Faktor C157804 bewiesen Crandall, Doenias, Norrie und Young 1993, daß er zusammengesetzt ist.

F20

1987 bewiesen Buell und Young, daß die 315653-stellige Zahl F20 zusammengesetzt ist. Mehr ist bisher nicht bekannt.

F21

Den bisher einzigen Primfaktor 4485296422913 = 534689*223 + 1 fand Wrathall 1963. Crandall, Doenias, Norrie und Young zeigten dann 1993, daß der restliche Faktor C631294 zusammengesetzt ist.

F22

1993 bewiesen Crandall, Doenias, Norrie und Young, daß die 1262612-stellige Zahl F22 zusammengesetzt ist. Mehr ist bisher nicht bekannt.

F23

Den ersten Primfaktor 167772161 = 5*225 + 1 fand Pervushin bereits 1878. Mayer, Papadopoulos und Crandall zeigten dann 2000, daß der restliche Faktor C2525215 zusammengesetzt ist.

F24

1999 bewiesen Mayer, Papadopoulos und Crandall, daß die 5050446-stellige Zahl F24 zusammengesetzt ist. Mehr ist bisher nicht bekannt.

F25

Es sind drei Primfaktoren bekannt 48413*229 + 1 (entdeckt 1963 von Wrathall), 1522849979*227 + 1 (entdeckt 1985 von Gostin) und 16168301139*227 + 1 (entdeckt 1987 von McLaughlin). Unbekannt ist die weitere Struktur.

F26

Es ist nur ein Primfaktor bekannt 143165*229 + 1 (entdeckt 1963 von Wrathall). Unbekannt ist die weitere Struktur.

F27

Es sind zwei Primfaktoren bekannt 141015*230 + 1 (entdeckt 1963 von Wrathall) und 430816215*229 + 1 (entdeckt 1985 von Gostin). Unbekannt ist die weitere Struktur.

F28

Es ist nur ein Primfaktor bekannt 25709319373*236 + 1 (entdeckt 1997 von Taura). Unbekannt ist die weitere Struktur.

F29

Es ist nur ein Primfaktor bekannt 1120049*231 + 1 (entdeckt 1980 von Gostin und McLaughlin). Unbekannt ist die weitere Struktur.

F30

Es sind zwei Primfaktoren bekannt 149041*232 + 1 (entdeckt 1963 von Wrathall) und 127589*233 + 1 (entdeckt 1963 von Wrathall). Unbekannt ist die weitere Struktur.

F31

Es ist nur ein Primfaktor bekannt 5463561471303*233 + 1 (entdeckt 2001 von Kruppa und Forbes). Unbekannt ist die weitere Struktur.

F32

Es ist nur ein Primfaktor bekannt 1479*234 + 1 (entdeckt 1963 von Wrathall). Unbekannt ist die weitere Struktur.
Mit F33 beginnt, wie oben schon erwähnt, die Liste der Fermatschen Zahlen, deren Struktur noch vollständig unbekannt ist. Das sporadische Wissen über bekannte Primfaktoren p = k*2n + 1 noch größerer Fermatscher Zahlen Fm wird durch die folgende Tabelle wiedergegeben.

m k n Entdeckungsdatum Entdecker
36 5 39 1886 Seelhoff
36 3759613 38 1981 Gostin, McLaughlin
37 1275438465 39 1991 Gostin
38 3 41 1903 Cullen, Cunningham, Western
38 2653 40 1963 Wrathall
39 21 41 1956 Robinson
42 43485 45 1963 Wrathall
43 212675402445 45 2000 Samidoost, Durman
48 2139543641769 50 2001 Bodschwinna, Durman
52 4119 54 1963 Wrathall
52 21626655 54 1982 Keller
55 29 57 1956 Robinson
58 95 61 1957 Robinson
61 54985063 66 1986 Gostin
62 697 64 1977 Shippee
63 9 67 1956 Robinson
64 17853639 67 1986 Gostin
66 7551 69 1977 Shippee
71 683 73 1977 Shippee
72 76432329 74 1986 Gostin
73 5 75 1906 Morehead
75 3447431 77 1982 Gostin
77 425 79 1957 Robinson, Selfridge
77 5940341195 79 1957 Taura
81 271 84 1957 Robinson, Selfridge
88 119942751127 90 2001 Nohara, Durman
90 198922467387 92 26.03.2001 Grobstich, Durman
91 1421 93 1977 Shippee
93 92341 96 1979 Baillie
94 482524552001 97 18.04.2001 Grobstich, Durman
99 16233 104 1979 Gostin, McLaughlin, Suyama
107 1289179925 111 1992 Gostin
116 3433149787 120 1999 Taura
117 7 120 1956 Robinson
122 5234775 124 1986 Gostin
125 5 127 1956 Robinson
133 88075576149 135 2001 Samidoost, Durman
142 8152599 145 1986 Gostin
144 17 147 1956 Robinson
146 37092477 148 1987 Gostin
147 3125 149 1979 Gostin, McLaughlin
147 124567335 149 1990 Gostin
150 1575 157 1956 Robinson
150 5439 154 1980 Gostin, McLaughlin, Suyama
164 1835601567 167 1993 Gostin
172 20569603303 174 2001 Durman
178 313047661 180 1991 Gostin
184 117012935 187 1990 Gostin
201 4845 204 1980 Gostin, McLaughlin
205 232905 207 1984 Keller
207 3 209 1956 Robinson
215 32111 217 1980 Suyama
226 15 229 1956 Robinson
228 29 231 1956 Robinson
230 372236097 232 2000 Durman
232 70899775 236 1991 Gostin
250 403 252 1957 Robinson, Selfridge
251 85801657 254 1991 Gostin
255 629 257 1979 Baillie
256 36986355 258 1991 Gostin
256 36986355 258 1991 Gostin
259 36654265 262 1991 Gostin
267 177 271 1957 Robinson, Selfridge
268 21 276 1956 Robinson
275 22347 279 1984 Keller
284 7 290 1956 Robinson
284 1061341513 286 2000 Durman
286 78472588395 288 02.11.2002 Vasily Danilov, Durman
287 5915 289 1980 Suyama
297 72677552745 301 13.02.2003 Vasily Danilov, Durman
298 247 302 1979 Baillie
301 7183437 304 1990 Gostin
316 7 320 1956 Robinson
329 1211 333 1981 Suyama
334 27609 341 1984 Keller
338 27654487 342 1990 Gostin
343 4844391185 345 2001 Vasily Danilov, Durman
353 18908555 355 1990 Gostin
370 573230511 373 2000 Durman
375 3733251 377 1986 Gostin
376 810373 378 1986 Gostin
380 321116871 385 2000 Durman
398 120845 401 1984 Keller
416 8619 418 1981 Suyama
416 38039 419 1984 Keller
417 118086729 421 1992 Gostin
431 5769285 434 1990 Gostin
452 27 455 1956 Robinson
468 27114089 471 1992 Gostin
480 5673968845 484 2001 Vasily Danilov, Durman
544 225 547 1979 Baillie
547 77377 550 1986 Gostin
556 127 558 1976 Matthew, Williams
569 6616590375 575 25.02.2003 Sergey Kuzmin, Durman
579 63856313 581 1999 Taura
620 10084141 624 1992 Gostin
635 4258979 645 1991 Gostin
637 11969 643 1984 Keller
642 52943971 644 1999 Taura
667 491628159 669 2001 Taura
692 717 695 1979 Atkin, Rickert
723 554815 730 1991 Gostin
744 17 747 1976 Matthew, Williams
851 497531 859 1988 Gostin
885 16578999 887 1992 Gostin
906 57063 908 1986 Gostin
931 1985 933 1980 Keller
971 541664191 976 2002 Komin, Durman
1069 137883 1073 1992 Gostin
1082 82165 1084 1991 Gostin
1114 11618577 1116 2001 Gostin
1123 25835 1125 1987 Gostin
1225 79707 1231 1991 Gostin
1229 29139 1233 1987 Gostin
1394 62705223 1396 2001 Taura
1451 13143 1454 1986 Gostin
1551 291 1553 1979 Atkin, Rickert
1598 10923781 1600 2000 Taura
1849 98855 1851 1992 Gostin
1945 5 1947 1957 Robinson
1990 150863 1993 1995 Taura
2023 29 2027 1979 Atkin, Rickert, Cormack, Williams
2059 591909 2063 2000 Ballinger, Gallot
2089 431 2099 1983 Suyama
2456 85 2458 1979 Atkin, Rickert
3310 5 3313 1979 Atkin, Rickert, Cormack, Williams
3506 501 3508 1986 Gostin
3723 13308899 3725 2002 Fougeron
4250 173373 4252 1999 Kerchner
4258 1435 4262 1993 Gostin
4332 2466157 4334 2002 Fougeron
4724 29 4727 1979 Cormack, Williams
5320 21341 5323 1998 Taura
5531 1503975 5533 2002 Gostin
5792 8872947 5794 25.02.2003 Fougeron
5957 421435 5960 2001 Gostin
6208 763 6210 1993 Gostin
6355 115185 6358 2000 Kerchner
6390 303 6393 1993 Gostin
6537 17 6539 1979 Cormack, Williams
6835 19 6838 1978 Keller
6909 6021 6912 1993 Gostin
7181 168329 7187 2000 Gostin
7309 145 7312 1992 Dubner
8239 7473 8242 1998 Prethaler, Gallot
8555 645 8557 1993 Dubner
9322 8247 9324 1999 Kerchner
9428 9 9431 1983 Keller
9448 19 9450 1980 Keller
9549 1211 9551 1998 Taura
9691 260435 9693 2001 Gostin
11695 203355 11703 2001 Gostin
12185 81 12189 1993 Dubner
13250 351 13252 1996 Taura
13623 48265 13626 2000 Gostin
14252 1173 14254 1997 Taura
14276 157 14280 1996 Taura
14528 17217 14530 2000 Gostin
15161 55 15164 1993 Dubner
17906 135 17909 1996 Taura
18749 11 18759 1992 Dubner
18757 33 18766 1993 Dubner
19211 13323 19220 2001 Gostin
22296 4777 22298 2001 Gostin
23069 681 23071 1997 Demichel, Gallot, Taura
23288 19 23290 1992 Dubner
23471 5 23473 1984 Keller
24651 99 24653 1996 Taura
25006 57 25010 1993 Young
28281 81 28285 1996 Taura
35563 357 35567 2000 Melo, Gallot
41894 4935 41897 2001 Fougeron
43665 2495 43667 2001 Fougeron
49093 165 49095 1998 Gallot
50078 7619 50081 2002 Axelsson
63679 169 63686 1998 Dubner, Gallot
83861 99 83863 1998 Gusev, Gallot
90057 189 90061 1999 Morenus, Gallot
91213 585 91215 2001 Axelsson
94798 21 94801 1995 Young
95328 7 95330 1994 Young
104448 927 104451 2001 Oleynick
113547 39 113549 1999 Renze, Gallot
114293 13 114296 1995 Young
125410 5 125413 1995 Young
142460 159 142462 2000 Melo, Gallot
146221 57 146223 2000 Lewis, Gallot
157167 3 175169 1995 Young
213319 3 213321 1996 Young
270091 63 270094 2002 Taura, Gallot
282717 51 282719 2002 Odermatt, Gallot
303088 3 303093 1998 Young
382447 3 382449 1999 Cosgrave, Gallot
2145351 3 2145353 21.02.2003 Cosgrave, Jobling, Woltman, Gallot