Primality Certificate for (3709^2161-1)/3708

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.390675% 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.338358%

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 = 59 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₁= 1 5189240060 0060275389 3062946584 3623810781 0912894768 6085873124 5193964322 3880571798 4233585670 1430234182 2659787101 5681106088 3346598607 9662741931 7701641666 2779687388 6886064998 4747240570 6010449043 6489795615 9716464074 8904790804 2624213185 6261434120 8318393194 4175187317 7697213305 9610237785 6408678096 6542753393 6840479321 4514779543 9360159109 4524829833 6387431824 6571137732 8149464901 9812888803 5598854360 6750330316 6667728849 5334284113 7743521114 9069526394 1862532991 6195909582 8547706623 9803934318 1548750845 8911182269 3150155224 3290260404 2299853112 1999299675 4378710902 2259765832 4481523688 4818050240 4328909814 3793764808 2911254643 8304994466 2426209326 1156434846 6301064871 9240735890 0281691885 1355147986 3723853205 8372185575 9887544881 0730603130 0906324977 5269996298 6317915383 1830222184 6456977021 6134292542 0675633836 9119801885 6292980963 1029451757 2832469005 2263503708 5091135208 4988295515 6644632368 5896968574 4252528935 4043131625 3959975249 9023418062 7864154613 7749905532 4033629098 5585914773 9648079162 0240717668 4105417961 9454093883 5502040550 1005391252 4578284301 3040937339 2715659597 5894390160 3573814424 9924204648 5792191742 7053897125 2266174491 0660382306 0925770880 5812602484 7282384016 9849203911 7237260071 5667161780 0527696184 5738114179 9144826984 0017831141 6745834146 1280454835 7427064541 7791343591 2822592541 6025173358 6455344515 0698668609 2788662414 3494250207 2076467331 1638109630 1130809091 1276109113 2751721676 6255751428 3577081960 3344692452 5596521325 6933688070 8823357329 2385617242 7382520867 1460261903 5853720358 2346017252 6600705961 0863670292 0670758348 7269244629 3365712838 6111038728 7275015958 0205842466 7297866129 7462067256 5813645658 6247218049 9435257412 8336724547 5796527595 3647902666 5034983239 4801651149 8570738903 2980630427 6979814143 6799060942 7349005037 2831768029 7368203761 4718174994 3946126295 9909386716 5630149337 3532750753 4168840985 6901444480 8184497682 6576572026 6013326709 3593995327 3614820901 9367855162 0562433232 7999867593 0652472161 4587492159 4627138968 3097922236 1074824417 5979389108 1791655962 8647087749 6531708199 7798468462 0303910191 2703719902 7615897259 9517078575 3779722996 5242317192 6271355152 7363432348 5608778345 0836696240 8701957673 0993516625 6754336457 8921840170 1523267866 7057824268 7476171394 5826894417 2913027372 9775743958 6282867289 5417801665 1806604850 5052911161 4210338359 6417003452 6495798570 3946879605 7407627763 4685010036 3501612344 3845579526 3218466879 2749782200 2881470626 4272172922 9872851779 6802286426 0380425950 3129708708 7784793257 2217455481 4414253832 8021685050 5285658013 6287607550 1838270226 3923394091 2146682701 8135414504 3467392964 7343164930 2380054351 1797766215 9839243304 9684592600 7892760127 8225899582 4333674750
• c₂= 1230991804 0711701487 2358998748 5751195576 9026985415 0557774649 5500871610 2839773250 8298745158 2339220823 7805101775 2772379075 9031670171 5660921334 4484237952 2558381018 1618754641 8109385733 1644877299 4648450859 3969915098 5711558538 2346815711 1787416256 3355318399 1335696806 8468169875 6291902882 1193309791 4591754573 8100711091 8308770609 2789874195 5158090489 7970709083 0194652911 7838961185 9746553526 8775049422 7254950013 7962464177 6113640669 4754622273 5915379732 0407934311 3390981957 4293388811 4286540269 8946893554 4408252321 9269581292 6263858337 0787109904 5552317154 3411709235 5692998828 3763948435 4627968648 9768056338 0604000193 7872132848 6481149419 9732607554 3956280031 8488415605 6082523048 9198721023 6145562391 8326374351 0311912485 5897943607 8764394670 4829840283 4787939843 8633306840 3109499975 8526384987 5832964972 0035402272 9826913583 9559548247 0201357605 7537867675 2874062793 4965702044 9096836169 2322781537 2276260804 5080720973 8327564866 2021736313 7670499168 7687699636 6453934487 0530635940 8882665146 6818653719 7487335147 4367378043 2695573559 2528697448 7311491219 9022511127 4174210078 5553480766 6571008371 2392063639 2723010044 4531638777 3418186030 7205774485 9015580981 5021377703 6226647068 3850024806 1760553218 7699136667 5572534311 3454452320 4001649063 1251663900 8541442875 3456359849 4271974558 6015932201 4082277027 2116757067 9192986085 6085559468 8278569578 5851308234 4348508167 2834963611 9639653327 8096716366 2179485727 4396421971 9997987635 8555394793 9086870389 8692888264 1037533847 6249007729 2263995870 4793591430 3937194192 9504471265 1140722667 0508430660 8594155916 8026478866 8615042763 0363131978 8755611122 3322863644 1423262048 9357263214 7275514727 4936953926 7143871278 4931538983 1403275531 0725125725 1898292277 3368761340 5551644583 7404270409 9315399582 5006653425 6256761019 4753000399 0603381865 2244074828 8075537523 8891374267 7753885648 1904042403 8958527471 7468263352 5987513974 6274127562 0917980917 6498160791 5776685305 7848359447 8645999671 9893158683 3794538727 3311520521 7464992387 0355996248 6791000427 2630706797 5958954271 5060085006 4872655791 6819611617 5489083161 4850503044 6973261647 0096443270 5295218068 3810671290 8181214796 2446881347 4943385811 9844925302 4275641593 2645943083 1332305676 0017687907 3109716641 2505702638 8021133383 5258193658 7070636813 9362119323 6367874090 9301858904 3822367285 9149527856 1621966649 8867609023 3879720732 7139740498 7372993522 5294681845 8578541949 0315385319 1782805446 8413576664 5167177471 3446477330 9652716278 6285399369 6985078795 7520682428 5852265351 3824700441 7523596693 5720394027 2718325288 8434132243 7613569795 7961823292 5969127369 7169933131 6888763069 4286654365 6432358166 4169281611 4503915427 0838363793 2986822575 4718525020 9323304375 5104197450

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