Primality Certificate for (8684^2791-1)/8683

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.043069% 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.372507%

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.

Express N in base F

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

• c₁= 14731930 7891074665 1656856673 5999261352 9322840127 6829955744 2315365016 9044854581 9534174954 5460006037 8313275591 1889015926 8100063094 4811904694 1805124913 3265569128 0827756781 0018498047 4243844393 1003630575 2946476742 1988811268 9631561407 5436302099 1141387744 2035075247 5695839037 6024638176 7829906939 1092729158 0641752316 6692419395 6051540691 6163319906 8580485682 7288566283 2382471225 9332849563 9198082116 3661165562 5880948192 4041365742 5594664361 0954227126 1402748040 1524631760 1295849458 0612167467 4454195336 2771766685 5172678879 5194737566 9561007660 1231481263 8946455070 8103770833 0203214183 4881059363 6079044310 5691552230 1192859704 4480893610 0288102695 4980010262 7835802111 0505454855 6361128225 4349309086 5449460070 8299647093 7379461076 5294096506 0636743225 3495687025 5043248503 4678191975 2258615529 8479840426 8193099046 1190017341 8833152592 4689524537 6449841848 4645973585 7316562569 4749068791 5258845861 7930968973 7401596790 0817173739 7542088025 8404650194 1431824780 3398621481 0917429170 6401196296 0673592218 7218482152 4802082006 1281911374 6551432198 0195371487 2738083708 2252835749 0050314418 4617924785 4762393680 4448355563 1045739231 8909294053 6998555339 3049101832 2716213106 3172521654 9037614917 2925422558 5009434379 4116328832 5823218842 1158451566 6012584207 8831280674 7703810849 4426976779 8585678730 4150656061 5249680043 7053812146 6793620093 9496223121 0632659586 2158679687 3523019728 4961552748 8155753019 9026187249 1419182644 4199123446 3959553742 9416875566 0641766298 7344701052 2811580063 1679433422 1050458176 7197985945 4955323527 6551490472 4131528727 9821353293 4115605542 3568126636 0048712559 8213070425 6257084541 5499400580 0522284362 7529431306 5950938527 6059599281 1255575884 7329253682 8216806112 2599697142 3275035755 3071068025 5857902413 6104036844 2092382034 9772274199 0393941991 6507836824 6892435013 6723207528 7207939087 0031050612 7078744846 7639593266 8212202443 8997759927 4565571628 1781110058 0912668609 7703629086 4006318060 1406853856 2732293309 1415644185 1615911537 7850951799 4401728239 4046589413 2518424118 5746020554 5722541220 1165922260 1828993649 3987149594 5858030534 8449375864 3796277402 2331312609 2836088652 2818329587 4417299399 5125445160 8845015682 4666069528 5013531405 1978620884 8211871551 7612992173 0418112519 3500323201 9192766294 3014708613 9927365441 9936254005 9689322307 4800527952 4186479776 3196508749 4311622652 7997677523 0678066443 0918169132 8194567457 3033001440 0367626836 9502566071 9009546348 4976712448 3917710936 6847381264 8951519837 3533459818 2410697005 3503923789 9075459291 0286392857 6332604839 8278362894 1153917329 7480349117 2945321689 6448318509 3972039289 8485924598 5528481889 8169361800 0692792303 2003762525 9548877598 2232234675 6695099805 8524423248 8113827200 2308157178 9968869389 5841191343 5319590298 2909242171 2947134775 7582495654 0520766308 5376673123 6945249769 8908800826 4246053190 3228427066 1212943156 7227265696 6208101015 3022505116 5436040201 8620358833 3667275874 8208779906 9576574083 4453456618 2132837071 8452944938 6611853720 5219787558 2396247761 9374627604 0852078066 5274254682 8426603276 8209012015 5639199329 8942619370 9091633582 0780423197 6178686731 8130256616 8354877356 6787328718 8091931336 3119785231 3781209484 7603654432 0414284114 6388327271 3481096695 5115005174 9247092032 7965732801 3155908703 1569774367 3543545649 6025250320 6550885553 4832853580 5515514187 1529570885 5202102304 3718362063 7150754024 9984429990 5259721555 5311415518 1704733957 8302931625 5482953401 1705679881 1033723741 7621476408 0209192536 9992970261 0376657471 0553680192 9345642828 7472346614 0674145850 7808561569 2446558034 0751190705 8477113678 0369406539 5664362995 9346454837 5573070085 1740520394 0234859365 4344623157 6680138692 4804828153 2973873344 2727874552 4368202612 0443397546 1434249692 6558937857 7343598021 3286311558 7329357922 7588296063 2241393388 8699139696 5064257243 6950778560 5433284105 0242436267 6984467777 3983419741 7489269263
• c₂= 25113 0809515781 9589938651 7609114677 9892303396 7522585187 7089242105 0223641719 9033512318 7821066021 1779309948 5881442322 9503703344 8828056671 5700856709 9082484142 5093883858 4431295503 2428105169 3622292586 4951264174 1767845752 3502777119 8629846464 8966499455 4344483982 7195119713 5277655414 6324041370 5915358827 0719940606 9895933852 9987779837 7916313117 9903226361 2366442340 1358969530 7758719647 3761634791 7620413068 4198977051 7794513062 6349120341 7396816295 6939050178 7066342978 4434767800 8485917373 2876681533 1869284512 5066805457 9198174430 7886951453 6098116670 1587106149 0490203022 2959431296 9305876201 3803088119 2913509242 6163716471 3202742750 5661977610 8966050323 8338694586 3609152459 8791258407 6389394740 0571913272 9099252527 0975708136 9883121242 0749832027 0777834818 6059733785 5205967098 5004173637 1967564534 4963174050 3008407354 7925772484 2032899100 7049646130 5743231304 8084681541 1163404764 0716995956 3352834266 6171144952 6862742822 0454730804 5621757144 6010754095 2848556188 3188527993 6511974105 8378075528 5643689701 6259560366 6939971716 0380167786 9840238346 8344134377 6119429985 1957544592 0994498992 3990073406 9879806760 8816611669 1768977742 0745796332 7513568122 5201578317 2924231795 5972398244 4157683682 2250131040 1094213034 7559193984 9119677311 3528956364 4985606184 8439620509 5761361855 4418756775 7717424724 2380983386 1950860402 7737494829 5359338998 6281638887 6994296396 2312535394 4452518674 5840574936 6947185200 3218925408 8654837965 1738575412 3634898656 2990600065 6502361816 0550939668 9395016143 6020371878 9907605480 5746641450 4524926578 9649747041 5486713170 0910394644 1739896487 4674810530 4909171259 2451005168 3366033971 8813663579 4743788273 8411433176 0201796290 7826329905 7692090792 9682810335 4386143968 3847364176 6961618405 9975105626 3183128983 2004077207 5452566661 7821852180 0110300197 6890092207 8223081292 7383017713 6727759833 4099042225 8088885702 2896021259 9155234644 0746759524 7927584237 8419943762 6532400023 2869923849 2951882807 4593157047 7611044933 3767623773 3225675098 5871572752 4549067978 6836819636 0544186529 4768725965 1509980703 9343039312 5554088202 6061575463 8311419492 4172655930 5394933538 6366878422 7247952947 7881190371 4567818421 8701026158 7890281195 9046256503 9125419203 1674699079 4854938307 0649595875 0172452859 7995584264 3184048016 2253117481 2828078753 2368690530 2341706566 7164894707 6508268504 7779383480 6607973966 4576114775 4423949828 9412529779 8167614363 7717821429 6907230399 0506217883 5904863599 1647896979 8214790931 6237090452 9366632721 7397312055 4635957285 0950884594 6315804882 2686253430 0657426616 0085623548 9119566897 0419953827 9688760464 1974553336 6261424466 9352711615 5813552237 2864178765 5251450002 5704220567 5181292545 2401748572 2274512636 0427256817 6868925334 2317421565 9273876614 9639464263 8257099085 5794749167 5467506136 0333256591 5990811938 9950123332 8893904505 4245957801 9191184677 1400812869 8851695018 9770286267 9345969818 4586857872 1565959595 5174829926 5916063660 1804451027 9146897045 9186728007 7370664772 7234532708 2307454167 8422054885 5454159814 9655857631 9720651100 6189323129 6469189452 0690694394 0881335779 0546112177 8456904033 2760730419 9545065330 8625298129 4672588461 2595491651 5607487686 6905355815 8670365369 1828563814 7878457330 1545748130 0991277923 7756160213 8757621490 9837653205 5744816531 5671157449 4663116121 4664424472 4217517396 3339121626 0517231786 9573475930 6241225588 6722326836 2561116178 5625498878 7149335565 6524891274 0942657101 9689268670 7756637524 7477880953 8546637151 4746519996 2694328567 3046377024 5488481367 7341186055 6617327543 6483392107 0329824285 2805914727 8587061556 3295315285 4882113669 1632656338 9942904454 9510127746 5245914016 5508317927 0752808161 0226407990 9202647350 4079061810 1484846811 6625750047 9933374096 0880987840 7656787305 2148331797 4827133030 9941031954 9297887692 2486627232 8157746162 8380141133 9523481760 7481793606 2023260899 6080133843 7636551963

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