Primality Certificate for (8781^2851-1)/8780

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.673517% 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.353395%

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.

Express N in base F

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

• c₁= 271456391 7676111049 4545643626 3537632991 8570400696 9898802236 8046255124 7461498773 6418143319 7001572183 5718222499 4602740775 0911976763 6418871305 5051864190 7028630128 9636273433 5391497579 0119087081 0535014127 5369028860 1977887293 5608287944 5344908578 8078237901 4716488468 4892621574 2741908129 2480245181 2403663376 5504996648 9739992134 7162105531 3707922357 3714573623 2072627653 8919560544 9528822656 5541668276 0257457379 3622513264 2658102903 6972465357 4674870021 6118400311 4039148199 0970022573 9631770341 6106757682 8658240714 0595155169 9692485863 2482084883 6870094860 3515179589 0370590520 5680395594 9093195772 8705192042 9210805021 3559795699 1969661119 3982047260 4994135304 9886422903 1801015487 2811411145 0365475221 2285230035 7207681585 3654312854 9074665854 9272416611 8495330605 8548685229 5899129743 7943648234 2370720106 0979716309 9286516620 4002912320 5197612182 9748453188 9190897792 0627265879 2772025627 7996252135 0572086127 7703625616 4359953596 3982000897 2843883613 3055571054 3932648768 1650102822 9414066472 2603335947 5975101589 2125258022 3567734440 9926597027 3867485168 9344527336 2780959892 4987166950 5155483370 8224337815 3265196645 2453960891 6639761122 9642919649 9636214547 1678535734 1485040841 2977161825 3471323868 6920720017 9838607528 9564500036 5401472807 0468794062 7066914465 2314232649 5712286859 9088176721 0804844384 5765335663 9240182999 2682313376 2344139966 0515933179 8147273582 7317650950 0642787615 3263345035 7519688387 8955118469 1912333547 6473069116 0551079325 5978393219 8686528232 7554574141 0539466486 8508277119 0442923269 7905683179 5813974051 5242932643 1754853196 9261891871 6560800676 4863735949 3675191363 2426917468 1051659763 0137401296 5796023899 6833550031 8513106900 8863479651 8615678327 7065876663 8683110569 0324286814 5619471762 8795644371 5546813405 4212145007 4773124861 7645726325 3700361557 1372155522 8745593162 7770479005 1651348001 9467985852 4248226420 2461921666 9659601068 9522884539 1593731042 7341855021 0827730582 8353304165 3820552346 3872932665 1454596976 5820289308 6062711107 5801188210 4580284529 9582794119 8169324565 8833832973 2332019005 2271513004 2374375357 9744491152 3710081837 4700390432 9624251547 0346791945 6149278418 3898399143 1851178077 8073849421 5271318964 9992032436 3945472097 4816830513 0891205054 9947274562 4498172350 6298878622 7736474635 8333202096 3281288539 8671103748 0132631149 1564980409 2563813622 9814664039 4575043976 9214185205 0899929841 6456190828 2806841559 5631991598 2734359397 5754734711 1978506824 3061384343 7143595178 4617705730 0388451375 6300288532 4798921275 7938062755 5999621049 3858809643 5822845414 8270734984 8468735197 9585668296 9311938905 5419655294 1640722654 3643474525 3182393459 5757670562 6858797473 3783848280 3643442631 8334389075 0446270034 8676538145 1205029264 6568391129 9323361833 4481977343 9125190611 1211446331 5887370777 1521497092 5557214163 1265397947 4134948810 0612895166 6379283135 6453037749 8328988573 4754250471 3630773434 9019372166 1205428447 6465640951 3248782025 2815057406 8636171236 7878676936 7279244292 6041399023 0758774786 2729944874 7310246904 4879531821 2971071058 2807415625 5595247664 7700269198 7440392428 5727516128 2648911009 4526065401 0708224496 4910704019 0879629487 3737389603 6454413016 3750174115 8843696511 7817794334 6256343838 0429170868 8872667117 9481298934 2733423883 3703305103 7696765879 5736721947 1087302059 0570361669 0735943549 9089212298 2304065775 5989982099 8986102468 8545897032 4412628570 5105534058 7376451718 8084138481 4459687166 4896499419 1350133097 2168851692 7251662093 7862574986 5923730383 0286525804 8455843703 5170273960 0990172739 1345684167 6807151603 7898406324 4083729844 1533563094 7984002539 0182463749 2684518360 3248839325 9531572126 7040816557 9862286837 0779644559 0648108967 4426534120 4530256819 9781656881 2205529764 8028636116 8710430609 6252659714 5876585084 6611200410 1168202843 2684339036 9854548717 0495277307 9815249734 1256345134 6377313624 4800746831 7528391198 9821932055 4242544217 2969326832 6339910362 7042117449 9238322525 4741422995 4476890459 2454227868
• c₂= 71 9801803070 8663533428 2999909894 6843264165 9113775218 9223223182 9879657533 0476426790 8835813236 6705184935 7032408285 3522906252 7595618569 3928738237 7760215832 7832551092 9587192207 0340182834 1881765063 2419350632 0566122426 8278805583 7607068466 6321966464 6533268490 1779067641 4236866281 8878766499 7091666122 0811956179 7654750688 1168263099 4346364854 2819544592 4503916402 0449916268 6391939883 4083016302 0245347363 8560787012 9385309889 3701119335 6522839309 9468626207 7746308243 7366676652 1779087771 6727671672 0541283702 1140655461 6362399707 8436381570 1446917060 9615224219 0191987394 4721490669 7216117325 4274206694 7430802794 7647173900 6931602002 6748953735 9203282447 3627402847 8196482957 8227392654 3698354003 9546804217 5305283813 6242268836 4949196479 4283336642 0978903690 4963424317 9886270893 6313969685 3294912214 7028532120 5505782932 7524413722 2829577763 1714080766 3265556475 7942594480 3539411032 9638428396 3794670731 0792763853 1562286603 6924042672 9405567784 1434267571 0124454578 9749887694 0206403557 4487344327 4876893760 9028523766 4376206312 9013552434 5227643632 8216633672 9099506264 8330893824 5708761508 0335803799 1971771048 0933197682 9017238003 5073989033 6416927740 9380009064 0381215980 9698757166 2172629931 7571938361 5486608822 1872077812 4129279234 7232714326 1954128369 3421142833 0096237965 2192399488 2422410617 0656572685 6670546512 5823392548 6626284372 6599710430 4610311254 3860790449 3923890993 7405610519 6708634498 9327613569 6076506405 3537611399 6114688860 8428182823 9297439268 6729764824 1210862799 0278768314 0324956761 0956416304 0120696064 9732875383 0578591913 8016176313 4745931913 6929483253 4560341072 6345177456 6480996844 2654607152 7431743755 3852985707 8621162631 6175263028 5827901392 7934949075 1025072515 9172232842 7973561741 9014684182 5735643917 2807284112 9142260581 5742696200 6005906820 8854412904 2506366860 5683234961 2857809604 3220590690 8538380766 9009412757 3531158153 8832293541 3887414919 6546872964 7955196198 0211736425 3502224272 3391090739 5065213082 4125282929 2576839972 7596406196 9581083698 0988540124 0649000122 5163995807 8222900714 4844152189 2283035753 7370062246 9097535982 4129273132 1049797047 3396427180 0994864206 0699224937 8119684237 4517502906 7081272592 9348668799 3369074066 8702096238 8051749499 9197411758 6172633677 7482004602 4133072266 5347941565 6523762904 4681470560 9565692590 7777101097 0736658203 6562493794 7191002406 5126602754 0013505831 9777685584 0474831147 8676904350 6843987655 3328540632 0390298598 5453930251 4978389706 4474431540 8957162865 6065758696 2888074486 0667849608 5502273481 9888875958 0770698627 5087093330 7415095528 6699138851 4966826251 0681178507 0039223111 5224688250 4926386176 9334171911 2269105619 9563585990 5965379338 7548545913 4115380349 3912241139 5853907860 2418680002 4000965892 0274794428 0281036335 3152738242 3701088192 3148927744 8177624455 0434974570 4386872801 6258495443 1533267619 1175973413 4665270823 4337334435 5783700265 3315360197 2139745759 7748622428 9502290241 0783125665 8773144404 8845235279 8899796453 7172422557 9858627558 7209499174 8030816617 6846326076 4450357812 3268181517 2004925483 5474456887 1741231795 7616954440 5540267150 7000763903 4804046007 5358679376 6164323637 3196384666 2204949853 4887480064 1785956879 5217907250 9973282873 5276064923 0132864404 3861080201 0937819563 6718124301 5299828089 4705078807 0471414076 1772036739 8565861986 4190010435 7840234511 5460128722 9811861890 4694904897 8973696381 1312552895 0732177829 8086201544 8207725033 7513877720 8702023076 6051359180 7107109949 3075123157 8053633745 0914840801 2230698772 9371185954 0870444029 1709387622 8622279755 9870074998 5320690034 0418703060 8571795118 9341012080 1712344706 5761109945 2673172744 1205052045 9664233161 4779114857 9440613577 5251787415 5496839908 4796834926 1692721886 3692069652 0251848091 9443054397 3907715101 0581620442 3492125816 5814067732 7522695226 0967662744 4232169304 6367426670 5164638462 6827591779 9718859865 5631826187 6668307816 8447945408 5114146838 1257483769 0111121508 3635975454 6431773894 7125333298

Brillhart, Lehmer and Selfridge's Theorem shows that N is prime if and only if c₁²-4·c₂ is not a square.

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