Primality Certificate for (3894^3967-1)/3893

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 33.613245% 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.377690%

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 = 2 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₁= 237 0021608722 5976469545 6311464192 8615839960 0265463517 2587932130 0918579638 3514981806 1310168320 0093651335 9608189007 1455974109 9829750819 8213458807 3016761232 8306165590 0509859442 0430856005 0501068569 5736174872 8313184333 7591164033 8931798115 1849485900 6247454074 1437312243 1251635750 6572589024 7789605471 7531156106 1485549722 0981147681 8373462380 3860123361 1163767306 4330061720 2778528933 3843872014 2576207098 4866850717 7970775449 2582560749 4073358468 2696226594 0306774770 9540847667 4338729118 0982703383 8034862477 0486301406 4777639556 9897151107 4295815825 5372591043 1125320297 4785785119 3572538587 4690885909 3081952591 3112293392 6738076170 8654146945 0911804269 9209849291 8666366219 0485996222 0730624232 1568410994 7334871639 9792885947 7208790029 4692231615 5498339739 3270396327 8846252428 3930879151 0995837347 9913840680 5817505037 8259612432 7036957828 3271106601 9484387258 6539906644 3400113021 5559943766 8628795689 6433822406 0544620749 5531693371 8778041510 6887078270 6737014996 3716554024 7711742221 9198280506 2099092043 7310414643 4981014746 7833727445 3625384072 2014014886 7311168016 9489294117 9457075153 6461049200 6357965396 6752619326 5876070406 1847258142 0349576774 8662393077 2144438130 2868063758 9486322810 7555436035 4582152003 5072002225 3171323384 1303717555 2194286525 4869875144 6012557141 6452660508 9666500743 7841753264 3669163392 8512027001 2442867391 7494431245 2057289456 4722993511 0868675186 3285356645 4693634939 1976319143 4034382774 6162662583 7379934118 6412622565 0683885161 2237009396 2199034503 6313962558 3872629836 8048932043 8177077180 9585070495 1217173877 4208844811 1714391668 5333797508 6790861454 3016679882 6251192897 0795690382 5368077485 1446554205 8352040888 7337393768 2293310410 3408921691 5661695729 5953240917 7307025502 0347419372 3398966391 9159467493 0699471799 3687584141 0879027759 8998950339 9556655387 6772760649 5582938338 2557326021 1459837615 9023058582 9297060995 3731315439 8494627450 9399751685 8349526699 9639050708 8649648329 9827587681 4244002794 0697592814 4701350578 3712336909 1204139145 2839378881 3478539475 3258139021 8828229174 9635904200 8611270489 3385372934 6678793233 3745041525 9754791443 6234901897 7556855920 3781525554 0590306564 9419277854 0103948774 7582223639 5655716581 2658611088 2910898423 8409164466 8786288614 5169955174 1337447836 6204264321 5118765088 3499614395 2938582141 2436018429 3259133320 7700967998 3261864633 5586661727 8123140009 4667800973 4201980303 0706418643 5324082119 3082429819 8200481746 4090218258 0973158364 1328305262 9729169415 8228008541 7347906286 0173398497 5864392554 9868839579 4962353978 5625699819 2449297618 0656696277 2072174390 4704990689 8430024106 5678219983 3267858126 9235633204 5882019149 1816004234 6387515851 2999376363 3150779570 8618605714 0582909959 3948020851 6716818964 0913665985 4898186478 4572489952 7341032201 0666332704 5400410224 2828440897 6747359751 1117839509 3018789998 3680350450 6878826378 7029733034 8273661851 0471467200 1532191833 4533087991 4910621812 9912601029 3427980667 0646500313 8363233250 5559498547 3906829790 7423913482 7272039571 5443376186 2966672276 8264388443 0953090936 6724846544 7011451351 6823439324 5030388926 8689614845 6698025641 4115080096 1726117124 7580724058 6969241338 9136444989 0630988079 1891688830 7795592484 9282306422 9304921491 8475108485 9608449544 8577729711 5237570785 7780028114 1721368474 4280828480 5468286423 3268843573 7075364622 3425468170 6423186482 2089570985 2806700102 1491211434 9212137287 8524178000 1537265136 2500028522 1502134345 4172894308 2788156364 5487735023 0767747841 7043673759 3432721727 4976528877 9157565626 8981231988 0405678244 7981616638 6760104092 4313600921 2800790167 5583157335 6805866849 3357453005 2937522879 1525467232 5663511312 7774754227 1914881846 7562413346 6049001956 4091666237 1802580226 3688956091 1420638928 7970544461 2969621780 1454404882 7513115224 0956272253 2668918094 5443181851 1139003041 8486726080 5581061614 8189041330 3858608151 1396316923 2328962945 2408003255 9889976409 8246493875 5899244929 5821415609 6733087702 6587486293 8741232974 1159748751 4403995767 1278130486 1187402898 2066915851 0559981574 9929743211 3875181843 8265729320 4059578890 2006293440 3177012421 6134452256 3896998906 1315512792 4365258180 2776907057 6045102618 1579476741 1119475714 8509664383 5110586867 6469402371 7036392109 1509646427 7172923874 9359686293 0619690460 2000637450 1277669341 4531719544 7611890598 9776979443 8368054843 2706600821 4124754473 2983415249 0595789620 6852775324 4615001616 3759650253 3166166445 5532085351 4869010612 9438692704 3060784290 4551075061 4759882266 0737462292 5943707029 3586044735 8547294029 5538584418 6462968355 1901429929 7969934900 2012064574 9004452764 9833865973 9546615899 7751066155 1555872197 3917426282 0960327603 7396203594 9300803396 3767897553 5441101290 4578040825 8297415862 7260471579 7016332104 4823894590 5362717933 3337666369 4963904597 7579167542 1130354359 0470601970 4406663784 7744619248 1820027913 0596828585 5504241343 2354161548 1165170740 4813455508 5178049118 7480044212 9491076004 6624358039 1940247769 9293235782 5771463723 0552300210 6305089089 6972860760 6206236071 4270925517 9364442637
• c₂= 7433 3685108774 0629848626 5066962969 6592186829 3561100012 8043120847 1843000249 2539068490 5164871214 6261744970 2061764276 9397528501 9661991256 6470682044 4204514945 6723476683 2922544308 8677124576 7810675442 1273912777 8707333385 1027426525 2393860118 1670227023 1203441426 1919111926 0913082178 7934627216 7731869545 8131430385 1028022885 1977411666 0557805764 7647713637 8000705561 3077465250 9257819443 2031018580 8452879686 7220784149 8624150661 8677913905 6315224622 6778763801 3339120223 4749267945 2826897291 8834459083 1843102292 5959393619 3016348107 4398843398 5181757379 5774293027 1698341405 9184103172 1194295277 6329556227 8829824815 5560092930 5900384457 7014901635 6275016243 0346333767 0716605233 6458684805 5946691033 9944412341 7938741712 1483190687 6048323079 7822045142 4581570502 8600520106 8685293132 9900661105 7247083552 3101554374 3550010658 7968804368 9185375310 9626365994 9470015255 1994009380 0545189817 5552724068 0638695904 5730507433 4228251474 7458530162 7334332731 6774393245 1576963564 3984925082 9394139711 6305050460 8183541863 5114984146 7320255554 8610059742 4529500103 6178778948 5330045266 7010458145 2377032448 0747754427 1825101857 2199272648 6402136621 7764069737 6856700777 0045767093 2189680593 5232422124 7943432285 0762453879 6934917215 4859796040 6316944320 8381152555 6407250186 0488797466 5521971112 6365699635 3117155654 0709850687 6065627132 5027087919 5850211122 1417951997 5768506299 4855604203 2910650860 0370277968 0956289326 2465401177 7610763740 9494794083 1911461413 6416761309 6863067436 2089738104 8426633784 1867891633 1898125921 2233199815 1609928782 1330564367 7388963732 1232135076 0791809975 9427589077 3168619070 5603972270 6539184701 3838290147 4846077737 9679432972 6775336850 7890887071 4218562150 4748238639 3483113251 2364535365 0235954611 6967018424 0502733680 1078577024 0088381311 0301667291 2628539552 0624552196 3784389840 9957587096 6686891452 5638590900 5348873440 1283627119 8582197955 2799535130 9240481840 0745306318 7547044822 2587929957 4434264425 0596795137 4624497775 1114622594 2512353777 9849133984 7505328380 7800500531 8092017168 0458954285 5957542791 5645824218 1295028520 2006329818 9260420997 6222719303 1674660691 5411578653 3445585205 1617911152 1151263485 3005096436 1950347358 3147455236 7547857109 0731475777 8139270137 4856664895 0885063465 7399478971 7759174719 5673346013 7261759689 4221112417 2931646904 5484596480 8241864344 5890440234 9073544298 2794577762 0033266715 2040624671 4821864150 2426487371 7818992091 8825405838 7323237455 4367966408 9634835490 6212693457 1265361438 1255505336 6793091397 0046665645 5266232963 2260436705 3806214077 3567391311 2915196715 9786421174 7550396865 8457994009 5049758366 6306069563 0546322344 1596154787 4235632456 0934659767 3647273810 0869850468 4616423727 0591808059 3048597543 6519200717 5716746263 2994547115 1604569542 9428137420 8832292028 0316605081 2999167427 3619412407 5084397923 1663319161 4771754019 8605022521 5683955203 4019376355 2010205724 8944064037 9513006741 8047270592 8340698726 6050590816 5181322788 3560942053 6830325514 9778544790 5352063897 7313602520 1200470408 0045112883 8802728207 9154571279 9070369362 7812836585 1143296686 8109688581 7838279525 8052255838 6941295848 9338808442 9580790514 0957504904 6329174556 7147414683 4788072810 5944239518 7540800143 5347886554 1502352928 6027835939 6253086381 2128079462 8812593871 5212427825 6607575428 0131298064 1986586972 8388710273 6312824851 7629481697 4804268047 5458941465 1236418281 5739810008 9194548072 5266561278 0411655245 4555258139 5570312216 1946560664 7992959247 2077612632 8716036846 9104492196 9688151094 4590965353 9395382311 4212629804 9555375806 7182409828 1916600182 7303115764 8056116317 6922964391 6100561349 7720910549 2880725908 6231019867 9699913719 0433191380 4191330541 9411122564 7565797905 8494102067 4740410214 0026681075 7982744108 7006540081 8532330475 1871733662 6478888223 3124860767 4683634992 5268668669 4774172991 9211262093 3437825877 2493736582 6138853008 4007020037 7010510562 2204824106 6758598824 6861442150 3373437561 0219654559 4116634025 7177302277 2779872656 7541680330 2943961291 5026680187 5824759056 3019042274 1510313850 1996882965 2514859739 7194071726 2373149965 9730228067 7323804642 9898498409 1565049427 7577827224 5030384601 1238383809 6717390310 1409608644 2233108807 9862295872 6105742268 0927918282 9520562921 7409816742 7872942603 0829218590 7617969231 3242337686 0367313069 7770010755 9801275608 8852432346 1642139775 9806052619 4258397330 6865990653 9848613474 1350511159 8466780415 9859383201 5255748291 0790122268 9800184591 2898698338 4583622732 0810970065 3957178538 5079140665 0736129738 2306630586 7272333685 6264484045 4862729449 0478813186 8322914239 6289846717 7722375834 3179583879 2748648261 0265114176 9476603494 2703408017 1574704395 7146456110 5347484407 4852409653 1008564763 0250629181 7177203376 8903496849 7529598379 7925955363 0081252352 8110121756 5433022676 6205911532 2508006345 4643111021 2393150777 6830865213 7010473466 8727321025 3002323978 8275143861 8464591112 6184951878 0537488362 2526295175 1784200527 8420551796 0146649749 5377575482 9792472189 8620022884 0488734017 6997503306 0670229141

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 ≡ 21 (mod 64) and therefore cannot be a square and N is prime.