Factors of Generalized Fermat Numbers

These numbers have the form 23n + 1 and 23n - 1.

The problem here is to find factors of these numbers.

Since 23n+1 + 1 = (23n + 1) (43n - 23n + 1)

the first factor of the RHS has the same form of the LHS, so we are interested on factors of the second expression.

In the same way 23n+1 - 1 = (23n - 1) (43n + 23n + 1)

Notice that 43n - 23n + 1 is always multiple of 3, because 43n = 13n = 1 (mod 3), 23n = 2odd = 2 (mod 3), so 1 - 2 + 1 = 0 (mod 3).

The numbers 43n + 23n + 1 are known as Generalized Fermat Number Fn,2.

Prime factors of (43n - 23n + 1) / 3
ExponentPrime factorsDiscoverer
0No prime factors 
12*32+1 = 19 
23230*33+1 = 87211 
32*34+1 = 163 
1672*34+1 = 135433 
3358160*34+1 = 272010961 
46*35+1 = 1459 
574*35+1 = 139483 
4291937 2147783270*35+1 = 1042940743 1911334611 
377829239 3426209464*35+1 = 9 1812505160 2568899753 
5312568*36+1 = 227862073 
4267065754*36+1 = 3110690934667 
2 9752059431 0685684488*36+1 = 2168 9251325248 9863991753 
15 1179583137 9924450952*36+1 = 11020 9916107596 4924744009 
(78 digits) 
68*37+1 = 17497 
2478*37+1 = 5419387 
2766*37+1 = 6049243 
11338334*37+1 = 2 4796936459 
84279294*37+1 = 1 84318815979 
78*38+1 = 52489 
4410*38+1 = 28934011 
80183520*38+1 = 526084074721 
440 5633237922*38+1 = 2890535 9674006243Philippe Strohl (7/2003)
1107 8656127098*38+1 = 7268706 2849889979Philippe Strohl (7/2003)
862*39+1 = 1220347 
141 0521316064*39+1 = 2776329 1064087713Philippe Strohl (7/2003)
9400455322*310+1 = 2364 6486308779Dario Alpern
13760*314+1 = 3635056441Dario Alpern
33493592*314+1 = 16019 8812234649Dario Alpern
145659504816*315+1 = 8120770 8270836113Dario Alpern (10/2005)
27622252160*315+1 = 39634912 7374389121Dario Alpern (12/2005)
152*316+1 = 86093443Dario Alpern
1638480104*317+1 = 4969326902816953Dario Alpern
1764074*318+1 = 24823580412187Dario Alpern
1833158976*319+1 = 3853940 0089977793Dario Alpern
134770686*319+1 = 15663877 5218956363Dario Alpern
2040749616*321+1 = 42625537 6246620049Dario Alpern
23228978058*324+1 = 6467016678 5259533899Dario Alpern (10/2005)
27578221330*328+1 = 1 322784935944 1514518131Dario Alpern (10/2005)
286*329+1 = 41178 2264189299Dario Alpern
101256*329+1 = 694923749 0458593049Dario Alpern
291373422682*330+1 = 2827 7555084144 9107428619Dario Alpern (10/2005)
303028366*331+1 = 18 7054111241 0831440603Dario Alpern (10/2005)
3132*332+1 = 5929664 6043258913Dario Alpern
3200*332+1 = 592966460 4325891201Dario Alpern
326912*333+1 = 3842422663 6031774977Dario Alpern
5 3257453584*333+1 = 2960614 1009397550 8931344433Dario Alpern (1/2006)
33234402*334+1 = 39 0916474476 5243106739Dario Alpern
3915098*340+1 = 1835 5643310084 1511037499Dario Alpern
42110*343+1 = 361 0826641339 9078538971Dario Alpern
436152*344+1 = 60583 1059023357 6304683913Dario Alpern
4696*347+1 = 25525 2617845992 0315627553Dario Alpern
4761406648*348+1 = 4 8981898922 3354715405 5937023929Dario Alpern (10/2005)
5054*351+1 = 1162994 7400608011 9380780339Dario Alpern
518*352+1 = 516886 5511381338 6391457929Dario Alpern
5312202*354+1 = 7095430909 1109480834 2140842139Dario Alpern
542544*355+1 = 4437987928 0720173555 7057769809Dario Alpern
55211435592*356+1 = 110654 3166109387 2738317683 8841455433Dario Alpern (10/2005)
5614*357+1 = 219806005 8714914256 2967483883Dario Alpern
24*357+1 = 376810295 7796995867 9372829513Dario Alpern
574663458*358+1 = 21965 4873542025 7844537383 2096296563Dario Alpern (10/2005)
586*359+1 = 847823165 5043240702 8588866403Dario Alpern
5962080*360+1 (34 digits)Dario Alpern
3587982080*360+1 (39 digits)Dario Alpern (10/2005)
65860704*366+1 (38 digits)Dario Alpern
758*376+1 (38 digits)Dario Alpern
84203214*385+1 (46 digits)Dario Alpern
8560037080*386+1 (49 digits)Dario Alpern (10/2005)
8762192*388+1 (47 digits)Dario Alpern
9319388858*394+1 (53 digits)Dario Alpern (10/2005)
9423922928*395+1 (53 digits)Dario Alpern (10/2005)
99260280*3100+1 (54 digits)Dario Alpern
11030*3111+1 (55 digits)Dario Alpern
11132*3112+1 (55 digits)Dario Alpern
11892774*3119+1 (62 digits)Dario Alpern
1258800130*3126+1 (68 digits)Dario Alpern (10/2005)
1306*3131+1 (64 digits)Dario Alpern
1361190881376*3137+1 (75 digits)Dario Alpern (3/2006)
14414*3145+1 (71 digits)Dario Alpern
161616400864*3162+1 (87 digits)Dario Alpern (5/2006)
163104620466*3167+1 (87 digits)Dario Alpern (11/2005)
166150*3167+1 (82 digits)Dario Alpern
16756*3168+1 (82 digits)Dario Alpern
175407078202*3176+1 (93 digits)Dario Alpern (6/2006)
17654*3177+1 (87 digits)Dario Alpern
1846222*3185+1 (93 digits)Dario Alpern
20296*3203+1 (99 digits)Dario Alpern
20682880766*3203+1 (107 digits)Dario Alpern (8/2006)
2084104*3209+1 (104 digits)Dario Alpern
2148256*3209+1 (107 digits)Dario Alpern (10/2005)
21111128*3212+1 (106 digits)Dario Alpern
2141062270*3215+1 (109 digits)Dario Alpern (10/2005)
2212208*3222+1 (110 digits)Dario Alpern
22278*3223+1 (109 digits)Dario Alpern
238968*3239+1 (118 digits)Dario Alpern
281723538*3282+1 (141 digits)Dario Alpern (10/2005)
2859960*3286+1 (141 digits)Dario Alpern
2861127030*3287+1 (143 digits)Dario Alpern (10/2005)
30881816*3309+1 (153 digits)Dario Alpern
3145826134*3315+1 (158 digits)Dario Alpern (10/2005)
3192*3320+1 (153 digits)Dario Alpern
32516950610*3326+1 (163 digits)Dario Alpern (1/2006)
33024*3331+1 (160 digits)Dario Alpern
3333108970*3334+1 (166 digits)Dario Alpern (1/2006)
362109064*3363+1 (179 digits)Dario Alpern
398528*3399+1 (194 digits)Dario Alpern
405413610*3406+1 (200 digits)Dario Alpern (10/2005)
499316072*3500+1 (245 digits)Dario Alpern (10/2005)
525168074*3526+1 (257 digits)Dario Alpern
67914922*3680+1 (329 digits)Dario Alpern (10/2005)
6946*3695+1 (333 digits)Dario Alpern
7061974806*3707+1 (344 digits)Dario Alpern (1/2006)
72438102*3725+1 (351 digits)Dario Alpern (10/2005)
7812*3782+1 (374 digits)Dario Alpern
7974650*3798+1 (385 digits)Dario Alpern (10/2005)
8206*3821+1 (393 digits)Dario Alpern
9367262*3937+1 (451 digits)Dario Alpern (10/2005)
9798*3980+1 (469 digits)Dario Alpern
122326*31224+1 (586 digits)Dario Alpern
12512*31252+1 (598 digits)Dario Alpern
136614*31367+1 (654 digits)Dario Alpern
140748*31408+1 (674 digits)Dario Alpern
14532*31454+1 (695 digits)Dario Alpern
1530558*31531+1 (734 digits)Dario Alpern (10/2005)
187029758*31871+1 (898 digits)Donovan Johnson (9 nov 2007)
20561296*32057+1 (985 digits)Dario Alpern (10/2005)
2183458*32184+1 (1045 digits)Dario Alpern (10/2005)
22522512*32253+1 (1079 digits)Dario Alpern (11/2005)
240814*32409+1 (1151 digits)Dario Alpern
245148*32452+1 (1172 digits)Dario Alpern
262332*32624+1 (1254 digits)Dario Alpern
2703210*32704+1 (1293 digits)Dario Alpern (11/2005)
2789210*32790+1 (1334 digits)Dario Alpern (11/2005)
45998*34600+1 (2196 digits)Dario Alpern (11/2005)
54792*35480+1 (2615 digits)Dario Alpern (12/2005)
78406*37841+1 (3742 digits)Dario Alpern (12/2005)
9409160*39410+1 (4492 digits)Dario Alpern (1/2006)

