Primality Certificate for (23151^5347-1)/23150

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 34.163526% 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.336955%

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 = 5 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₁= 31132651 0044263498 3371647880 8917311252 5428425544 5135262069 9447562776 6404497705 0522632597 9976273831 7229520349 8568949267 1903069830 3226067786 4116633697 7396290662 7484140163 6167718292 3430246832 1661058797 9660879773 1693794045 8456954477 7206397704 4932054704 2539021105 3307854954 4996865822 9172819922 7618901772 2384537121 1676073756 7893225039 2706579674 2749945966 2273302380 4945584973 8024831303 3037586680 7493936403 3865003602 6887507467 7382180790 7625352516 3335754708 8342523986 7158608221 9081027385 4330754320 1027245879 0978672511 2379257144 7688528514 3246069818 2470320010 8070475685 3941688512 0599814244 4672072959 3540468638 2326884645 7985639322 2954214760 6094044036 6668464679 0225028647 1296356212 7604430236 3531783405 8127235523 3455887613 1530251957 9464337176 7185930231 4084390090 7799454907 1043548039 4223021695 6577875331 8044268433 1954071632 2793679775 8890899028 8522714022 2407887518 6964748840 6507133097 2203563486 1249651389 7410474507 4377621038 4577804304 5644869991 6259622739 9752742349 0701498782 7035852715 1471237099 0118111514 2874387111 3026538967 0893235751 9740588199 9252156795 4987766144 2002262213 9310745302 4290702168 4017404945 8701386231 7897757991 6925673038 1831126926 7628229478 2277077277 0820541505 1398592420 5788742780 5222727835 5762917801 8292525613 6280371204 8941301741 2810296462 8184644389 4950432381 1689952766 8373144085 3681945112 3210680340 5744799326 4469614705 1681029279 8517028985 7336743431 6218427704 5180581970 3397737884 1140528164 4485761140 3109724491 5675094764 1144681148 2515169200 8048926246 5806745192 1381122350 8463609808 0527254185 1323320012 4247825401 6503008678 2125138188 2852404804 3853635433 9925888375 2307707569 4920279828 2545638129 7395364677 6731042870 0391830185 7561888851 6736603884 4827979686 4804421060 4386341323 9998176658 9462809747 5054021347 6279765590 8486885616 0996551127 8393687010 0136434794 7295578259 3847717370 4296928437 3034295343 9381562712 9009174960 6516720380 3861733243 9267090222 6118580000 1782223318 1516383072 4733380695 0495204374 8876712313 0145286789 6984699836 1292107717 3385198729 1883832487 6003024353 7241312496 5700079299 3746441208 4255132479 3063046820 9185735074 8378869693 0106820558 3403283937 0342522944 0235600233 3312542344 5622564843 6788428907 3272162280 9239818559 0133794931 6141137675 9121039340 3007009827 2172165941 3184705201 4377699110 9515239331 1605880202 6534715178 2573951747 3540326492 8330176738 9033610394 8331301182 8761545540 4147133960 1441569955 2230025744 0884858391 3990272597 5536897973 8573969050 6785412836 6424094022 2747895243 0183848270 5610192874 0410084259 6303572745 6136642387 9422238356 8841452066 3333634899 5975873375 4869102732 5626176018 6497427576 1907168240 5062036852 4198894035 7115404316 3909105451 0562141246 1672980088 4587456512 7175266469 5615274486 2392618871 6183736793 6887178806 7134851549 3253784353 7059423823 3940816320 8928325902 9639900681 8812716154 3261044984 5484193821 8813560812 0068740978 9154829799 0504584690 8002799561 0520829269 8752085227 3147468180 6741874237 5594085971 4313211357 9939628652 0074120349 9916804453 2386051530 2918127636 6769165680 7516533691 7594109311 7626186268 2746794366 8511587196 9850048846 8421693087 4652017441 1553065731 8987119896 7115114910 1200275368 7401957751 8890816778 3204229510 0459557981 5680440953 2905491379 2215678642 1429799977 8363333748 6226426157 0259277784 5789557856 8222611936 8729387761 7333954738 8936621184 5838423380 6181044238 6511040021 7957578395 1448224113 4591794416 8002932061 5702945913 5475331634 6939222064 8499562853 0890056175 8555554253 3415123392 9259831965 1298544977 9745740379 2055852484 7070324787 2794627512 0158557940 0073357882 1170756039 6984028681 4665882135 6281353241 6661012861 5675732096 2197428991 1408794237 2451693535 4811951668 2867276947 3204783113 4162938650 7250842733 8306052922 1745318293 9445730049 8953081869 1667402264 8760302065 5322320773 2048397044 5616137869 9077541433 9320392039 3081320440 2093818065 8596958783 4695391876 5292816714 8958133849 8478657772 3823786061 9146924067 6972935855 0126863814 1905529544 1153269675 4116984241 5197140548 4748793184 1787357556 2991838857 4700790448 0266516197 5480775368 4060101939 5506962481 0118825840 1811028502 3819836099 7930920821 7576230228 5474714543 0004313883 8452520891 8504949068 1497644069 2985704110 5864874709 7176719367 9268453450 8680882735 9620117992 8299385828 0726256567 9413800819 9632687901 2352129127 3079663191 5176678449 9988711235 1946261973 4219440144 8470447657 0789330897 5942596626 3618350517 7648957515 5584794186 3978919540 0008439435 3535062654 1207485306 2674999200 2478777391 4494765814 7313858087 3945774761 9277100575 5883991287 2558871998 2708053575 6064165093 4996327152 9461569231 6269470037 3455088763 4903239094 0531800207 9572664708 4359619332 2288905577 1516646691 6058118595 8623404425 6830612508 3586175593 9051294782 6236099637 6647956226 6270309371 5397329550 0529953090 4418357575 4393943653 8923443350 3163143281 3118691142 9774812372 1917058636 3893187925 3749648382 0814704612 7157711076 6874495696 3546211133 4116916613 1883382411 5754406856 2812710084 2320832827 8628850678 1882325754 5734225382 8660489158 6239943796 5062738369 4709802137 9653723134 1351363401 4673303590 3540804371 8731606258 4091873348 9636496124 3178685733 0013070582 9320574873 5122430190 1916252026 3159475990 8665317063 8374572197 4718328976 9343433491 1469187960 6776461767 0209632000 9456922911 8027040704 1064009832 3734424531 8586452769 4609978640 6382217048 3785080808 7309618116 5280993538 9697481519 0122220951 2189063170 0369836102 5044786022 3022357193 4660229860 8588269683 5660152873 4627250193 8921144844 2888471504 4864240467 1442787270 0864273729 3060058610 0650198048 7060044143 4431291983 5873972260 9218987809 5222306431 5563175459 9318846411 1158368155 9890519314 9897997857 3908160466 6820478259 3564924509 9346571358 8518930759 3956318508 4479948576 3269691301 7877849663 1720351836 3362103382 4753879352 2126433992 8600637047 8466543857 6045466552 5915488548 6332383382 0576343187 6875685367 8195057329 9837091839 1153242669 2616746172 4022501028 2685817011 0562930252 1891158591 6781023302 1593797333 5521054665 2976610598 5076643466 8993124892 5495518211 4684457289 0559862278 4413996156 5646639690 0131078618 2625708312 7220692155 6762944682 1372932662 1574594660 3379621112 6694763539 6355827848 7161458358 1596656477 5039474120 3391475294 6469180524 8497932701 8021340232 2918493556 7965909458 7850294341 2168760149 3488493751 2572954838 5166496040 9676210861 7683675747 1978120179 4489095156 9185471109 3423690947 4575212000 3829587646 0453598666 0503040499 4811845175 5315908194 4952856137 9226001924 0773683206 3260921969 3291673533 4341769735 5340821599 1034453740 7445624869 0229817985 5751381185 6093206834 4079412550 1433715444 1333695321 7024368305 4234963516 0806156172 3482900102 5722052693 0660998208 6730777648 2839009563 0376796641 1662181796 0834243391 7337913379 3707899143 7471132445 9717107338 9528795058 2757592928 5611559451 4170053728 4384012345 3367993599 6226872628 0553729362 7126501911 6895764151 5818101099 0371504590 6153299229 0266275194 4819796894 8115684338 6880103920 5752902541 1684102587 8362863424 8802087932 9358674517 2709849918 5369609183 1509797705 6673213946 6061497725 6731143727 6570235230 6331975504 0376979533 1427065162 4547240740 9405842882 7182958251 3449913428 9166223393 8258312994 6919225155 4323923029 9775189371 5721907331 0495064209 0264112091 7912964351 0992592234 1960627573 3889635426 1168874673 2106315643 9276352157 8521740620 2409164292 5389470076 0152162906 0885640450 0827288308 4566675261 0521740367 0328593403 6008198816 1719587703 0034182763 2675235465 4096596995 0859339965 5292501101 5764291117 6179980072 4532586188 0835688884 6641146462 0909172491 0900717378 4720993747 7654932386 1370680937 2252758026 6055831942 9750964349 4340552279 8074314194 2445013559 7023694264 3210023760 9274984297 6311012628 4159301731 5704879060 5254218080 6117272274 4042388503 8765478858 7130787120 8747739799 5940935203 2405816584 2982384703 3951373157 5683652975 1372335852 6173621349 5233503194 9129145329 7443114093 8392046844 3891096572 8659413899 6563267807 6630638578 0735242942 9375305688 7314537857 4068866018 2106402450 0758442797 5706035523 7978293215 9765565290 0345444843 1794640953 8192109588 4473305071 2570111856 2408147920 6724966833 0179219033 7799697158 1710646505 5367670152 1839593982 4777110387 5444229848 6768694890 9306681828 1246817321 1974546838 6014734169 5367968756
• c₂= 940142 2644611247 2539153562 8354482000 0828440631 4364201418 7145416372 4451254115 4816074807 1640723475 3552459719 5500782109 8275874887 2656871907 4573448705 6404670664 3555759739 9146394458 2439935682 5325739376 5657071564 1338967849 7764711637 5548458111 0362117152 8459618229 3083340377 7346228862 4607327032 5002253460 2295436850 2653447719 7596699366 8893701241 6966113162 8060292094 1952817359 7240597164 8618810159 9700895380 7703628415 3656546693 9801808218 4683292674 5786296193 2303128501 5551149799 2486636091 6895784284 5396673231 4726792142 8202623814 5218935228 6110270347 1924341543 5800937744 7805851562 6057988484 1017649930 5975768774 9335968274 1480699091 3452847369 2781113129 6296935585 0368256415 0367588537 2718921026 9964347217 2438375872 4100697249 4273876921 7432252949 2663942058 1868166705 7562937258 8360820028 4059261202 3176357537 3938097914 3898353443 6975422433 6332693519 1295626036 0131598846 6100500921 6828929709 6695766396 9367369725 3506215174 7970716752 0631751516 9060442216 3852707501 9941046211 4079184502 2768438336 8591179922 9096691528 0639504580 4155247914 0053938621 0414931071 9517024355 0265751486 0339123929 1476830096 6994332762 5123176620 5781035285 9146526512 6436180985 8855452667 4130242556 6144764510 1498022876 0967297017 1334844180 9769894923 2002995654 1933223818 3645776583 2065823273 1598538986 0233731939 7499997241 9154972649 7433820493 4365821155 0066700020 1069517418 5000547125 1965110104 7595922806 3368196759 5339330501 6569065848 9714272042 4332549146 6406102466 3769749215 1512798297 2759028824 5191947405 3876278093 8636268860 5545725827 9992516242 7796911707 7505391873 3330432780 3390834817 0913314196 4692158636 3507023544 0211929043 5921342998 9244283488 4901445853 0932885022 3011335691 1986670557 9771753737 6438559869 2522714183 4879033844 2027010311 0027987375 4489208372 2211687620 9441809171 3160754354 0260181550 6766793675 0638949633 7865143241 7522042857 6312525776 2433937946 7182701691 7758695930 4247503730 0685628762 3308534085 6020144365 6595945878 8167466708 9139836715 7583486941 7665145581 1100727031 5878678262 8529790149 3752315355 6388760177 3884670363 1595144969 1561691834 6120124109 3001016009 8456809173 2094329038 6624172356 3521153986 3894142478 5200262661 8122743059 6837611257 4379745171 4195083202 4683897202 1456695200 5480757664 9841164531 0103103354 5319909801 1427588493 6192910966 1159684659 4121297979 1475496595 4516692784 8144762437 9483455166 6424095508 6243346124 0677757123 7196812283 7409580027 0457339089 7513169786 9456818813 4087487162 2406772996 2854116918 1061511477 7845244847 4077861882 6471758598 4035449547 1106988372 9697307608 5860071223 4321695550 8763385094 1540298883 5766690090 0605125094 9409281133 6237846760 8572695444 6815016692 1686596089 2092888053 6398000520 1939310608 6616839388 8334909448 6667904705 8775880000 6298094908 5129186616 5060230473 9062263264 1379692489 7381833687 4158426593 4437185463 5269082777 5381627442 1215775882 0087337038 4007238648 8855208851 8530025239 1028762984 1987548021 5298918831 4700214619 9851074288 2241001975 5432815341 8259406881 5227750226 7589969757 9569038843 1000512600 6376579056 0828302268 3281734656 7190887519 9288978829 2312323383 9603474493 9205024385 6679715187 8480162431 8551106195 4083799828 3119103456 9425581182 5173869995 1107645901 6927487756 1150977044 6584840200 3563917072 0573950352 7709316928 5780208035 6391711047 6381413058 8297256570 7138920435 5247684175 4906402873 7733408528 4596043359 9970396555 2869683162 4798386217 4472855684 9589348472 5234393498 5235412565 3706024153 9083979294 5019219611 3174590888 3635950287 0117001008 1198784658 5157221535 5874642858 7381684537 6342374250 4145500328 4942658086 5134127216 8751531594 5249758883 4565687900 8374459761 1172207648 5700493477 5926811158 3411731100 0161601969 3020846492 4244154653 8204098275 2638520888 5011960498 0622526902 0585103789 0074873087 5813948036 1770907049 4809351344 6682979441 9195075413 2525686467 3039171214 2927795990 2916364961 3113344790 8383475412 6653766106 0368411824 5006343035 2179310066 4638629558 8981811330 5480239559 4462957242 2221723793 7892953767 2385846118 8012494175 1924253726 6937159987 2700621038 4123984562 1895206919 0667377408 0382723589 9005028075 7404267820 1414595936 2541301713 9474249738 1492850897 2779396873 8037830107 2715567732 9523990055 6791180549 1132992559 5475598612 1444068841 8509772282 4627296303 9707480185 4126414195 8084737004 7771958272 7417412510 3417598326 8703860666 7872584074 4275901829 4833366578 8780042771 8312243648 8986546309 9359705912 3415085999 6282404878 7499600608 4775289865 0732633194 4693414312 3098866633 4255247156 0901772369 6175571691 1967938228 6940499951 6015244440 5079204139 2047248856 4536191252 8947963317 7218753601 1703345539 0744286718 7062754171 0320053642 2155798257 0999566762 7370741814 6423151304 8497667142 5011027128 4508139548 6119374991 9163838075 0660457573 0273825472 1889053610 3503359531 7483183100 7903449429 5038953939 9610908367 7280433839 5468613681 4440865559 7594788341 4903581576 2906047628 7516072228 1222679497 1329297013 8347574164 9950935078 6100396769 6821528882 5203922817 3221537068 1146267248 4158917475 6464298770 6661142917 5911126137 8983577576 1843327541 6504008675 4440782066 6557348554 3552756260 9514023987 4149702978 1999144106 0953435132 6294764502 1166324174 9015172120 3543167474 2936387940 2357243096 4848930139 1526595334 3994961952 1492421972 0876019820 0250193141 3964716172 0960608600 6201577191 3727118707 1424483911 8302705330 7055032951 1569231180 3243285496 4098751426 6706963083 6283903890 0611597283 2657409967 2297542086 5954933114 9116132216 7633408266 3768570605 5880633213 8739559470 6392412692 9990144533 6356226999 5841393608 3582719153 4474543468 3620558437 9679648177 9650911772 8761418697 7137948242 3552986339 3525795366 1589373249 9150060429 6182150487 0403091822 0010459057 3389978556 4804238732 0369207712 9612866266 1688229714 3613682675 5624724095 4499638967 4831716042 6579336520 8597096922 5290054356 4626232749 9240640616 8667230516 1774976108 2232146021 3161142234 1628325717 8899129883 0631254917 2769922898 6486680000 0878930091 3408964169 8827934724 5626213852 9060289528 8658964737 6650744849 7124430868 7078875781 0129360859 4789019303 9659245003 5731004720 2827142109 6468462709 9026041709 5111703126 3829495111 2124040498 6295359608 0470239415 2949204582 3967839516 0964953389 7851245309 5583212784 5138647590 3977298716 0457074935 5708219896 0966489273 6306827447 3520225743 3059937904 2589721163 7532870375 2837754058 6106650079 0000245048 6993456674 6220314203 3639220454 2460285204 8683471547 0401624227 0332589114 9052663830 1391247723 9122079619 3520969773 9271501347 7428692196 2093314824 7059702952 0094575938 2433003608 7219142765 7817293187 5811314724 8399364776 5102396017 3001143750 8528616869 6857606393 6145320329 6943837001 5895176005 6642142292 8031867953 8927640700 8021408833 4079303373 8517803226 5907135973 5441081148 6657837501 9540179812 5208821129 5050847027 7232028556 9505172414 4395313893 5989356576 6554588308 7873771128 3317565630 9760255900 8143219488 7321043101 8557424652 3712880779 9318290736 8836906686 4931673323 9886861299 6070272276 3249293513 4375277619 0206446361 2203838709 7156000022 6348788273 6882923873 6902724788 0143146851 9660477710 3915109803 4803739636 4307807925 2684492484 0740017021 4565693222 2933731719 7217938298 4052307084 6217858302 6327244821 5389570863 2392910813 4212708489 9466201748 3514026024 4937614647 7976833225 3556243224 1397324843 9294221041 6931701655 1241744301 5740997509 8559256391 5347767174 5155086643 6708515223 1961527369 9358280516 0644538331 6193044074 7148826921 4275913274 7269770470 7180991395 5074331753 0670524484 8666280996 3477579476 5290107357 5347268239 0768143913 5363618203 4840009521 9158438281 8922186922 8145061900 9282000888 5535187491 7763882445 7102990851 0645739005 7947141587 6472962145 5333671245 4072414073 0403280678 8075165186 3887716617 1312426911 4504304415 3117182639 2737845377 1991708098 2413592658 3539155871 7096662637 9524051209 1903186716 6826487015 3377607508 4261717248 7270634192 3259197982 1801508723 9569730212 4601343605 5622181069 0818007313 2226654213 4522281627 7105541072 4054044201 2708936582 4247727967 6601063524 5335496603 0334253987 2484019108 5802146607 3097406060 3503565694 8672991677 2217015986 7572783112 0253782585 9225899768 6154206122 7338438825 1924394925 9329196386 1276328454 8456922469 4419608460 3632580200 9525425330 7116061064 8971727650 4981924843 2102661333 6797650858 2695184572

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