Primality Certificate for (4018^4177-1)/4017

This certificate uses a theorem of Brillhart, Lehmer and Selfridge to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 37.967644% factorization of N-1:

From this partial factorization, we use sufficient of the largest prime factors of N-1 so that their product F is at least N ^1/3 :

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 33.487778%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w^(N-1) ≡ 1 mod N and GCD(w^(N-1)/p-1,N) = 1. In this case, w = 3 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F³>N, N can have no more than two prime factors.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 1 0552556309 6768388420 9969938140 3982415254 7235116185 0353572886 6737815610 7145123882 4028834214 5404015843 9859586934 4801503533 8315249855 9571248621 7543462143 3829607761 6908291836 1157506809 5531402692 7210931597 1635972060 2702835003 3239662758 5432949855 3391251066 7097006075 5870016609 8960199841 6187717214 1090405188 2026387463 1259441283 5951996231 4679655513 5207879202 5901915662 8668683641 0786484116 6473471396 4430726314 3776046875 3711125578 3225729625 4237563533 3374035851 9858939458 4659781711 2589276268 0124403231 6212677328 6796066431 3343823743 3602932480 8813388365 5791414537 8723370057 3810999519 8746029657 0959943729 1939124373 2422347113 0130894195 8801175104 6189099127 0138555230 4542586222 3038481138 2896329214 2694505144 0210103055 4702594139 2891876790 3053663680 7879319944 1915511011 1095145244 7215246409 4196395874 0051258130 8775820399 8476023488 1359402184 1509916477 9249558318 6306560872 3061599864 2081018511 4121925268 9630845010 0941108877 6243532580 7078860633 6403088115 0568778265 7838698278 7392206884 8365306034 9608973815 3312802918 0852169615 2275992140 0368367507 8122609845 0363913970 3263377938 7317832442 9232520256 3336154378 8510942204 2942856147 7595714310 5303571257 8222224073 1672216064 3546785604 1968447142 1269879481 3490573200 9284143326 0263558857 8967049282 7289046878 2112436846 1940485959 1277029842 7323640991 6817162465 9190907636 0075615291 3753777956 9962148311 7442504280 2904155802 1077627892 0292314965 0941980393 5449802528 6104707533 4214669732 1720527252 3575633513 7130100490 2829104257 0042323120 8917289004 7498714098 4980013080 7303452141 1205405942 8069423685 1079861878 2284608462 1123096568 9727524512 0031104903 5986784538 1943405745 6623504499 0164495166 8086617395 8884726646 8890064862 5585958535 4378987414 8509959237 5006211029 4584762425 1120317655 6642473791 6526177464 6067862735 3210640062 2619180593 4481848613 2525085706 5887734936 9047233217 9288224077 8013220021 6049567704 4954132243 2309764483 4379587055 0758516375 4445981803 4493317710 2958194245 9911666218 7120750838 1236083620 4438502996 8056421781 6256363412 7940903323 6878219414 4108091319 7742778386 5504064032 3432195316 7077962067 6908172236 6466255246 5713600315 0800917295 3283099795 3374509839 7854369145 6850522583 5381404859 6366882277 3657886692 7351451110 5154056033 2289496812 9474004002 8971361767 2117650226 5992142047 0999101858 8163783552 0987599974 9542069768 9977735016 3044261899 7303563873 5954590948 0672967393 8458271518 5107614439 8999507842 2643440874 9716664223 7507135535 2548786422 0839672985 9422012432 6260187666 6430578625 4186466469 9314659356 4099373509 2143940383 8109437734 8303142385 5122624739 2481180325 1253571103 0861990999 3277846748 1756566160 0152789125 9915563508 3938842938 2120367833 6108475626 2469208217 8684431386 6542569905 2972529373 5403934247 4014621077 1199432038 1464668129 9903182264 6294747364 2871079085 0287266128 1609461450 1974705063 4973957699 6439197283 0922769488 3010030581 6922810502 8472112282 8487364411 3301065902 0657359202 1464229814 8494929932 8150729284 6841626020 5289962766 0549939537 2723478424 5395340138 4727066941 7991680337 4085233480 5234327574 7937992888 6430234819 2739225156 1801040022 5253289646 8242177302 0219645837 8431458783 4249265747 9729866369 8747979796 5104761043 6887882855 7311089903 7032457045 8876782628 4990362590 4696639839 3786862122 6954613073 7665986405 5046507161 0899550686 1695276180 4876404110 9463076667 2726236861 0177943405 2701311358 1864517064 5939429869 5145835247 4814285047 7982829732 6650259836 6989469515 5005937603 6270265821 4302072572 4266736898 7725341847 7368432432 0539564265 4421146059 5938104959 4782281161 2174639705 2623050762 0711711772 6539310432 7040089400 3997256980 6379051163 5627215204 6611640872 8783286134 5448617521 9327880494 0654496009 5518080812 1063357723 5816774649 6905238197 2066973087 0677569554 1371539766 8630932006 6515110874 0516316544 7487272870 3926804548 1670748173 1530300811 0288187590 3199926459 2704461906 6127270943 0298491288 4127094769 0941663279 2525685089 7898715200 6429452904 3076981103 2646753503 1598010419 2189216996 9367676440 7573712695 0527628871 5318562327 1999380674 3334552732 3639607908 7370979287 4825032521 4434240739 0195667292 7417183880 4329775241 8840052345 6717039844 4239023032 8698613904 3621254010 6311669345 6966814013 0764270450 1198412420 3498088273 0200360422 1821054396 9189954019 5395155771 5714218698 5099251400 9915365591 9030048864 6265230478 5621777108 5331864537 9117775533 9580053468 8073325765 4741947046 5460908144 8080498029 9144135815 9009564572 9063809776 8737804096 1787461764 9133110608 5530178962 2267139488 5610649162 2872667232 1118733943 2894314158 7344401886 0631910055 6940302892 7069829162 4439083523 2678213529 9653855877 7139177736 3758967687 2481560239 7121275356 6597935441 1318266324 1756759397 1092758046 0000346090 4878718331 1845193140 8031673783 5326529872 0259687126 8896151173 0955619686 4011080355 7007277347 8085290011 7203559332 3267305538 6260200937 3133598064 3734123365 2796664727 7196805741 1651491150 2248438492 4447404362 9505617377 1181221980 3294329523 0013485335 6611970165 9524049126 2077911311 1367556684 5159477934 6886326079 3831700711 7367074138 6243769664 9929870080 9521668571 7370799031 5129586679 9179780931 4870209274 1220372887 3477891521 5838184405 4959705928 9829276076 4644159020 7931005425 8269557545 1546489482 1068779021 5264354230 8194957818 3215564503 9317256042 6263169551 7457391489 7091414192 6994834798 7006247950 4752201697
• c₂= 1 9624733061 6003098882 0049781713 1077510195 7818849464 0431266568 0229281580 3535107282 4374167505 7196949235 1268158284 8077673363 8437441291 1137780275 4596611060 6862866260 0038364347 4289165989 9302530111 3994258065 5220441948 0611674805 7677219806 9347467754 6898561267 3353884331 9069265405 2934496288 2580385038 6040783189 6605591173 3399051000 7025851578 4885110594 5236341434 9553034425 9459098837 9698791553 6896134228 7105083847 5318383028 6949774838 2545097579 7071235206 6666098703 1075362463 2737757814 8524751265 5851071269 2726447664 6364165918 2256276471 3466951917 1395692985 7572698539 5772778126 5254669822 7211682150 5213177906 9837959061 4110541024 3648076336 4906993073 2938706234 2995210072 8009047050 9951618841 9520244788 0425396872 3840832680 6248142341 3759352784 9376306070 2095989433 6661238760 9169475847 4996674902 3296627868 6411771485 8192188020 8491849631 9068628735 3990397476 2854824487 5254927530 5168097094 6771303133 7396701556 2682032297 9385360302 0237337622 4712880264 8898374099 7204146785 7232423072 8217440821 1917793099 4396394441 8648796105 8168900671 0534169321 1896796380 2120129076 5891196795 5405461945 4885519768 9715564373 2181721577 8218765172 4822469976 4661083593 6244542654 2221834460 0899736000 5197169167 8395329560 1705154553 1670745464 8670902745 5924706156 1587484387 4459455657 3006958119 5468107613 5264789726 4619899142 1244401004 1589180021 2685522151 9900097570 3968621332 2580994305 2644619477 4767024269 8636065905 7842158737 6769724321 0225833296 1444872686 5522575259 8527661847 8356186928 4738689798 4141055262 2832448880 2423229442 4446350280 0611795992 7860455905 1459257301 3900784004 4665105923 6347587244 2078954122 5780028169 1986021682 7615754985 6474099344 9077187562 0847982069 0965445658 6759145085 5779156183 8200150294 3675198832 3707825116 3134218287 1132722611 7413052703 7165554690 9294959716 2803324394 5746579843 3686311492 4178745860 2457119857 4446921839 0838242451 0060255728 3481750404 6571786941 8733812981 2344691253 4573464085 3738585472 8223305674 8074451939 5568976364 5873298154 4127949392 3238288603 3417750028 6928187266 2580036543 1089446782 3184210552 2945730094 7252025020 0345869140 9353958745 2188691854 8548348354 6466142472 7127514880 5456651263 0802718485 2790481034 5398156719 8776032896 3893099334 6091455042 7407165159 8651615621 9623580441 6509867374 2248987529 3451621371 4198695413 4365717520 6216091385 7993435901 6785032204 2746662254 9163627372 0159848089 8609302397 0750270008 9549556186 0417163082 8520694038 3735253644 8285996081 2635760709 5669985058 6509259558 5036668157 7417978646 0415444167 9316764838 7534775861 3632630314 3879261803 2319128712 2416629500 4672466399 6518138879 7631146060 2286408514 9173672840 0894963574 8063699197 1298683019 9717176217 5315669935 5923265795 2932097807 3733670081 4419502371 3004087258 7538294565 4850877439 0605104276 6018530231 8600339617 7830322312 2952378267 9938413744 4126062618 3572530982 5864645281 5493215607 3281084809 3644887164 5503267214 2260897542 7334869470 9778410166 0221718559 0501865094 0989171152 9665824023 1675267767 8392983910 5401268007 8804698062 8787222155 4193645232 1114719325 8852619920 8122509986 8516142549 7891544944 6136840390 9063797514 8161185030 3946154211 4669902307 7446298416 4391928325 4258783037 1371489753 9984930511 1382597953 0468445464 4932588719 8845431877 1381634603 8548852354 1322612032 6727251439 4697374754 6930004637 4149234819 7110257956 8109618569 8485184696 9306900434 9181031434 2742861679 7077494283 0671383343 7982554426 5527150899 2686253713 5144821919 6169864652 7230499293 5990147994 6177511617 9299559651 8709331245 1087924354 8329383268 5768044788 9699135803 7103552308 2720097438 6392673679 1032737007 9281005158 4084469464 4145929524 4465981026 2894764086 1187014098 1875850848 1864123571 0333982951 5793166861 6670372023 6302756513 4886170931 4172511433 7070106981 6959641442 6402839817 2244551453 5511171239 0767593371 0397900898 0497183968 5720895637 5850353334 3130016346 6489002097 6205112048 9405098223 4758655091 4955189980 7664862049 8328328457 6098565603 0960291350 3711227805 7410432625 1134314129 5330367002 5267298955 0197647313 0680242219 1576596753 9241949285 6990627139 8450467848 1023347527 4871344096 6070037615 3443692700 2390021692 3928343642 7063673256 8454281256 2320414319 6792649311 9954291386 1628854992 4606771010 4583358361 2282291343 1868164532 0638276094 1783757293 8729903474 1013744121 4043431768 5988115337 0348406359 3890463174 8604378529 2416193567 6148757812 2186377857 4929733874 4641676629 4990097043 2450591654 9433133370 2736613912 1740905557 8588183129 3203871871 8825480257 8187857148 5004505347 6711157499 1029082579 7568209436 6014293002 3767379020 3158958434 2166410917 5830001700 7119463491 5808825139 8035974527 0835295516 9670523036 6714442205 0437281091 6159724559 8826665433 3757760425 2367415360 7443137674 7195908096 5362815176 7948011740 0578563422 9627286652 3988543645 9118507837 1056369250 3844299743 4553086164 3667625794 3042478083 9309445639 1556294267 5790941652 3639170700 1755758687 6438866406 9163978116 2676618591 2597872813 5198781497 6365864619 3950175352 9811393579 7925965810 6587361757 2108928624 2513062526 5857732958 5585408953 0452352282 7028995314 2895860283 8690426813 4107834665 6459477754 4955824487 8260605302 2083175846 0128689298 6184039399 8948785377 0587448961 2088507166 2056652061 9424971945 8376220567 8020771056 2433845832 7766230621 5073976715 4340601709

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square (given 2F³ > N).

Here, c₁²-4·c₂ is ≡ 13 (mod 64) and therefore cannot be a square and N is prime.