Exponents 0 to 5 are completely factored.
For exponent 6 to 9 I ran 300 ECM curves with B1 = 50000 and 700 with B1 = 250000.
For exponents 10 and 11 I ran 250 ECM curves with B1 = 50000.
All cofactors for exponents 6 to 12 were found composite by Donovan Johnson on 9 November 2007.

The limits in the search for factors are:

Exponents 11 to 37: 2*1011
Exponents 38 to 64: 2*1010
Exponents 65 to 200: 5*109
Exponents 201 to 283: 2*108
Exponents 284 to 400: 2*107
Exponents 401 to 801: 2000000
Exponents 802 to 1400: 200000
Exponents 1401 to 2900: 20000
Exponents 2901 to 5000: 2000
Exponents 5001 to 10000: 200

Factors found so far: 137

Prime factors of 43n + 23n + 1
ExponentPrime factorsDiscoverer
02*31+1 = 7 
18*32+1 = 73 
29728*33+1 = 262657 
332*34+1 = 2593 
878*34+1 = 71119 
1205998*34+1 = 97685839 
42*35+1 = 487 
68 945611600*35+1 = 1675 3783618801 
794 122245632*35+1 = 19297 1705688577 
1527979 4910498594*35+1 = 371299016 3251158343 
5110*36+1 = 80191 
134*36+1 = 97687 
520*36+1 = 379081 
911835396 9088590993 8096624124 8655269152*36+1Robert Silverman
(90 digits)Robert Silverman
618*37+1 = 39367 
3477936*37+1 = 7606246033 
120345960*37+1 = 26 3196614521 
241912920*37+1 = 52 9063556041 
732*38+1 = 209953 
198*38+1 = 1299079 
1067874826 9716005072*38+1 = 700 6326739760 6709277393 
87192*39+1 = 141560137 
298 0726001840*39+1 = 5866962 9894216721 
14 8184916806 7520103946 5100468042*39+1Dario Alpern (9/2005)
98*310+1 = 472393 
686184*310+1 = 40518479017 
1151958*310+1 = 6 8021967943Yannick Saouter (1995)
2819752928*310+1 = 16650 3590645473Donovan Johnson (9 Nov 2007)
106175 5910828066*311+1 = 1093987433 5459407703Donovan Johnson (9 Nov 2007)
11166*312+1 = 88219207Yannick Saouter (1995)
122735946*313+1 = 436 1981634559Yannick Saouter (1995)
133 5198840558*314+1 = 16835496 3224856703Dario Alpern (11/2005)
1418*315+1 = 258280327Yannick Saouter (1995)
1626*317+1 = 3357644239Yannick Saouter (1995)
1698664*317+1 = 21936 5745842233Yannick Saouter (1995)
1731078*318+1 = 1204 0253957143Yannick Saouter (1995)
19190*320+1 = 66 2489036191Yannick Saouter (1995)
1677086*320+1 = 584763 7303935487Yannick Saouter (1995)
218*322+1 = 25 1048476873Yannick Saouter (1995)
23126*324+1 = 3558 6121596607Yannick Saouter (1995)
261386*327+1 = 1056907 8114191983Yannick Saouter (1995)
292483478*330+1 = 5 1132609695 2154709223Yannick Saouter (1995)
1 3802075504*330+1 = 28417 2495077438 3172378097Dario Alpern (10/2005)
5 7791187848*330+1 = 118986 9309111924 2074625353Dario Alpern (1/2006)
30298*331+1 = 18406667 2092616207Yannick Saouter (1995)
33288*334+1 = 480302832 9503971873Yannick Saouter (1995)
3419 5296351960*335+1 = 97709782 4075685982 2208875721Dario Alpern (1/2006)
39128*340+1 = 15 5618117875 9286886529Yannick Saouter (1995)
15152*340+1 = 1842 1294703563 0585192753Yannick Saouter (1995)
4288*343+1 = 288 8661313071 9262831177Dario Alpern
44287122*345+1 = 8482481 7293028847 3221775447Dario Alpern
45539382*346+1 = 47805092 8885440534 6124375879Dario Alpern
4640160*347+1 = 10678067 8465573333 2037525921Dario Alpern
476288*348+1 = 5015713 9406737434 2020813969Dario Alpern
501289566968*351+1 = 2777 3325939632 5098361020 2554605097Dario Alpern (10/2005)
556*356+1 = 31400857 9816416322 3281069127Dario Alpern
572304*358+1 = 10 8521365184 5534809965 9374899457Dario Alpern
642*365+1 = 20 6021029217 5507490794 7094535687Dario Alpern
602*365+1 = 6201 2329794482 7754729207 5455241487Dario Alpern (10/2005)
75923680232*376+1 (46 digits)Dario Alpern (11/2005)
7626*377+1 (39 digits)Dario Alpern
8159425822*382+1 (47 digits)Dario Alpern (10/2005)
871140517862*388+1 (52 digits)Dario Alpern (1/2006)
9426*395+1 (47 digits)Dario Alpern
9522*396+1 (48 digits)Dario Alpern
9914008*3100+1 (52 digits)Dario Alpern
1023883390160*3103+1 (59 digits)Dario Alpern (2/2006)
103161129448*3104+1 (58 digits)Dario Alpern (10/2005)
115537432*3116+1 (62 digits)Dario Alpern (10/2005)
11814010*3119+1 (61 digits)Dario Alpern
120354*3121+1 (61 digits)Dario Alpern
121762630*3122+1 (65 digits)Dario Alpern (10/2005)
1298*3130+1 (63 digits)Dario Alpern
136379406664*3137+1 (74 digits)Dario Alpern (3/2006)
1582266*3159+1 (80 digits)Dario Alpern
16170*3162+1 (80 digits)Dario Alpern
2041362*3205+1 (101 digits)Dario Alpern
282154*3205+1 (104 digits)Dario Alpern (10/2005)
22154264*3222+1 (111 digits)Dario Alpern
225247968*3226+1 (114 digits)Dario Alpern (10/2005)
227192*3228+1 (112 digits)Dario Alpern
2461223920*3247+1 (124 digits)Dario Alpern (10/2005)
27310152*3274+1 (135 digits)Dario Alpern
28810*3289+1 (139 digits)Dario Alpern
315626280*3316+1 (157 digits)Dario Alpern (10/2005)
32924*3330+1 (159 digits)Dario Alpern
36332*3364+1 (176 digits)Dario Alpern
4307136*3431+1 (210 digits)Dario Alpern
43231890*3433+1 (212 digits)Dario Alpern
57132*3572+1 (275 digits)Dario Alpern
5752272*3576+1 (279 digits)Dario Alpern
626766514*3627+1 (306 digits)Dario Alpern (1/2006)
63050*3631+1 (303 digits)Dario Alpern
653224*3654+1 (315 digits)Dario Alpern
6662408*3667+1 (322 digits)Dario Alpern
56976*3667+1 (323 digits)Dario Alpern (10/2005)
76130*3762+1 (366 digits)Dario Alpern
78032*3781+1 (375 digits)Dario Alpern
7881069946*3789+1 (383 digits)Dario Alpern (1/2006)
8956*3896+1 (429 digits)Dario Alpern
100034*31001+1 (480 digits)Dario Alpern
10051422*31006+1 (484 digits)Dario Alpern (10/2005)
106826*31069+1 (512 digits)Dario Alpern
11542544*31155+1 (555 digits)Dario Alpern (10/2005)
120696*31207+1 (578 digits)Dario Alpern
128024*31281+1 (613 digits)Dario Alpern
15584336*31559+1 (748 digits)Dario Alpern (10/2005)
16548*31655+1 (791 digits)Dario Alpern
1734178*31735+1 (831 digits)Dario Alpern
212026*32121+1 (1014 digits)Dario Alpern
23436822*32344+1 (1123 digits)Dario Alpern (11/2005)
25058934*32506+1 (1200 digits)Dario Alpern (11/2005)
28124616*32813+1 (1346 digits)Dario Alpern (11/2005)
3709302*33710+1 (1773 digits)Dario Alpern (11/2005)
42162*34217+1 (2012 digits)Dario Alpern (11/2005)
527132*35272+1 (2517 digits)Dario Alpern (12/2005)
571970*35720+1 (2731 digits)Dario Alpern (12/2005)
622218*36223+1 (2971 digits)Dario Alpern (12/2005)
8757198*38758+1 (4181 digits)Dario Alpern (1/2006)

Exponents 0 to 5 are completely factored.
For exponent 6 to 9 I ran 300 ECM curves with B1 = 50000 and 700 with B1 = 250000.
For exponent 10 I ran 300 ECM curves with B1 = 50000.
All cofactors for exponents 6 to 12 were found composite by Donovan Johnson on 9 November 2007.

The limits in the search for factors are:

Exponents 11 to 37: 2*1011
Exponents 38 to 64: 2*1010
Exponents 65 to 200: 5*109
Exponents 201 to 283: 2*108
Exponents 284 to 400: 2*107
Exponents 401 to 801: 2000000
Exponents 802 to 1400: 200000
Exponents 1401 to 2900: 20000
Exponents 2901 to 5000: 2000
Exponents 5001 to 10000: 200

Factors found so far: 120

If you have a number that can be in these tables or you have any comment please fill the form.

In October 2005 I wrote a program to find factorizations of numbers of the form (2^pe+1)-1)/(2^pe-1) and (2^pe+1+1)/(2^pe+1). The numbers in this page can be factored using p=3. You can download it here. It includes both the source code and the Windows executable. The source code can be compiled in Linux also by typing:

gcc genferm.c -o genferm -lm

Last updated on February 4th, 2008.